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

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

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

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

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

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

Здесь Node — структура вида:

Node
    children : list<Node>
    value : string // имя нетерминала или текст терминала
    addChild(Node) // функция, подвешивающая поддерево к данному узлу

Токен — один или несколько нетерминалов, для удобства объединяемые по смыслу в одну логическую единицу.

curToken — текущий токен строки.

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

A() : Node
    res = Node("A")
    switch (curToken) :
         case [math]FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)[/math] :
            // [math]\alpha_1 = x_1x_2..x_{t_1}[/math]
            for [math]x_1 .. x_{t_1}[/math]
                if [math]x_1[/math] is terminal
                    consume([math]x_1[/math])
                    res.addChild(new Node("[math]x_1[/math]")
                    nextToken()
                else
                    Node t = [math]X_1()[/math]
                    res.addChild(t)
            break
        case [math]FIRST(\alpha_2) \cup ((\varepsilon \in FIRST(\alpha_2))  ?  FOLLOW(A)  :  \varnothing)[/math] : 
            ...
            break
        ...
        default :
            error("unexpected char")
    return res

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

Такой парсер не только разбирает строку, но и находит ошибки в неудовлетворяющих грамматике выражениях.

Пример

Рассмотрим построение парсера на примере 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]

Построим для нее множества 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

E'()
    res = Node("E'")
    switch(curToken) 
        case '+' :
            consume('+')
            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' :
            consume('n')
            res.addChild(Node("n"))
            break
        case '(' :
            consume('(')
            res.addChild(Node("("))
            res.addChild(E())
            consume(')')
            res.addChild(Node(")"))
        default :
            error("unexpected char")
    return res

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

Дерево разбора

Рисунок 2. Дерево разбора выражения (1 + 2) * 3

Рассмотрим дерево разбора для выражения (1 + 2) * 3 и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть [math]Е[/math]. Так как первым токеном является '(', то будет использовано первое правило разбора [math]TE'[/math]. Поэтому к вершине с меткой [math]Е[/math] добавятся два ребёнка: [math]T[/math] и [math]E'[/math]. А рекурсивный разборщик перейдёт к нетерминалу [math]T[/math]По-прежнему curToken равен '(', поэтому в [math]F[/math] сработает второй case, первым ребёнком добавится '(', curToken станет равен [math]1[/math], а разборщик перейдёт к нетерминалу [math]E[/math]. После того как выражение после '(', которое выводится из [math]E[/math], будет полностью разобрано, функция рекурсивного разбора для [math]F[/math] добавит ')' последним сыном к этому нетерминалу.

Продолжая в том же духе, мы построим всё дерево разбора данного выражения.

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