Изменения
Нет описания правки
{{В разработке}}
Пусть <tex>\Gamma</tex> {{---}} LL(1)-грамматика. Построим для нее парсер.
Для каждого нетерминала <tex>A </tex> : <tex>A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_k </tex> создадим функцию A() : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала <tex>A</tex>.
Здесь Node {{---}} структура вида:
Токен {{---}} один или несколько нетерминалов, для удобства объединяемые по смыслу в одну логическую единицу.
curToken {{---}} текущий токен строки.
nextToken () {{---}} записывает в curToken следующий за ним токен.
A() : Node
switch (curToken) :
case : <tex>FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1)) ? FOLLOW(A) : \varnothing)</tex> :
// <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>")
nextToken()
else
Node t = <tex>X_1()</tex>
res.addChild(t)
break
== Пример ==
Рассмотрим построение парсера на примере грамматики арифметических выражений.Запишем грамматику. <tex> E \to T + E \mid T \\T \to F \times T \mid F \\F \to n \mid (E)</tex> Данная грамматика не является LL(1)-грамматикой, так как содержит правое ветвление, от него нужно избавиться перед построением парсера:грамматики арифметических выражений.
<tex>
</tex>
{| style="background-color:#CCC;margin:0.5px"
return res
Функции для <tex>T </tex> и <tex>T' </tex> строятся аналогично.
{{TODO | t = Картинки примеров разбора чего-нибудь типа 1+2*3}}
{{TODO | t = Построение таблицы предиктивного анализа}}
