Семантические правила / Правила абстрактного синтаксического дерева

Question

Прежде всего, совпадают ли семантические правила и правила абстрактного синтаксического дерева?

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

Answer 1

Правила «Абстрактного синтаксического дерева» (это странная терминология) могут интерпретироваться как те правила, которые формируют построение абстрактного синтаксиса в процессе синтаксического анализа.Они обычно записываются в грамматическом правиле для нетерминального T как конструкторы над абстрактными синтаксическими деревьями, создаваемыми путем синтаксического анализа вспомогательных фраз T. Если

 T = '(' A ';' B ')' ;

является правилом грамматики, конструктор AST для T можетbe

   T(A,B)

, подразумевающее построение узла T, дочерними элементами которого являются AST, построенные для подпунктов A и B.

Семантические правила - это ограничения, которым должна соответствовать программа, чтобы быть законной, помимопростой синтаксис.Таким образом, можно построить абстрактное синтаксическое дерево (из «правил»);это только демонстрирует, что программа синтаксически верна.Но абстрактный синтаксис может говорить вещи, которые просто бессмысленно семантически, например,

  "declare s as function; ...  s=7; ..."

Единственный способ проверить это в целом - это пройтись по абстрактному синтаксическому дереву, собирая факты локально (например, "sфункция "- это факт, извлеченный из оператора объявления;" s назначено целое число "(извлекается из присваивания) и распространяющий эти факты до тех пор, пока они не встретятся и не будут показаны (не) совместимыми.

Answer 2

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

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.

A конкретное синтаксическое дерево или дерево разбора - это дерево, которое представляет синтаксическую структуру строки в соответствии с некоторой формальной грамматикой.

Вот ссылка на пример получения дерева синтаксического анализа из грамматики:

http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html

, что также подчеркивает проблему работы с неоднозначными грамматиками.