Преобразование абстрактного синтаксического дерева (AST) в F#

Я пытаюсь разработать AST для таблицы логики решений. Одна из вещей, которую я хотел бы сделать с размеченным объединением, которое представляет мой AST, — это преобразовать его части по разным причинам. Для наглядности приведу пример

Таблица логики принятия решений

@ ВАР = 10 ;Y;

Вышеупомянутое можно прочитать, так как есть одно правило, и условие VAR = 10 входит в это правило с записью Y.

Определение абстрактного синтаксического дерева (упрощено для этого примера)

 type expression = 
     | Value of double
     | Variable of string 
     | Equality of expression * expression

type entry =
    | Entry of string

type entries =
    | Entries of entry list

type conditional =
    | ConditionEntries of expression * entries

type condition
    | Condition of expression * string

type rule = 
    | Rule of condition list

Визуализировано (до преобразования)

ConditionEntries(
    Equality(
        Variable("VAR"), 
        Value(10.0)), 
    Entries(["Y"]))

Визуализировано (после преобразования)

Rule(
    Condition(
        Equality(
            Variable("VAR"),
            Value(10.0)
        ),
        Entry("Y")
    )
)

Теперь я хотел бы преобразовать приведенное выше дерево, чтобы расширить правила, представленные в записях. Я думал, что могу использовать рекурсивную функцию и сопоставление с образцом, чтобы сделать это, но сейчас у меня небольшие проблемы с обдумыванием этого.

Я думаю, по сути, что я пытаюсь сделать, так это всякий раз, когда я вижу узел ConditionEntries, я хочу создать новое правило для каждой строки в списке записей, где условие объединено с записью. Имеет ли это хоть какой-то смысл?

Заранее благодарю за любой совет.

p.s. Я не совсем пытался скомпилировать приведенный выше пример, поэтому прошу простить за любые грамматические ошибки.


f# discriminated-union abstract-syntax-tree pattern-matching
person Jeffrey Cameron    schedule 19.09.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Хм, на основе вашего AST, который ужасно разбит, вот функция tranform, которая производит вывод из ввода, который вы хотите (хотя она не рекурсивная, просто использует List.map с некоторым сопоставлением с образцом. expression ваш единственный рекурсивный тип, но он не похоже, вы хотите обработать его рекурсивно?):

let ex1 =
    ConditionEntries(
        Equality(
            Variable("VAR"), 
            Value(10.0)), 
        Entries([Entry("Y")]))

let ex2 =
    ConditionEntries(
        Equality(
            Variable("VAR"), 
            Value(10.0)), 
        Entries([Entry("X");Entry("Y");Entry("Z")]))

let transform ces =
    match ces with
    | ConditionEntries(x, Entries(entries)) ->
        entries
        |> List.map (function Entry(entry) -> Condition(x, entry))


//FSI output:
> transform ex1;;
val it : condition list =
  [Condition (Equality (Variable "VAR",Value 10.0),"Y")]
> transform ex2;;
val it : condition list =
  [Condition (Equality (Variable "VAR",Value 10.0),"X");
   Condition (Equality (Variable "VAR",Value 10.0),"Y");
   Condition (Equality (Variable "VAR",Value 10.0),"Z")]
person Stephen Swensen    schedule 19.09.2011
comment
Извините за разбитый AST, я решил включить только соответствующие части для краткости. Спасибо за ответ, попробую позже. Однако еще один вопрос: сильно ли изменилась бы функция преобразования, если бы ConditionEntries и Condition находились под другим узлом? (т.е. я бы хотел изменить только часть дерева, а не все целиком) - person Jeffrey Cameron; 19.09.2011
comment
Привет, Джеффри, не беспокойтесь, разбитый AST не оскорбителен для меня, я просто выразил обеспокоенность тем, что способ, которым вы смоделировали свой язык, может быть слишком сложным (слишком много семантики встроено в ваш AST?). - person Stephen Swensen; 19.09.2011
comment
Что касается вашего дополнительного вопроса, я не уверен, не видя общей картины, но, как правило, если вы хотите преобразовать только часть дерева, вы можете получить окончательное универсальное совпадение, которое просто возвращает ветвь дерева без изменений, что-то нравится ... | branch -> branch - person Stephen Swensen; 19.09.2011
comment
Спасибо Степан, буду пробовать. - person Jeffrey Cameron; 19.09.2011