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

Для LL(1)-грамматик возможна автоматическая генерация парсеров, если известны множества [math]\mathrm{FIRST}[/math] и [math]\mathrm{FOLLOW}[/math]. Существуют общедоступные генераторы: ANTLR, Bison, Yacc, Happy.

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

Пусть [math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — LL(1)-грамматика. Построим для нее парсер.

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

Здесь [math]\mathtt{Node}[/math] — структура следующего вида:

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

Каждый момент времени парсер работает с определённым токеном (англ. token) входного слова [math]s[/math]. Токен — один или несколько терминалов, объединяемые по смыслу. Примерами токенов могут выступать следующие лексические единицы:

• произвольный символ [math] c [/math],
• целое слово, например [math] public [/math],
• число со знаком, обозначаемое далее для краткости как [math] n [/math].

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

Здесь [math]\$[/math] обозначает маркер конца строки.

В псевдокоде используются следующие обозначения:

• [math]\mathtt{curToken}[/math] — текущий токен строки,
• [math]\mathtt{nextToken()}[/math] — функция, записывающая в [math]\mathtt{curToken}[/math] следующий за ним токен.

Тогда шаблон функции рекурсивного парсера для нетерминала [math]A[/math] имеет вид:

A() : Node
    Node res = Node("A")
    switch (curToken) : // принимаем решение в зависимости от текущего токена строки
        case [math]\mathrm{FIRST}(\alpha_1) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_1))[/math] :
            // [math]\alpha_1 = X_1X_2 \ldots X_{t}[/math] 
            for i = 1 .. t
                if [math] X_i [/math] — терминал
                    consume([math]X_i[/math])
                    res.addChild(Node("[math]X_i[/math]")
                else // [math]X_i[/math] — нетерминал, нужно вызвать соответствующую ему функцию рекурсивного парсера 
                    Node t = [math]X_i()[/math]
                    res.addChild(t)
            break
        case [math]\mathrm{FIRST}(\alpha_2) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_2))[/math] : 
            [math]\ldots[/math]
            break
        [math]\ldots[/math]
        default :
            error("unexpected char")
    return res

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

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

Пример

Рассмотрим построение парсера на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана ранее:

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

Напомним, что множества [math]\mathrm{FIRST}[/math] и [math]\mathrm{FOLLOW}[/math] для неё выглядят так:

Правило	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]\{\ *,\ \varepsilon\ \} [/math]	[math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]F[/math]	[math]\{\ n,\ (\ \} [/math]	[math]\{\ *, \ +,\ \$\ ,\ )\ \} [/math]

Псевдокоды

Построим функции обработки некоторых нетерминалов, используя описанный выше шаблон:

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

E'() : Node
    Node 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() : Node
    Node res = Node("F")
    switch (curToken)
        case n :
            consume(n)
            res.addChild(Node(curToken)) // [math]\mathtt{curToken}[/math] подпадает под шаблон [math]n[/math], поэтому запишем его в [math]\mathtt{value}[/math] вершины
            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] строятся аналогично.

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

Рассмотрим дерево разбора для выражения [math](1 + 2) * 3[/math] и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть [math]E[/math]. Так как первым токеном является '(', то будет использовано первое правило разбора [math]TE'[/math]. Поэтому к вершине с меткой [math]E[/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] добавит ')' последним сыном к этому нетерминалу.

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

Дерево разбора выражения [math](1 + 2) * 3[/math]

Нерекурсивный нисходящий парсер

Рекурсивные разборщики можно генерировать автоматически, зная множества [math]\mathrm{FIRST}[/math] и [math]\mathrm{FOLLOW}[/math], так как они имеют достаточно прозрачный шаблон построения. Альтернативным способом осуществления нисходящего синтаксического анализа является построение нерекурсивного нисходящего парсера. Его можно построить с помощью явного использования стека (вместо неявного при рекурсивных вызовах). Такой анализатор имитирует левое порождение.

Стек нерекурсивного предиктивного синтаксического анализатора содержит последовательность терминалов и нетерминалов и таблицу синтаксического анализа. На стеке располагается последовательность символов грамматики с маркером конца разбора [math]\perp[/math] на дне. В начале процесса анализа строки стек содержит стартовый нетерминал грамматики непосредственно над символом [math]\perp[/math]. Таблица синтаксического анализа представляет собой двухмерный массив [math]\mathcal{M}[A, c][/math], где [math]A[/math] — нетерминал или [math]\perp[/math], [math] c [/math] — токен или символ конца строки [math]\$[/math].

Нерекурсивный синтаксический анализатор смотрит на текущий токен [math] c [/math] входного слова и на символ на вершине стека [math]A[/math], а затем принимает решение в зависимости от одного из возникающих ниже случаев:

