AST для этого мини-языка

У меня возникли проблемы с вычислением, принятием решения о том, как абстрактное синтаксическое дерево приведет к памяти, будет ли это лес деревьев для каждого оператора? Или это будет бинарное дерево с одним корнем?.

Источник образца:

P: 10
if A < 15:
    P: 9

Вот BNF-грамматика:

<Prog>       ::= <Stmts>
<Stmts>      ::= <Stmt> | <Stmt> <Stmt>
<Stmt>       ::= <IfStmt> NL | <AssignStmt> NL
<AssignStmt> ::= <Id> : <Aexp> | <Indents> <AssignStmt>
<IfStmt>     ::= if <Lexp> : NL <Stmts> | <Indents> <IfStmt>
<Aexp>       ::= <Id> | <Int> | <Aexp> <AOP> <Aexp>
<Lexp>       ::= <Aexp> <LOP> <Aexp>
<LOP>        ::= < | > | & 
<AOP>        ::= + | - | * | /
<Int>        ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | <Int> <Int>
<Id>         ::= A | B | C | D | E | F | P
<Indents>    ::= SPC | SPC <Indents>

Где SPC представляет пробел, а NL символ новой строки. Да, он позволяет использовать только 7 идентификаторов. И положительные целые числа.

Его легко лексировать, однако я много искал, но большинство примеров AST используют только математические выражения, которые довольно легко понять. Если вы обнаружите, что моя грамматика неверна, скажите об этом. Также обратите внимание, что синтаксис вдохновлен Python. Я прочитал для него документ Lexical Analysis. но в нем даже не упоминается слово дерево.

Заранее спасибо.


parsing data-structures abstract-syntax-tree compiler-construction bnf
person Tristian    schedule 10.10.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Учитывая тот факт, что в программе может быть несколько «операторов» и под каждым «оператором if», вы можете расположить операторы в виде списков/массивов в памяти. Если вы действительно хотите использовать деревья, вы можете это сделать, но эти деревья будут деревьями только формально, поскольку они будут вырожденными и будут выглядеть и функционировать как списки. Подумайте об этом, каждый оператор практически не имеет отношения к соседним операторам, кроме порядка, в котором они появляются и выполняются. Они не образуют рекурсивной структуры. P: 10 и if A < 15: не имеют рекурсивных отношений друг с другом.

Не похоже, что есть веская причина или явное преимущество использования деревьев для представления операторов. Однако вы можете использовать деревья, чтобы иметь единую унифицированную структуру данных.

Что касается выражений, то они хорошо вписываются в идею дерева, поскольку многие операторы являются бинарными, они принимают один или два входа и производят вывод, который, в свою очередь, может использоваться в качестве ввода для какого-либо другого оператора. Здесь явная рекурсия.

Я думаю, было бы целесообразно организовать всю программу в виде списка подсписков (для операторов) и деревьев (для выражений). Но вы можете использовать вырожденные деревья вместо (под)списков.

person Alexey Frunze    schedule 10.10.2012
comment
Спасибо за ваш ответ, например, в каких языках рекомендуется использовать древовидную структуру? Что именно будет считаться отношением между утверждениями? - person Tristian; 11.10.2012
comment
Нет, я более глубоко обдумал ваш ответ, и он совершенно ясен. Спасибо. - person Tristian; 11.10.2012
comment
Ясно, что деревья хороши для математических выражений и функциональных языков, использующих их или подобные выражения. - person Alexey Frunze; 11.10.2012