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

2015-05-25T13:52:03Z

178.71.143.38:

Для [[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>.

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

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

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

Здесь <tex>\mathtt{Node}</tex> {{---}} структура следующего вида:
'''struct''' Node
children : '''list<Node>'''
value : '''string''' // имя нетерминала или текст терминала
'''function''' addChild('''Node''') // функция, подвешивающая поддерево к данному узлу

Каждый момент времени парсер работает с определённым '''токеном''' (англ. ''token'') входного слова <tex>s</tex>. Токен {{---}} один или несколько терминалов, объединяемые по смыслу. Примерами токенов могут выступать следующие лексические единицы:
* произвольный символ <tex> c </tex>,
* целое слово, например <tex> public </tex>,
* число со знаком, обозначаемое далее для краткости как <tex> n </tex>.
В общем случае, токеном может являться любое слово, удовлетворяющее произвольному [[Регулярные языки: два определения и их эквивалентность | регулярному выражению]].

[[Файл:string_token.png|300px]]

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

В псевдокоде используются следующие обозначения:
* <tex>\mathtt{curToken}</tex> {{---}} текущий токен строки,
* <tex>\mathtt{nextToken()}</tex> {{---}} функция, записывающая в <tex>\mathtt{curToken}</tex> следующий за ним токен.

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

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

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

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

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

<tex>
E \to TE' \\
E' \to +TE' \mid \varepsilon \\
T \to FT' \\
T' \to * FT' \mid \varepsilon \\
F \to n \mid (E)
</tex>

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

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</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>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</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>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ *, \ +,\ \$\ ,\ )\ \} </tex>
|}

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

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

Функции для <tex>T</tex> и <tex>T'</tex> строятся аналогично.

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

Рассмотрим дерево разбора для выражения <tex>(1 + 2) * 3</tex> и несколько первых шагов алгоритма рекурсивного разбора. Сначала вызывается функция стартового нетерминала грамматики, то есть <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>, то синтаксический анализатор прекращает работу, так как разбор строки завершён,
* eсли <tex>A = c</tex>, то синтаксический анализатор снимает со стека токен <tex>A</tex> и перемещает указатель текущего токена ленты к следующему токену (то есть вызывает <tex>\mathtt{nextToken}</tex>), таким образом, происходит выброс символа <tex> c </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>) // здесь <tex> S </tex> {{---}} стартовый нетерминал грамматики
'''while''' s.top() <tex>\neq\ \perp</tex>
A = st.top()
'''if''' <tex>\mathcal{M}[A,\ curToken]\ ==\ \mathrm{ok}</tex> // <tex> A\ ==\ \perp </tex> и <tex>\mathtt{curToken}\ ==\ \$</tex>
'''break''' // разбор строки завершён
'''else if''' <tex>\mathcal{M}[A,\ curToken]\ ==\ \nearrow</tex> // выброс
nextToken()
st.pop()
вывести в выходной поток нетерминал, отвечающий <tex>\mathtt{curToken}</tex>
'''else if''' <tex>\mathcal{M}[A,\ 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'''
error("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.

[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]

Викиконспекты - Вклад участника [ru]

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