Изменения

Для [[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>.

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

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

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

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

Рассмотренные случаи отображены коротко на картинке справа, где блок <tex> N </tex> отвечает нетерминалам грамматики. Из картинки видно, что вместо рассмотрения всех случаев в коде, достаточно просто создать таблицу <tex>\mathcal{M}</tex> таким образом, чтобы она учитывала все случаи, что упростит код.

Теперь можно построить часть таблицы <tex>\mathcal{M}</tex>, содержащей строки, отвечающие нетерминаламстроки. Её построение легко осуществить, если известны <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>. По сути по этим множествам можно понять, какое правило использовать для данного нетерминала при текущем токене.

На картинке ниже показаны состояние состояния стека на нескольких первых итерациях цикла и указатель на текущий токен.