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

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

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

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

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

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

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

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

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

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

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

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

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

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

A() : Node
    Node res = Node("A")
    switch (curToken) : // принимаем решение в зависимости от текущего токена строки
        case $\mathrm{FIRST}(\alpha_1) \setminus \varepsilon$ :
            // $\alpha_1 = X_1X_2 \ldots X_{t}$ 
            for i = 1 .. t
                if $X_i$ — терминал
                    consume($X_i$)
                    res.addChild(Node($X_i$))
                else // $X_i$ — нетерминал, нужно вызвать соответствующую ему функцию рекурсивного парсера 
                    Node t = $X_i()$
                    res.addChild(t)
            break
        case $\mathrm{FIRST}(\alpha_2) \setminus \varepsilon$ : 
            $\ldots$
            break
        $\ldots$
        case $\mathrm{FIRST}(\alpha_k) \setminus \varepsilon$ : 
            $\ldots$
            break
        case $\mathrm{FOLLOW}(A)\ \mathrm{if}\ \exists i : \varepsilon \in \mathrm{FIRST}(\alpha_i)$
            res.addChild(Node($\varepsilon$)) // в этом случае нетерминал раскрывается в $\varepsilon$; можно не добавлять детей к $\mathtt{res}$,  
            break                 // подразумевая, что если у нетерминала $0$ детей, то было использовано $\varepsilon$-правило
        default :
            error("unexpected char")
    return res

function consume(c: char) 
    if curToken != c
        error("Expected $c but found$curToken")
    nextToken()

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

Пример

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

$E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to * FT' \mid \varepsilon \\ F \to n \mid (E)$

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

Правило	FIRST	FOLLOW
$E$	$\{\ n,\ (\ \}$	$\{\ \$,\ )\ \}$
$E'$	$\{\ +,\ \varepsilon\ \}$	$\{\ \$,\ )\ \}$
$T$	$\{\ n,\ (\ \}$	$\{\ +,\ \$\ ,\ )\ \}$
$T'$	$\{\ *,\ \varepsilon\ \}$	$\{\ +,\ \$\ ,\ )\ \}$
$F$	$\{\ n,\ (\ \}$	$\{\ *, \ +,\ \$\ ,\ )\ \}$

Псевдокоды

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

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)) // $\mathtt{curToken}$ подпадает под шаблон $n$, поэтому запишем его в $\mathtt{value}$ вершины
            break
        case '(' :
            consume('(')
            res.addChild(Node("("))
            res.addChild(E())
            consume(')')
            res.addChild(Node(")"))
        default :
            error("unexpected char")
    return res

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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,\ \mathtt{curToken}]\ ==\ \mathrm{ok}[/math] // [math] A\ ==\ \perp [/math] и [math]\mathtt{curToken}\ ==\ \$[/math]
            break // разбор строки завершён
        else if [math]\mathcal{M}[A,\ \mathtt{curToken}]\ ==\ \nearrow[/math] // выброс
            nextToken()
            st.pop()
            вывести в выходной поток терминал, отвечающий [math]\mathtt{curToken}[/math]
        else if [math]\mathcal{M}[A,\ \mathtt{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")

Пример

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

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

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

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

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

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

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