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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 7 участников)
Строка 1: Строка 1:
{{В разработке}}
+
Для [[LL(k)-грамматики, множества FIRST и FOLLOW | LL(1)-грамматик]] возможна автоматическая генерация парсеров, если известны множества <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>. Существуют общедоступные генераторы: ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref>, Bison<ref>[http://www.gnu.org/software/bison/ Bison {{---}} GNU Project]</ref>, Yacc<ref>[http://dinosaur.compilertools.net/ Lex & Yacc {{---}} A Lexical Analyzer Generator and Yet Another Compiler-Compiler]</ref>, Happy<ref>[https://www.haskell.org/happy/ Happy {{---}} The Parser Generator for Haskell]</ref>.
Для LL(1)-грамматик возможна автоматическая генерация парсеров, если известны множества FIRST и FOLLOW. Существуют общедоступные генераторы: [http://en.wikipedia.org/wiki/ANTLR ANTLR], [http://en.wikipedia.org/wiki/GNU_bison GNU bison], [http://en.wikipedia.org/wiki/Yacc Yacc].
 
  
== Общая схема построения парсеров с помощью <tex>FIRST</tex> и <tex>FOLLOW</tex> ==
+
== Общая схема построения рекурсивных парсеров с помощью 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>\$</tex> обозначает маркер конца строки.
  
curToken {{---}} текущий токен строки.
+
В псевдокоде используются следующие обозначения:
 +
* <tex>\mathtt{curToken}</tex> {{---}} текущий токен строки,
 +
* <tex>\mathtt{nextToken()}</tex> {{---}} функция, записывающая в <tex>\mathtt{curToken}</tex> следующий за ним токен.
  
nextToken() {{---}} записывает в curToken следующий за ним токен.
+
Тогда шаблон функции рекурсивного парсера для нетерминала <tex>A</tex> имеет вид:
  
 
+
  A() : '''Node'''
  A() : Node
+
     Node res = Node("A")
     res = Node("A")
+
     '''switch''' (curToken) : <font color="green">// принимаем решение в зависимости от текущего токена строки</font>
     switch (curToken) :
+
        '''case''' <tex>\mathrm{FIRST}(\alpha_1) \setminus \varepsilon</tex> :
          case <tex>FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)</tex> :
+
             <font color="green">// <tex>\alpha_1 = X_1X_2 \ldots X_{t}</tex> </font>
             // <tex>\alpha_1 = x_1x_2..x_{t_1}</tex>
+
             '''for''' i = 1 .. t
             for <tex>x_1 .. x_{t_1}</tex>
+
                 '''if''' <tex> X_i </tex> {{---}} терминал
                 if <tex>x_1</tex> is terminal
+
                     consume(<tex>X_i</tex>)
                     consume(<tex>x_1</tex>)
+
                     res.addChild(Node(<tex>X_i</tex>))
                     res.addChild(new Node("<tex>x_1</tex>")
+
                 '''else''' <font color="green">// <tex>X_i</tex> {{---}} нетерминал, нужно вызвать соответствующую ему функцию рекурсивного парсера </font>
                    nextToken()
+
                     Node t = <tex>X_i()</tex>
                 else
 
                     Node t = <tex>X_1()</tex>
 
 
                     res.addChild(t)
 
                     res.addChild(t)
             break
+
             '''break'''
         case <tex>FIRST(\alpha_2) \cup ((\varepsilon \in FIRST(\alpha_2))  ?  FOLLOW(A) : \varnothing)</tex> :
+
         '''case''' <tex>\mathrm{FIRST}(\alpha_2) \setminus \varepsilon</tex> :
             ...
+
            <tex>\ldots</tex>
             break
+
            '''break'''
         ...
+
        <tex>\ldots</tex>
        default :
+
        '''case''' <tex>\mathrm{FIRST}(\alpha_k) \setminus \varepsilon</tex> :
             error("unexpected char")
+
            <tex>\ldots</tex>
     return res
+
            '''break'''
 +
        '''case''' <tex>\mathrm{FOLLOW}(A)\ \mathrm{if}\ \exists i : \varepsilon \in \mathrm{FIRST}(\alpha_i)</tex>
 +
             res.addChild(Node(<tex>\varepsilon</tex>)) <font color="green">// в этом случае нетерминал раскрывается в <tex>\varepsilon</tex>; можно не добавлять детей к <tex>\mathtt{res}</tex>,</font> 
 +
             '''break'''                <font color="green">// подразумевая, что если у нетерминала <tex>0</tex> детей, то было использовано <tex>\varepsilon</tex>-правило</font>
 +
         '''default''' :
 +
             <font color="red">error</font>("unexpected char")
 +
     '''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 but found $curToken")
 
     nextToken()
 
     nextToken()
  
Строка 54: Строка 64:
  
 
== Пример ==
 
== Пример ==
Рассмотрим построение парсера на примере LL(1)-грамматики арифметических выражений.
+
Рассмотрим построение парсера на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]]:
  
 
<tex>  
 
<tex>  
Строка 60: Строка 70:
 
E' \to +TE' \mid \varepsilon \\
 
E' \to +TE' \mid \varepsilon \\
 
T \to FT' \\
 
T \to FT' \\
T' \to \times FT' \mid \varepsilon \\
+
T' \to * FT' \mid \varepsilon \\
 
F \to n \mid (E)
 
F \to n \mid (E)
 
</tex>
 
</tex>
  
Построим для нее множества <tex>FIRST</tex> и <tex>FOLLOW</tex> (их построение подробно разобрано [[Построение FIRST и FOLLOW#Пример | здесь]]).
+
Напомним, что множества <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex> для неё выглядят так:
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 84: Строка 94:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ *,\ \varepsilon\ \} </tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ *, \ +,\ \$\ ,\ )\ \} </tex>
 
|}
 
|}
  
 
=== Псевдокоды ===
 
=== Псевдокоды ===
Построим функции обработки некоторых нетерминалов.
+
Построим функции обработки некоторых нетерминалов, используя описанный выше шаблон:
  
  E()
+
  E() : '''Node'''
     res = Node("E")
+
     Node res = Node("E")
     switch(curToken)
+
     '''switch''' (curToken)
         case 'n', '(' :
+
         '''case''' n, '(' :
 
             res.addChild(T())
 
             res.addChild(T())
 
             res.addChild(E'())
 
             res.addChild(E'())
             break
+
             '''break'''
         default :
+
         '''default''' :
             error("unexpected char")
+
             <font color="red">error</font>("unexpected char")
     return res
+
     '''return''' res
  
  E'()
+
  E'() : '''Node'''
     res = Node("E'")
+
     Node res = Node("E'")
     switch(curToken)  
+
     '''switch''' (curToken)  
         case '+' :
+
         '''case''' '+' :
 
             consume('+')
 
             consume('+')
 
             res.addChild(Node("+"))
 
             res.addChild(Node("+"))
 
             res.addChild(T())
 
             res.addChild(T())
 
             res.addChild(E'())
 
             res.addChild(E'())
             break
+
             '''break'''
         case '$', ')' :
+
         '''case''' '$', ')' :
             break
+
             '''break'''
         default :
+
         '''default''' :
             error("unexpected char")
+
             <font color="red">error</font>("unexpected char")
       return res
+
       '''return''' res
  
  F()
+
  F() : '''Node'''
     res = Node("F")
+
     Node res = Node("F")
     switch(curToken)
+
     '''switch''' (curToken)
         case 'n' :
+
         '''case''' n :
             consume('n')
+
             consume(n)
             res.addChild(Node("n"))
+
             res.addChild(Node(curToken)) <font color="green">// <tex>\mathtt{curToken}</tex> подпадает под шаблон <tex>n</tex>, поэтому запишем его в <tex>\mathtt{value}</tex> вершины</font>
             break
+
             '''break'''
         case '(' :
+
         '''case''' '(' :
 
             consume('(')
 
             consume('(')
 
             res.addChild(Node("("))
 
             res.addChild(Node("("))
Строка 134: Строка 144:
 
             consume(')')
 
             consume(')')
 
             res.addChild(Node(")"))
 
             res.addChild(Node(")"))
         default :
+
         '''default''' :
             error("unexpected char")
+
             <font color="red">error</font>("unexpected char")
     return res
+
     '''return''' res
  
 
Функции для <tex>T</tex> и <tex>T'</tex> строятся аналогично.
 
Функции для <tex>T</tex> и <tex>T'</tex> строятся аналогично.
Строка 142: Строка 152:
 
=== Дерево разбора ===
 
=== Дерево разбора ===
  
[[Файл:parse_ex1.png|400px|thumb|right|Рисунок 2. Дерево разбора выражения (1 + 2) * 3]]
+
Рассмотрим дерево разбора для выражения <tex>(1 + 2) * 3</tex> и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть <tex>E</tex>. Так как первым токеном является <tex>(</tex>, то будет использовано первое правило разбора <tex>TE'</tex>. Поэтому к вершине с меткой <tex>E</tex> добавятся два ребёнка: <tex>T</tex> и <tex>E'</tex>, а рекурсивный разборщик перейдёт к нетерминалу <tex>T</tex>. <tex>\mathrm{curToken}</tex> по-прежнему равен <tex>(</tex>, поэтому в <tex>F</tex> сработает второй <tex>\mathrm{case}</tex>, первым ребёнком добавится <tex>(</tex>, <tex>\mathrm{curToken}</tex> станет равен <tex>1</tex>, а разборщик перейдёт к нетерминалу <tex>E</tex>. После того как выражение после <tex>(</tex>, которое выводится из <tex>E</tex>, будет полностью разобрано, функция рекурсивного разбора для <tex>F</tex> добавит <tex>)</tex> последним сыном к этому нетерминалу.
  
Рассмотрим дерево разбора для выражения (1 + 2) * 3 и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть <tex>E</tex>. Так как первым токеном является '(', то будет использовано первое правило разбора <tex>TE'</tex>. Поэтому к вершине с меткой <tex>E</tex> добавятся два ребёнка: <tex>T</tex> и <tex>E'</tex>. А рекурсивный разборщик перейдёт к нетерминалу <tex>T</tex>. По-прежнему curToken равен '(', поэтому в <tex>F</tex> сработает второй case, первым ребёнком добавится '(', curToken станет равен <tex>1</tex>, а разборщик перейдёт к нетерминалу <tex>E</tex>. После того как выражение после '(', которое выводится из <tex>E</tex>, будет полностью разобрано, функция рекурсивного разбора для <tex>F</tex> добавит ')' последним сыном к этому нетерминалу.  
+
Продолжая в том же духе, мы построим всё дерево разбора данного выражения.
  
Продолжая в том же духе, мы построим всё дерево разбора данного выражения.
+
[[Файл:parse_ex1.png|400px|thumb|center|Дерево разбора выражения <tex>(1 + 2) * 3</tex>]]
  
 
== Нерекурсивный нисходящий парсер ==
 
== Нерекурсивный нисходящий парсер ==
 +
 +
[[Файл:Parse_table.png|400px|right]]
 +
 +
Рекурсивные разборщики можно генерировать автоматически, зная множества <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>, так как они имеют достаточно прозрачный шаблон построения. Альтернативным способом осуществления нисходящего синтаксического анализа является построение нерекурсивного нисходящего парсера. Его можно построить с помощью явного использования [[Стек | стека]] (вместо неявного при рекурсивных вызовах). Такой анализатор имитирует
 +
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#Лево- и правосторонний вывод слова | левое порождение]]. 
 +
 +
Стек нерекурсивного предиктивного синтаксического анализатора содержит последовательность терминалов и нетерминалов и таблицу синтаксического анализа. На стеке располагается последовательность символов грамматики с маркером конца разбора <tex>\perp</tex> на дне. В начале процесса анализа строки стек содержит стартовый нетерминал грамматики непосредственно над символом <tex>\perp</tex>. Таблица синтаксического анализа представляет собой двухмерный массив <tex>\mathcal{M}[A, c]</tex>, где <tex>A</tex> {{---}} нетерминал или <tex>\perp</tex>, <tex> c </tex> {{---}} токен или символ конца строки <tex>\$</tex>.
 +
 +
Нерекурсивный синтаксический анализатор смотрит на текущий токен <tex> c </tex> входного слова и на символ на вершине стека <tex>A</tex>, а затем принимает решение в зависимости от одного из возникающих ниже случаев:
 +
* если <tex>A\ =\ \perp\ \land\ c\ =\ \$</tex>, то синтаксический анализатор прекращает работу, так как разбор строки завершён (на картинке это соответствует <tex>\mathrm{ok}</tex>),
 +
* eсли <tex>A = c</tex>, то синтаксический анализатор снимает со стека токен <tex>A</tex> и перемещает указатель текущего токена ленты к следующему токену (то есть вызывает <tex>\mathtt{nextToken}</tex>), таким образом, происходит выброс символа <tex> c </tex> со стека (на картинке данная ситуация соответствует символу <tex>\nearrow</tex>),
 +
* eсли <tex>A</tex> является нетерминалом, то программа рассматривает запись <tex>\mathcal{M}[A,c]</tex> таблицы разбора <tex>\mathcal{M}</tex>. Эта запись представляет собой либо правило грамматики вида <tex>A \to \alpha_i,\ \alpha_i = X_1 X_2 \ldots X_t</tex>, и тогда <tex>\mathcal{M}[A,c]</tex> содержит номер <tex>i</tex> данного правила, либо запись об ошибке, и тогда <tex>\mathcal{M}[A,c] = \varnothing</tex>. Если <tex>\mathcal{M}[A,c] \neq \varnothing</tex>, то синтаксический анализатор замещает на стеке нетерминал <tex> A </tex> правой частью правила с номером <tex> i </tex>, помещая символы правила на стек в обратном порядке,
 +
* во всех остальных случаях парсер выдаёт сообщение об ошибке.
 +
 +
Рассмотренные случаи отображены на картинке справа, где блок <tex> N </tex> отвечает нетерминалам грамматики. Из картинки видно, что вместо рассмотрения всех случаев в коде достаточно просто создать таблицу <tex>\mathcal{M}</tex> таким образом, чтобы она учитывала все случаи, что упростит код.
 +
 +
=== Псевдокод ===
 +
 +
Здесь по-прежнему <tex>\mathtt{curToken}</tex> обозначает текущий токен строки, а <tex>\mathtt{nextToken}</tex> передвигает указатель на следующий токен.
 +
 +
<code style = "display: inline-block;">
 +
'''function''' nonRecursiveParser():
 +
    st : '''Stack'''
 +
    st.push(<tex>\perp</tex>)
 +
    st.push(<tex>S</tex>) <font color="green">// здесь <tex> S </tex> {{---}} стартовый нетерминал грамматики</font>
 +
    '''while''' s.top() <tex>\neq\ \perp</tex>
 +
        A = st.top()
 +
        '''if''' <tex>\mathcal{M}[A,\ \mathtt{curToken}]\ ==\ \mathrm{ok}</tex> <font color="green">// <tex> A\ ==\ \perp </tex> и <tex>\mathtt{curToken}\ ==\ \$</tex></font>
 +
            '''break''' <font color="green">// разбор строки завершён</font>
 +
        '''else if''' <tex>\mathcal{M}[A,\ \mathtt{curToken}]\ ==\ \nearrow</tex> <font color="green">// выброс</font>
 +
            nextToken()
 +
            st.pop()
 +
            вывести в выходной поток терминал, отвечающий <tex>\mathtt{curToken}</tex>
 +
        '''else if''' <tex>\mathcal{M}[A,\ \mathtt{curToken}]</tex> {{---}} номер правила <tex>A \to \alpha_i,\ \alpha_i = X_1 X_2 \ldots X_t</tex>
 +
            st.pop()
 +
            '''for''' k = t '''downto''' 1
 +
                st.push(<tex>X_k</tex>)   
 +
            вывести в выходной поток нетерминал, отвечающий <tex>A</tex>
 +
        '''else'''
 +
            <font color="red">error</font>("unexpected symbol")
 +
</code>
 +
 +
=== Пример ===
 +
 +
Рассмотрим пример работы нерекурсивного парсера на всё той же грамматике арифметических выражений. Для начала пронумеруем все правила:
 +
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Номер
 +
!style="background-color:#EEE"| Правило
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>1</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>E \to TE'</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>2</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to +TE'</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>3</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to \varepsilon</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>4</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>T \to FT'</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>5</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to * FT'</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to \varepsilon</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>7</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>F \to n</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>8</tex>
 +
|style="background-color:#FFF;padding:2px 10px"| <tex>F \to (E)</tex>
 +
|}
 +
 +
Теперь можно построить часть таблицы <tex>\mathcal{M}</tex>, содержащей отвечающие нетерминалам строки. Её построение легко осуществить, если известны <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>. По этим множествам можно понять, какое правило использовать для данного нетерминала при текущем токене.
 +
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"|
 +
!style="background-color:#EEE;text-align:center;"| <tex>n</tex>
 +
!style="background-color:#EEE;text-align:center;"| <tex>(</tex>
 +
!style="background-color:#EEE;text-align:center;"| <tex>)</tex>
 +
!style="background-color:#EEE;text-align:center;"| <tex>+</tex>
 +
!style="background-color:#EEE;text-align:center;"| <tex>*</tex>
 +
!style="background-color:#EEE;text-align:center;"| <tex>\$</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>1 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>1 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>3 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>2 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>3 </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>4 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>4 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>5 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6 </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>7 </tex>
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>8 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|-
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>\perp</tex>
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px 30px"|
 +
|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>\mathrm{ok}</tex>
 +
|}
 +
 +
На картинке ниже показаны состояния стека на нескольких первых итерациях цикла и указатель на текущий токен.
 +
 +
[[Файл:Parse_stack.png|500px]]
 +
 +
== Примечания ==
 +
<references/>
 +
== Источники информации ==
 +
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 288 {{---}} 294.
 +
 +
[[Категория: Методы трансляции]]
 +
[[Категория: Нисходящий разбор]]

Текущая версия на 19:27, 4 сентября 2022

Для LL(1)-грамматик возможна автоматическая генерация парсеров, если известны множества [math]\mathrm{FIRST}[/math] и [math]\mathrm{FOLLOW}[/math]. Существуют общедоступные генераторы: 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]\$[/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] 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]([/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](1 + 2) * 3[/math]

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

Parse table.png

Рекурсивные разборщики можно генерировать автоматически, зная множества [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], то синтаксический анализатор прекращает работу, так как разбор строки завершён (на картинке это соответствует [math]\mathrm{ok}[/math]),
  • eсли [math]A = c[/math], то синтаксический анализатор снимает со стека токен [math]A[/math] и перемещает указатель текущего токена ленты к следующему токену (то есть вызывает [math]\mathtt{nextToken}[/math]), таким образом, происходит выброс символа [math] c [/math] со стека (на картинке данная ситуация соответствует символу [math]\nearrow[/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,\ \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]

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

Parse stack.png

Примечания

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

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