В первую очередь, являются ли семантические правила и абстрактные синтаксические правила деревьев одинаковыми?Семантические правила/Абстрактные правила дерева синтаксиса
Теперь, если у меня есть спецификация языка, и у меня есть CFG, то как мне заняться конструированием абстрактных правил дерева синтаксиса. Любой источник оценен. Благодарю.
«Абстрактное синтаксическое дерево» Правила (это странная терминология) могут быть интерпретированы как те правила, которые формируют конструкцию абстрактного синтаксиса в процессе синтаксического анализа. Они, как правило, написаны, в правиле грамматики для нетерминального T, так как конструкторы более абстрактных синтаксических деревьев, полученных путем анализа вспомогательных фраз T. Если
T = '(' A ';' B ')' ;
это правило грамматики, А. Н. АСТ конструктор для Т может быть
T(A,B)
, предполагающий конструкцию узла Т с детьми, являющимися АСТ, построенными для подпараметров А и В.
Семантические правила - это ограничения, с которыми программа должна соответствовать закону, за исключением простого синтаксиса. Таким образом, можно построить абстрактное синтаксическое дерево (из «правил»); это только демонстрирует, что программа синтаксически корректна. Но абстрактный синтаксис может говорить вещи, которые просто бессмысленны семантически, например,
"declare s as function; ... s=7; ..."
Единственный способ проверить это вообще ходить по абстрактного синтаксического дерева, собирая факты локально (например, «s является функцией «это факт, извлеченный из инструкции declare,« s присваивается целое число », полученное из назначения) и распространяя эти факты до тех пор, пока они не совпадут и не будут показаны (совместимы).
Чтобы ответить на ваш второй вопрос, вот статья, которая связывает понятия грамматики и дерева синтаксиса и рассматривает некоторые алгоритмы синтаксического анализа.
http://www.cs.purdue.edu/homes/xyzhang/spring11/notes/ast.pdf
Из статьи:
The resulting grammar is called the concrete grammar.
The corresponding derivation tree is called the parse tree.
бетона синтаксического дерева или дерева разбора этого дерево, которое представляет собой синтаксическую структуру строки в соответствии с некоторой формальной грамматикой.
Вот ссылка на примере вывод дерева разбора из грамматики:
http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html
, который также выдвигает на первом план проблемы борьбы с неоднозначными грамматиками.