Изменения
Нет описания правки
{{В разработке}}
== Общая схема построения парсеров с помощью 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>\Gamma</tex> {{---}} LL(1)-грамматика. Построим для нее парсер.
Для каждого нетерминала A : <tex>A \rightarrow \alpha_1 | \alpha_2 | ... | \alpha_k </tex> создадим функцию A() : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала A.
Здесь Node {{---}} структура вида:
Node
children : list<Node>
value : string
Тут картинка про строку.
A() : Node
res = Node("A")
switch (curToken) :
case : FIRST(\alpha_1) :
// \alpha_1 = X_1x_2..x_{t_1}
// X_1 {{---}} нетерминал
Node t = X_1()
res.addChild(t)
// x_2 {{---}} терминал
if (curToken != x_2)
error("expected x_2")
res.addChild(new Node("x_2")
nextToken()
// x_3
...
break;
case FIRST(\alpha_2) :
// \varepsilon \in FIRST(\alpha_2)
case FOLLOW(A) :
...
break;
...
default :
error("unexpected char")
return res
{{TODO | t = Примеры псевдокодов для грамматики арифметических выражений}}
{{TODO | t = Картинки примеров разбора чего-нибудь типа 1+2*3}}
{{TODO | t = Построение таблицы предиктивного анализа}}
