Предиктивный синтаксический анализ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общая схема построения рекурсивных парсеров с помощью FIRST и FOLLOW)
Строка 4: Строка 4:
 
== Общая схема построения рекурсивных парсеров с помощью FIRST и FOLLOW ==
 
== Общая схема построения рекурсивных парсеров с помощью FIRST и FOLLOW ==
  
Пусть <tex>\Gamma</tex> {{---}} LL(1)-грамматика. Построим для нее парсер.
+
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} LL(1)-грамматика. Построим для нее парсер.
  
Для каждого нетерминала <tex>A</tex> : <tex>A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_k </tex> создадим функцию A() : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала <tex>A</tex>.
+
Для каждого нетерминала <tex>A : A \rightarrow \alpha_1 \mid \alpha_2 \mid \ldots \mid \alpha_k </tex> создадим функцию <tex> \mathtt{A}() : \mathtt{Node} </tex>, возвращающую фрагмент дерева разбора, выведенный из нетерминала <tex>A</tex>.
  
Здесь Node {{---}} структура вида:
+
Здесь <tex>\mathtt{Node}</tex> {{---}} структура следующего вида:
  Node
+
  '''struct''' Node
     children : list<Node>
+
     children : '''list<Node>'''
     value : string // имя нетерминала или текст терминала
+
     value : '''string'''          <font color="green">// имя нетерминала или текст терминала</font>
     addChild(Node) // функция, подвешивающая поддерево к данному узлу
+
     '''function''' addChild('''Node''') <font color="green">// функция, подвешивающая поддерево к данному узлу</font>
  
 +
Каждый момент времени парсер работает с определённым '''токеном''' (англ. ''token'') входного слово <tex>s</tex>. Токен {{---}} один или несколько нетерминалов, для удобства объединяемые по смыслу в одну логическую единицы. Примерами токенов могут выступать следующие лексические единицы:
 +
* произвольный символ <tex> c </tex>,
 +
* целое слово, например <tex> public </tex>,
 +
* число со знаком, обозначаемое далее для краткости как <tex> n </tex>,
 +
В общем случае, токеном может являться любое слово, удовлетворяющее произвольному [[Регулярные языки: два определения и их эквивалентность | регулярному выражению]].
  
 
[[Файл:string_token.png|300px]]
 
[[Файл:string_token.png|300px]]
  
Токен {{---}} один или несколько нетерминалов, для удобства объединяемые по смыслу в одну логическую единицу.
+
В псевдокоде используются следующие обозначения:
 +
* <tex>\mathtt{curToken}</tex> {{---}} текущий токен строки,
 +
* <tex>\mathtt{nextToken()}</tex> {{---}} функция, записывающая в <tex>\mathtt{curToken}</tex> следующий за ним токен.
  
curToken {{---}} текущий токен строки.
+
Тогда шаблон функции рекурсивного парсера для нетерминала <tex>A</tex> имеет вид:
  
nextToken() {{---}} записывает в curToken следующий за ним токен.
+
  A() : '''Node'''
 
+
     Node res = Node("A")
 
+
     '''switch''' (curToken) : <font color="green">// принимаем решение в зависимости от текущего токена строки</font>
  A() : Node
+
        '''case''' <tex>\mathrm{FIRST}(\alpha_1) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_1))</tex> :
     res = Node("A")
+
            <font color="green">// <tex>\alpha_1 = X_1X_2 \ldots X_{t}</tex> </font>
     switch (curToken) :
+
            '''for''' i = 1 .. t
          case <tex>FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)</tex> :
+
                '''if''' <tex> X_i </tex> {{---}} нетерминал
            // <tex>\alpha_1 = x_1x_2..x_{t_1}</tex>
+
                    consume(<tex>X_i</tex>)
            for <tex>x_1 .. x_{t_1}</tex>
