Изменения

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

Нерекурсивный предиктивный синтаксический анализатор Стек нерекурсивного предиктивного синтаксического анализатора содержит дополнительно стек, содержащий последовательность терминалов и нетерминалов, и таблицу синтаксического анализа. На стеке располагается последовательность символов грамматики с маркером конца строки $ разбора <tex>\perp</tex> на дне. В начале процесса анализа строки стек содержит стартовый нетерминал грамматики непосредственно над символом $<tex>\perp</tex>. Таблица синтаксического анализа представляет собой двухмерный массив М<tex>\mathcal{M}[XA, аc]</tex>, где X — <tex>A</tex> {{---}} нетерминалили <tex>\perp</tex>, а — терминал <tex> c </tex> {{---}} токен или символ конца строки <tex>\$</tex>.

Нерекурсивный синтаксический анализатор смотрит на текущий токен строки a <tex> c </tex> входного слова и на символ на вершине стека X<tex>A</tex>, а затем принимает решение в зависимости от одного из возникающих ниже случаев:* если Х<tex>A\ =curToken\ \perp\ \land\ c\ =\ \$</tex>, то синтаксический анализатор прекращает работу, так как разбор строки завершён,* eсли Х<tex>A =curToken≠$c</tex>, то синтаксический анализатор снимает со стека X токен <tex>A</tex> и перемещает указатель входного потока текущего токена ленты к следующему токену (то есть вызывает <tex>\mathtt{nextToken}</tex>), таким образом, происходит выброс символа <tex> c </tex> со стека,* eсли X <tex>A</tex> представляет собой нетерминал, то программа рассматривает запись <tex>\mathcal{M}[ХA,аc] </tex> таблицы разбора М<tex>\mathcal{M}</tex>. Эта запись представляет собой либо X-продукцию грамматикивида <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{X → UVWM}[A, c] \neq \varnothing</tex>, то синтаксический анализатор замещает X на вершине стека стеке нетерминал <tex> A </tex> правой частью правила с номером <tex> i </tex>, помещая символы правила на WVU (с U стек в обратном порядке,* во всех остальных случаях парсер бросает сообщение об ошибке. Рассмотренные случаи отображены коротко на вершине стека)картинке справа, где блок <tex> N </tex> отвечает нетерминалам грамматики. В кач-ве выхода синтаксический анализатор Из картинки видно, что вместо рассмотрения всех случаев в коде, достаточно просто выводит использованную продукцию. Если создать таблицу <tex>\mathcal{M[Х}</tex> таким образом,а] = 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,\ 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\ curToken] \ == undefined \ \nearrow</tex> <font color="green">// запись об ошибкевыброс</font> nextToken() errorst.pop("unexpected symbol") вывести в выходной поток нетерминал, отвечающий <tex>\mathtt{curToken}</tex> '''else if ''' <tex>\mathcal{M}[XA, c\ 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