• если [math]A\ =\ \perp\ \land\ c\ =\ \$[/math], то синтаксический анализатор прекращает работу, так как разбор строки завершён,
• eсли [math]A = c[/math], то синтаксический анализатор снимает со стека токен [math]A[/math] и перемещает указатель текущего токена ленты к следующему токену (то есть вызывает [math]\mathtt{nextToken}[/math]), таким образом, происходит выброс символа [math] c [/math] со стека,
• eсли [math]A[/math] является нетерминалом, то программа рассматривает запись [math]\mathcal{M}[A,c][/math] таблицы разбора [math]\mathcal{M}[/math]. Эта запись представляет собой либо правило грамматики вида [math]A \to \alpha_i,\ \alpha_i = X_1 X_2 \ldots X_t[/math], и тогда [math]\mathcal{M}[A,c][/math] содержит номер [math]i[/math] данного правила, либо запись об ошибке, и тогда [math]\mathcal{M}[A,c] = \varnothing[/math]. Если [math]\mathcal{M}[A,c] \neq \varnothing[/math], то синтаксический анализатор замещает на стеке нетерминал [math] A [/math] правой частью правила с номером [math] i [/math], помещая символы правила на стек в обратном порядке,
• во всех остальных случаях парсер выдаёт сообщение об ошибке.

Рассмотренные случаи отображены на картинке справа, где блок [math] N [/math] отвечает нетерминалам грамматики. Из картинки видно, что вместо рассмотрения всех случаев в коде достаточно просто создать таблицу [math]\mathcal{M}[/math] таким образом, чтобы она учитывала все случаи, что упростит код.

Псевдокод

Здесь по-прежнему [math]\mathtt{curToken}[/math] обозначает текущий токен строки, а [math]\mathtt{nextToken}[/math] передвигает указатель на следующий токен.

function nonRecursiveParser():
    st : Stack
    st.push([math]\perp[/math])
    st.push([math]S[/math]) // здесь [math] S [/math] — стартовый нетерминал грамматики
    while s.top() [math]\neq\ \perp[/math] 
        A = st.top()
        if [math]\mathcal{M}[A,\ curToken]\ ==\ \mathrm{ok}[/math] // [math] A\ ==\ \perp [/math] и [math]\mathtt{curToken}\ ==\ \$[/math]
            break // разбор строки завершён
        else if [math]\mathcal{M}[A,\ curToken]\ ==\ \nearrow[/math] // выброс
            nextToken()
            st.pop()
            вывести в выходной поток нетерминал, отвечающий [math]\mathtt{curToken}[/math]
        else if [math]\mathcal{M}[A,\ curToken][/math] — номер правила [math]A \to \alpha_i,\ \alpha_i = X_1 X_2 \ldots X_t[/math]
            st.pop()
            for k = t downto 1
                st.push([math]X_k[/math])    
            вывести в выходной поток терминал, отвечающий [math]A[/math]
        else
            error("unexpected symbol")

Пример

Рассмотрим пример работы нерекурсивного парсера на всё той же грамматике арифметических выражений. Для начала пронумеруем все правила:

Номер	Правило
[math]1[/math]	[math]E \to TE'[/math]
[math]2[/math]	[math]E' \to +TE'[/math]
[math]3[/math]	[math]E' \to \varepsilon[/math]
[math]4[/math]	[math]T \to FT'[/math]
[math]5[/math]	[math]T' \to * FT'[/math]
[math]6[/math]	[math]T' \to \varepsilon[/math]
[math]7[/math]	[math]F \to n[/math]
[math]8[/math]	[math]F \to (E)[/math]

Теперь можно построить часть таблицы [math]\mathcal{M}[/math], содержащей отвечающие нетерминалам строки. Её построение легко осуществить, если известны [math]\mathrm{FIRST}[/math] и [math]\mathrm{FOLLOW}[/math]. По этим множествам можно понять, какое правило использовать для данного нетерминала при текущем токене.

	[math]n[/math]	[math]([/math]	[math])[/math]	[math]+[/math]	[math]*[/math]	[math]\$[/math]
[math]E[/math]	[math]1 [/math]	[math]1 [/math]
[math]E'[/math]			[math]3 [/math]	[math]2 [/math]		[math]3 [/math]
[math]T[/math]	[math]4 [/math]	[math]4 [/math]
[math]T'[/math]			[math]6 [/math]	[math]6 [/math]	[math]5 [/math]	[math]6 [/math]
[math]F[/math]	[math]7 [/math]	[math]8 [/math]
[math]\perp[/math]						[math]\mathrm{ok}[/math]

На картинке ниже показаны состояния стека на нескольких первых итерациях цикла и указатель на текущий токен.

Источники информации

• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 288 — 294.