Предиктивный синтаксический анализ

Эта статья находится в разработке!

Общая схема построения парсеров с помощью FIRST и FOLLOW

Для LL(1) грамматик возможна автоматическая генерация парсеров, если известны множества FIRST и FOLLOW. Существуют общедоступные генераторы: ANTLR, GNU bison, Yacc.

Пусть [math]\Gamma[/math] — LL(1)-грамматика. Построим для нее парсер.

Для каждого нетерминала A : [math]A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_k [/math] создадим функцию 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

Пример

Рассмотрим построение парсера на примере грамматики арифметических выражений. Запишем грамматику.

[math] E \to T + E \mid T \\ T \to F \times T \mid F \\ F \to n \mid (E) [/math]

Данная грамматика не является LL(1)-грамматикой, так как содержит правое ветвление, от него нужно избавиться перед построением парсера:

[math] E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to \times FT' \mid \varepsilon \\ F \to n \mid (E) [/math]

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

Правило	FIRST	FOLLOW
[math]E[/math]	[math]\{\ n,\ (\ \} [/math]	[math]\{\ \$,\ )\ \} [/math]
[math]E'[/math]	[math]\{\ +,\ \varepsilon\ \} [/math]	[math]\{\ \$,\ )\ \} [/math]
[math]T[/math]	[math]\{\ n,\ (\ \} [/math]	[math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]T'[/math]	[math]\{\ \times,\ \varepsilon\ \} [/math]	[math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]F[/math]	[math]\{\ n,\ (\ \} [/math]	[math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]

Построим функции обработки некоторых нетерминалов.

   E()
       res = Node("E")
       switch(curToken)
           case 'n', '(' :
               res.addChild(T())
               res.addChild(E'())
               break
           default :
               error("unexpected char")
       return res

   consume(char c) 
       if (curToken != c)
           error("expected" + c)
       nextToken()

   E'()
       res = Node("E'")
       switch(curToken) 
           case '+' :
               consume('+')
               nextToken()
               res.addChild(Node("+"))
               res.addChild(T())
               res.addChild(E'())
               break
           case '$', ')' :
               break
           default :
               error("unexpected char")
       return res

   F()
       res = Node("F")
       switch(curToken)
           case 'n' :
               if (curToken != 'n')
                   error("expected n")
               nextToken()
               res.addChild(Node("n"))
               break
           case '(' :
               consume('(')
               res.addChild(Node("("))
               res.addChild(E())
               consume(')')
               res.addChild(Node(")"))
           default :
               error("unexpected char")
       return res

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

TODO: Картинки примеров разбора чего-нибудь типа 1+2*3

TODO: Построение таблицы предиктивного анализа