Сущность синтаксического анализа. Формальные грамматики. Нисходящий разбор с возвратами

этом случае принципиально важным является ответ на вопрос, в каком окружении (контексте) может находиться такой нетерминал, точнее, какой символ находится “вслед за ним”. Множество FOLLOW(U)  содержит терминальные символы, которые могут встречаться “вслед за…” нетерминалом U во всех промежуточных цепочках, выводимых в данной ФГ. Формальный алгоритм перебора таких цепочек естественным образом рекурсивен. Просматриваются правые части всех правил и определяются все включения нетерминала U. Для каждого из них возможны варианты:

-  если нетерминал – последний в правой части (правило вида X::=….U), то множество символов, “следующих за U” включает в себя множество символов, “следующих за X”, то есть за нетерминалом левой части, рекурсивно вызывается функция для построения множества FOLLOW(X) и ее результат добавляется к текущему множеству для U;

-  если вслед за нетерминалом в правой части следует терминал, то он просто добавляется в множество;

-  если вслед за нетерминалом в правой части следует терминал, то для него определяется множество FIRST, котороедобавляется к текущему множеству для U.

С большой долей успеха можно неформально определять множество FOLLOW, учитывая, что повторяющиеся последовательности, завершаемые аннулирующими нетерминалами, как правило, включены в определенные контексты (окружения терминальных символов), которые являются естественными (контекстными) ограничителями этих цепочек. Рассмотрим это на примере ФГ арифметических выражений.

O ::= E;

E ::= TM

M ::= e | +TM | -TM 

T ::= FG

G ::= e | *FG    | /FG

F ::= a | (E)

Нетерминал M в левой части аннулирующего правила используется для завершения цепочки операций сложения и вычитания, выводимой из E. Само же выражение встречается всего в двух контекстах: как выражение в скобках и как выражение, ограниченное символом “точка с запятой”. Эти два символа и составляют множество FOLLOW.

E → T+T-TM → T+T-T (в контексте “E;” и “(E)” )

FOLLOW(M)={ ),; }

Несколько сложнее обстоит дело с нетерминалом G, ограничивающем цепочку операций умножения и деления. Поскольку он используется для завершения цепочек, выводимых из T, а этот нетерминал встречается в уже рассмотренной выше цепочке в контексте операций сложения/вычитания, то операции +,- являются контекстными ограничителями для M, наряду с уже известными:

E → T+T-T → T+F*FG-T

E → T+T-TM → T+T-FG (в контексте “E;” и “(E)” )

FOLLOW(G)={ ),;,+,- }

Встречаются варианты синтаксиса, когда повторяющийся элемент не имеет явных ограничителей, либо когда речь идет о необязательном элементе синтаксиса. Тогда ограничивающим контекстом такой цепочки является начальный символ (множество FIRST) повторяющегося фрагмента верхнего уровня. Например, если определить ФГ, в которой оператором является последовательность выражений, не имеющих явных   ограничителей, то множества FOLLOW для всех перечисленных аннулирующих нетерминалов будут содержать символы, с которых может начинаться следующий оператор.

O ::= {S}

S ::= e | OS

O ::= E | while(E)O

O → {OOOE} → {OOOTM}

O → {OOEO} → {OOTMO} → {OOTMwhile(E)O}

O → {OOEO} → {OOTMO} → {OOTMwhile(E)O}

O → {OOEE} → {OOTME} → {OOTMa}

O → {OOE{S}} → {OOTM{S}}

FOLLOW(M)={ },{,a,(,),w }

Регулярные грамматики и выражения в лексическом анализе

Регулярные грамматики так же, как и конечные автоматы (КА),  могут быть использованы для описания лексики. Причем они являются эквивалентными друг другу. Так в правиле вида   U ::=aX нетерминал в левой части можно интерпретировать как - как текущее состояние, нетерминал в правой части как состояние перехода, терминал - как распознаваемый символ. Начальное состояние КА соответствует начальному нетерминалу грамматики. Аннулирующие правила используются, если лексема не имеет явно