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

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

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

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

Для каждого нетерминала создадим функцию , возвращающую фрагмент дерева разбора, выведенный из нетерминала [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) \setminus \varepsilon[/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) \setminus \varepsilon[/math] : 
            [math]\ldots[/math]
            break
        [math]\ldots[/math]
        case [math]\mathrm{FIRST}(\alpha_k) \setminus \varepsilon[/math] : 
            [math]\ldots[/math]
            break
        case [math]\mathrm{FOLLOW}(A)\ \mathrm{if}\ \exists i : \varepsilon \in \mathrm{FIRST}(\alpha_i)[/math]
            res.addChild(Node([math]\varepsilon[/math])) // в этом случае нетерминал раскрывается в [math]\varepsilon[/math]; можно не добавлять детей к [math]\mathtt{res}[/math],  
            break                 // подразумевая, что если у нетерминала [math]0[/math] детей, то было использовано [math]\varepsilon[/math]-правило
        default :
            error("unexpected char")
    return res

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

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

Пример

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

Напомним, что множества [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]([/math], то будет использовано первое правило разбора [math]TE'[/math]. Поэтому к вершине с меткой [math]E[/math] добавятся два ребёнка: [math]T[/math] и [math]E'[/math], а рекурсивный разборщик перейдёт к нетерминалу [math]T[/math]. [math]\mathrm{curToken}[/math] по-прежнему равен [math]([/math], поэтому в [math]F[/math] сработает второй [math]\mathrm{case}[/math], первым ребёнком добавится [math]([/math], [math]\mathrm{curToken}[/math] станет равен [math]1[/math], а разборщик перейдёт к нетерминалу [math]E[/math]. После того как выражение после [math]([/math], которое выводится из [math]E[/math], будет полностью разобрано, функция рекурсивного разбора для [math]F[/math] добавит [math])[/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], а затем принимает решение в зависимости от одного из возникающих ниже случаев:

если , то синтаксический анализатор прекращает работу, так как разбор строки завершён,
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]\mathcal{M}[A,c][/math] содержит номер [math]i[/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,\ \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")

Пример

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

Номер	Правило
[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.

[1] ANTLR — Parser generator

[2] Bison — GNU Project

[3] Lex & Yacc — A Lexical Analyzer Generator and Yet Another Compiler-Compiler

[4] Happy — The Parser Generator for Haskell

[1]

[2]

[3]

[4]

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

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

Пример

Псевдокоды

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

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

Псевдокод

Пример

Примечания

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты