Изменения

== Общая схема построения парсеров с помощью FIRST и FOLLOW ==Для LL(1) -грамматик возможна автоматическая генерация парсеров, если известны множества FIRST и FOLLOW. Существуют общедоступные генераторы: [http://en.wikipedia.org/wiki/ANTLR ANTLR], [http://en.wikipedia.org/wiki/GNU_bison GNU bison], [http://en.wikipedia.org/wiki/Yacc Yacc]. == Общая схема построения парсеров с помощью <tex>FIRST</tex> и <tex>FOLLOW</tex> ==

Для каждого нетерминала <tex>A </tex> : <tex>A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_k </tex> создадим функцию A() : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала <tex>A</tex>.

nextToken () {{---}} записывает в curToken следующий за ним токен.

// <tex>\alpha_1 = x_1x_2..x_{t_1}</tex> for <tex>x_1 .. x_{t_1}</tex> if <tex>x_1 </tex> is terminal consume(<tex>x_1</tex>) res.addChild(new Node("<tex>x_1</tex>")

Node t = <tex>X_1()</tex>

Рассмотрим построение парсера на примере грамматики арифметических выражений.Запишем грамматику. <tex> E \to T + E \mid T \\T \to F \times T \mid F \\F \to n \mid (E)</tex> Данная грамматика не является LL(1)-грамматикой, так как содержит правое ветвление, от него нужно избавиться перед построением парсера:грамматики арифметических выражений.

Теперь грамматика стала LL(1)-грамматикой, построим Построим для нее множества FIRST и FOLLOW (их построение подробно разобрано [[Построение FIRST и FOLLOW#Пример | здесь]]).

Функции для <tex>T </tex> и <tex>T' </tex> строятся аналогично.