Изменения

{{В разработке}}Для [[LL(k)-грамматики, множества FIRST и FOLLOW | LL(1)-грамматик]] возможна автоматическая генерация парсеров, если известны множества <tex>\mathrm{FIRST }</tex> и <tex>\mathrm{FOLLOW}</tex>. Существуют общедоступные генераторы: ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref>, Bison<ref>[http://www.gnu.org/software/bison/ Bison {{---}} GNU Project]</ref>, Yacc<ref>[http://dinosaur.compilertools.net/ Lex & Yacc {{---}} A Lexical Analyzer Generator and Yet Another Compiler-Compiler]</ref>, Happy<ref>[https://www.haskell.org/happy/ Happy {{---}} The Parser Generator for Haskell]</ref>.

Для каждого нетерминала <tex>A : A \rightarrow \alpha_1 \mid \alpha_2 \mid \ldots \mid \alpha_k </tex> создадим функцию <tex> \mathtt{A}() : \mathtt{Node} </tex>, возвращающую фрагмент [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#Дерево разбора | дерева разбора]], выведенный из нетерминала <tex>A</tex>.

Каждый момент времени парсер работает с определённым '''токеном''' (англ. ''token'') входного слово слова <tex>s</tex>. Токен {{---}} один или несколько нетерминаловтерминалов, для удобства объединяемые по смыслу в одну логическую единицы. Примерами токенов могут выступать следующие лексические единицы:

'''case''' <tex>\mathrm{FIRST}(\alpha_1) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ setminus \varepsilon \in \mathrm{FIRST}(\alpha_1))</tex> :

'''if''' <tex> X_i </tex> {{---}} нетерминалтерминал

res.addChild(Node("<tex>X_i</tex>") nextToken() '''else''' <font color="green">// <tex>X_i</tex> {{---}} терминалнетерминал, нужно вызвать соответствующую ему функцию рекурсивного парсера </font>

'''case''' <tex>\mathrm{FIRST}(\alpha_2) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ setminus \varepsilon \in \mathrm{FIRST}(\alpha_2))</tex> : ...<tex>\ldots</tex>

<tex>\ldots</tex> '''case''' <tex>\mathrm{FIRST}(\alpha_k) \setminus \varepsilon</tex> : <tex>\ldots</tex> '''break''' '''case''' <tex>\mathrm{FOLLOW}(A)\ \mathrm{if}\ \exists i : \varepsilon \in \mathrm{FIRST}(\alpha_i)</tex> res...addChild(Node(<tex>\varepsilon</tex>)) <font color="green">// в этом случае нетерминал раскрывается в <tex>\varepsilon</tex>; можно не добавлять детей к <tex>\mathtt{res}</tex>,</font> '''break''' <font color="green">// подразумевая, что если у нетерминала <tex>0</tex> детей, то было использовано <tex>\varepsilon</tex>-правило</font>

<font color="red">error</font>("expected Expected $c but found $curToken" + c)

Рассмотрим дерево разбора для выражения <tex>(1 + 2) * 3</tex> и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть <tex>E</tex>. Так как первым токеном является '<tex>('</tex>, то будет использовано первое правило разбора <tex>TE'</tex>. Поэтому к вершине с меткой <tex>E</tex> добавятся два ребёнка: <tex>T</tex> и <tex>E'</tex>. А , а рекурсивный разборщик перейдёт к нетерминалу <tex>T</tex>. По<tex>\mathrm{curToken}</tex> по-прежнему curToken равен '<tex>('</tex>, поэтому в <tex>F</tex> сработает второй <tex>\mathrm{case}</tex>, первым ребёнком добавится '<tex>('</tex>, <tex>\mathrm{curToken }</tex> станет равен <tex>1</tex>, а разборщик перейдёт к нетерминалу <tex>E</tex>. После того как выражение после '<tex>('</tex>, которое выводится из <tex>E</tex>, будет полностью разобрано, функция рекурсивного разбора для <tex>F</tex> добавит '<tex>)' </tex> последним сыном к этому нетерминалу.

Рекурсивные разборщики можно генерировать автоматически, зная множества <tex>\mathrm{FIRST }</tex> и <tex>\mathrm{FOLLOW}</tex>, так как они имеют достаточно прозрачный шаблон построения. Альтернативным способом осуществления нисходящего синтаксического анализа является построение нерекурсивного нисходящего парсера. Его можно построить с помощью явного использования [[Стек | стека ]] (вместо неявного при рекурсивных вызовах). Такое Такой анализатор имитирует [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#Лево- и правосторонний вывод слова | левое порождение]].  Стек нерекурсивного предиктивного синтаксического анализатора содержит последовательность терминалов и нетерминалов и таблицу синтаксического анализа. На стеке располагается последовательность символов грамматики с маркером конца разбора <tex>\perp</tex> на дне. В начале процесса анализа строки стек содержит стартовый нетерминал грамматики непосредственно над символом <tex>\perp</tex>. Таблица синтаксического анализа представляет собой двухмерный массив <tex>\mathcal{M}[A, c]</tex>, где <tex>A</tex> {{---}} нетерминал или <tex>\perp</tex>, <tex> c </tex> {{---}} токен или символ конца строки <tex>\$</tex>.

Нерекурсивный предиктивный синтаксический анализатор содержит дополнительно стексмотрит на текущий токен <tex> c </tex> входного слова и на символ на вершине стека <tex>A</tex>, а затем принимает решение в зависимости от одного из возникающих ниже случаев:* если <tex>A\ =\ \perp\ \land\ c\ =\ \$</tex>, то синтаксический анализатор прекращает работу, так как разбор строки завершён (на картинке это соответствует <tex>\mathrm{ok}</tex>),* eсли <tex>A = c</tex>, содержащий последовательность терминалов то синтаксический анализатор снимает со стека токен <tex>A</tex> и нетерминаловперемещает указатель текущего токена ленты к следующему токену (то есть вызывает <tex>\mathtt{nextToken}</tex>), таким образом, происходит выброс символа <tex> c </tex> со стека (на картинке данная ситуация соответствует символу <tex>\nearrow</tex>),* eсли <tex>A</tex> является нетерминалом, то программа рассматривает запись <tex>\mathcal{M}[A, и таблицу синтаксического анализаc]</tex> таблицы разбора <tex>\mathcal{M}</tex>. На стеке располагается последовательность символов Эта запись представляет собой либо правило грамматики с маркером конца строки $ на дне. В начале процесса анализа строки стек вида <tex>A \to \alpha_i,\ \alpha_i = X_1 X_2 \ldots X_t</tex>, и тогда <tex>\mathcal{M}[A,c]</tex> содержит стартовый нетерминал грамматики непосредственно над символом $номер <tex>i</tex> данного правила, либо запись об ошибке, и тогда <tex>\mathcal{M}[A,c] = \varnothing</tex>. Таблица синтаксического анализа представляет собой двухмерный массив МЕсли <tex>\mathcal{M}[XA, аc]\neq \varnothing</tex>, где X — то синтаксический анализатор замещает на стеке нетерминал<tex> A </tex> правой частью правила с номером <tex> i </tex>, помещая символы правила на стек в обратном порядке, а — терминал или символ $* во всех остальных случаях парсер выдаёт сообщение об ошибке.

Нерекурсивный синтаксический анализатор смотрит Рассмотренные случаи отображены на текущий токен строки a и на символ на вершине стека X, а затем принимает решение в зависимости от одного из возникающих ниже случаев:* если Х=curToken=$, синтаксический анализатор прекращает работу, так как разбор строки завершён,* eсли Х=curToken≠$, синтаксический анализатор снимает со стека X и перемещает указатель входного потока к следующему токену (то есть вызывает nextToken),* eсли X представляет собой нетерминалкартинке справа, программа рассматривает запись M[Х,а] таблицы разбора М. Эта запись представляет собой либо X-продукцию где блок <tex> N </tex> отвечает нетерминалам грамматики, либо запись об ошибке. ЕслиИз картинки видно, например, М[Х,а] = что вместо рассмотрения всех случаев в коде достаточно просто создать таблицу <tex>\mathcal{X → UVWM}</tex> таким образом, синтаксический анализатор замещает X на вершине стека на WVU (с U на вершине стека). В кач-ве выхода синтаксический анализатор просто выводит использованную продукцию. Если M[Х,а] = errorчтобы она учитывала все случаи, синтаксический анализатор вызывает программу восстановления после ошибкичто упростит код.

'''function ''' nonRecursiveParser(w : String): s st : '''Stack''' sst.push(bottom<tex>\perp</tex>) sst.push(Start<tex>S</tex>)<font color="green">// здесь <tex> S </tex> {{---}} стартовый нетерминал грамматики</font> do X = '''while''' s.top()<tex>\neq\ \perp</tex> if X == c c A = nextToken() sst.poptop() else '''if X in Sigma''' <tex>\mathcal{M}[A,\ \mathtt{curToken}]\ ==\ \mathrm{ok}</tex> <font color="green">// <tex> A\ ==\ \perp </tex> и <tex>\mathtt{curToken}\ ==\ \$</tex></font> error('''break''' <font color="unexpected symbolgreen")>// разбор строки завершён</font> '''else if ''' <tex>\mathcal{M}[XA, c\ \mathtt{curToken}] \ == undefined \ \nearrow</tex> <font color="green">// запись об ошибкевыброс</font> nextToken() errorst.pop("unexpected symbol") вывести в выходной поток терминал, отвечающий <tex>\mathtt{curToken}</tex> '''else if ''' <tex>\mathcal{M}[XA, c\ \mathtt{curToken}] </tex> {{---}} номер правила <tex>A \to \alpha_i,\ \alpha_i == X -X_1 X_2 \ldots X_t</tex> Y_1 Y_2 ... Y_k sst.pop() '''for i ''' k = k t '''downto ''' 1 sst.push(Y_i<tex>X_k</tex>) вывести в выходной поток нетерминал, отвечающий <tex>A</tex> while s.top '''else''' <font color="red">error</font>("unexpected symbol") != bottom

Рассмотрим пример работы нерекурсивного парсера на всё той же грамматике арифметических выражений. Для начала пронумеруем все правила: {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Номер!style="background-color:#EEE"| Правило|-|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>1</tex> (1) \ |style="background-color:#FFF;padding:2px 10px"| <tex>E \to TE' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>2) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to +TE' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>3) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to \varepsilon \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>4) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T \to FT' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>5) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to \times * FT' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to \varepsilon \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>7) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>F \to n \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>8) \ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>F \to (E)</tex>|} Теперь можно построить часть таблицы <tex>\mathcal{M}</tex>, содержащей отвечающие нетерминалам строки. Её построение легко осуществить, если известны <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>. По этим множествам можно понять, какое правило использовать для данного нетерминала при текущем токене.

!style="background-color:#EEE;text-align:center;"| <tex>n</tex>!style="background-color:#EEE;text-align:center;"| <tex>(</tex>!style="background-color:#EEE;text-align:center;"| <tex>)</tex>!style="background-color:#EEE;text-align:center;"| <tex>+</tex>!style="background-color:#EEE;text-align:center;"| <tex>*</tex>!style="background-color:#EEE;text-align:center;"| <tex>\$</tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>E</tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>1 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>1 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>E'</tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>3 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>2 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>3 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>T</tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>4 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>4 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>T'</tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>6 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>6 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>5 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>6 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>F</tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>7 </tex>|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>8 </tex>

|style="background-color:#FFF;padding:2px 30px;text-align:center;"| <tex>\perp</tex>|style="background-color:#FFF;padding:2px 30px"|