+
                    res.addChild(Node("<tex>X_i</tex>")
                if <tex>x_1</tex> is terminal
+
                    nextToken()
                    consume(<tex>x_1</tex>)
+
                '''else''' <font color="green">// <tex>X_i</tex> {{---}} терминал, нужно вызвать  </font>
                    res.addChild(new Node("<tex>x_1</tex>")
+
                    Node t = <tex>X_i()</tex>
                    nextToken()
+
                    res.addChild(t)
                else
+
             '''break'''
                    Node t = <tex>X_1()</tex>
+
         '''case''' <tex>\mathrm{FIRST}(\alpha_2) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_2))</tex> :  
                    res.addChild(t)
 
             break
 
         case <tex>FIRST(\alpha_2) \cup ((\varepsilon \in FIRST(\alpha_2))  ?  FOLLOW(A)  :  \varnothing)</tex> :  
 
 
             ...
 
             ...
             break
+
             '''break'''
 
         ...
 
         ...
         default :
+
         '''default''' :
             error("unexpected char")
+
             <font color="red">error</font>("unexpected char")
     return res
+
     '''return''' res
  
  consume(char c)  
+
  '''function''' consume(c: '''char''')  
     if (curToken != c)
+
     '''if''' curToken != c
         error("expected" + c)
+
         <font color="red">error</font>("expected " + c)
 
     nextToken()
 
     nextToken()
  

Версия 13:40, 25 мая 2015

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

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

Общая схема построения рекурсивных парсеров с помощью 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],

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

String token.png

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

  • [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]")
                   nextToken()
               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] : 
            ...
            break
        ...
        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 \times FT' \mid \varepsilon \\ F \to n \mid (E) [/math]

Построим для нее множества [math]FIRST[/math] и [math]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]\{\ \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] строятся аналогично.

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

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

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

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

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

Parse table.png

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

Нерекурсивный предиктивный синтаксический анализатор содержит дополнительно стек, содержащий последовательность терминалов и нетерминалов, и таблицу синтаксического анализа. На стеке располагается последовательность символов грамматики с маркером конца строки $ на дне. В начале процесса анализа строки стек содержит стартовый нетерминал грамматики непосредственно над символом $. Таблица синтаксического анализа представляет собой двухмерный массив М[X, а], где X — нетерминал, а — терминал или символ $.

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

  • если Х=curToken=$, синтаксический анализатор прекращает работу, так как разбор строки завершён,
  • eсли Х=curToken≠$, синтаксический анализатор снимает со стека X и перемещает указатель входного потока к следующему токену (то есть вызывает nextToken),
  • eсли X представляет собой нетерминал, программа рассматривает запись M[Х,а] таблицы разбора М. Эта запись представляет собой либо X-продукцию грамматики, либо запись об ошибке. Если, например, М[Х,а] = {X → UVW}, синтаксический анализатор замещает X на вершине стека на WVU (с U на вершине стека). В кач-ве выхода синтаксический анализатор просто выводит использованную продукцию. Если M[Х,а] = error, синтаксический анализатор вызывает программу восстановления после ошибки.

Псевдокод

function nonRecursiveParser(w : String):
    s : Stack
    s.push(bottom)
    s.push(Start)
    do 
        X = s.top()
        if X == c
            c = nextToken()
            s.pop()
        else if X in Sigma
            error("unexpected symbol")
        else if M[X, c] == undefined // запись об ошибке
            error("unexpected symbol")
        else if M[X, c] == X -> Y_1 Y_2 ... Y_k
            s.pop()
            for i = k downto 1
                s.push(Y_i)
    while s.top() != bottom

Пример

[math] (1) \ E \to TE' \\ (2) \ E' \to +TE' \\ (3) \ E' \to \varepsilon \\ (4) \ T \to FT' \\ (5) \ T' \to \times FT' \\ (6) \ T' \to \varepsilon \\ (7) \ F \to n \\ (8) \ F \to (E) [/math]

n ( ) + * $
[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]

Parse stack.png

Примечания

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

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