Предиктивный синтаксический анализ — различия между версиями
Shersh (обсуждение | вклад) (Новая страница: «{{В разработке}} {{TODO | t = Общая схема для построения парсеров с помощью FIRST и FOLLOW}} {{TODO | t = Пр...») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| + | == Общая схема построения парсеров с помощью 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 = Примеры псевдокодов для грамматики арифметических выражений}} | ||
{{TODO | t = Картинки примеров разбора чего-нибудь типа 1+2*3}} | {{TODO | t = Картинки примеров разбора чего-нибудь типа 1+2*3}} | ||
{{TODO | t = Построение таблицы предиктивного анализа}} | {{TODO | t = Построение таблицы предиктивного анализа}} | ||
Версия 15:13, 24 мая 2015
Эта статья находится в разработке!
Общая схема построения парсеров с помощью FIRST и FOLLOW
Для LL(1) грамматик возможна автоматическая генерация парсеров, если известны множества FIRST и FOLLOW. Существуют общедоступные генераторы: ANTLR, GNU bison, Yacc.
Пусть — LL(1)-грамматика. Построим для нее парсер.
Для каждого нетерминала A : создадим функцию 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: Примеры псевдокодов для грамматики арифметических выражений
TODO: Картинки примеров разбора чего-нибудь типа 1+2*3
TODO: Построение таблицы предиктивного анализа
