Изменения

{{В разработке}}== Общая схема построения парсеров с помощью Для [[LL(k)-грамматики, множества FIRST и FOLLOW ==Для | LL(1) -грамматик ]] возможна автоматическая генерация парсеров, если известны множества <tex>\mathrm{FIRST }</tex> и <tex>\mathrm{FOLLOW}</tex>. Существуют общедоступные генераторы: ANTLR<ref>[http://enwww.wikipediaantlr.org/wiki/ANTLR ANTLR{{---}} Parser generator]</ref>, Bison<ref>[http://enwww.wikipediagnu.org/wikisoftware/GNU_bison bison/ Bison {{---}} GNU bisonProject]</ref>, Yacc<ref>[http://endinosaur.compilertools.net/ Lex & Yacc {{---}} A Lexical Analyzer Generator and Yet Another Compiler-Compiler]</ref>, Happy<ref>[https://www.wikipediahaskell.org/wikihappy/Yacc YaccHappy {{---}} The Parser Generator for Haskell]</ref>.

Для каждого нетерминала A : Пусть <tex>A \rightarrow Gamma =\alpha_1 langle \mid \alpha_2 \mid ... \mid Sigma, N, S, P \alpha_k rangle</tex> создадим функцию A{{---}} LL(1) : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала A-грамматика. Построим для нее парсер.

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

AКаждый момент времени парсер работает с определённым '''токеном''' (англ. ''token'') : Node res = Node("A") switch (curToken) : case : FIRST(\alpha_1) : /входного слова <tex>s</ \alpha_1 = X_1x_2.tex>.x_{t_1} // X_1 Токен {{---}} нетерминал Node t = X_1() resодин или несколько терминалов, объединяемые по смыслу.addChild(t)Примерами токенов могут выступать следующие лексические единицы: * произвольный символ <tex> c </tex>,* целое слово, например <tex> public </ x_2 {{---}} терминалtex>, if (curToken != x_2) error("expected x_2") res.addChild(new Node("x_2") nextToken() /* число со знаком, обозначаемое далее для краткости как <tex> n </ x_3 tex>... break; case FIRST(\alpha_2) : // \varepsilon \in FIRST(\alpha_2) case FOLLOW(A) В общем случае, токеном может являться любое слово, удовлетворяющее произвольному [[Регулярные языки: ... break; два определения и их эквивалентность | регулярному выражению]]... default : error("unexpected char") return res

[[Файл: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) : <font color= Пример "green">// принимаем решение в зависимости от текущего токена строки</font> '''case''' <tex>\mathrm{FIRST}(\alpha_1) \setminus \varepsilon</tex> : <font color="green">// <tex>\alpha_1 =X_1X_2 \ldots X_{t}</tex> </font>Рассмотрим построение '''for''' i = 1 .. t '''if''' <tex> X_i </tex> {{---}} терминал consume(<tex>X_i</tex>) res.addChild(Node(<tex>X_i</tex>)) '''else''' <font color="green">// <tex>X_i</tex> {{---}} нетерминал, нужно вызвать соответствующую ему функцию рекурсивного парсера на примере грамматики арифметических выражений</font> Node t = <tex>X_i()</tex> res.addChild(t)Запишем грамматику '''break''' '''case''' <tex>\mathrm{FIRST}(\alpha_2) \setminus \varepsilon</tex> : <tex>\ldots</tex> '''break''' <tex>\ldots</tex> '''case''' <tex>\mathrm{FIRST}(\alpha_k) \setminus \varepsilon</tex> : <tex>\ldots</tex> '''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  '''function''' consume(c: '''char''') '''if''' curToken != c <font color="red">error</font>("Expected $c but found $curToken") nextToken()

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

T' \to \times * FT' \mid \varepsilon \\

Теперь грамматика стала LL(1)-грамматикойНапомним, построим для нее что множества <tex>\mathrm{FIRST }</tex> и <tex>\mathrm{FOLLOW (их построение подробно разобрано [[Построение FIRST и FOLLOW#Пример | здесь]]).}</tex> для неё выглядят так:

|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times*,\ \varepsilon\ \} </tex>

|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times*, \ +,\ \$\ ,\ )\ \} </tex>

=== Псевдокоды ===Построим функции обработки некоторых нетерминалов, используя описанный выше шаблон:  E() : '''Node''' Node res = Node("E") '''switch''' (curToken) '''case''' n, '(' : res.addChild(T()) res.addChild(E'()) '''break''' '''default''' : <font color="red">error</font>("unexpected char") '''return''' res

E'(): '''Node''' Node res = Node("E'") '''switch''' (curToken) '''case 'n', ''+' : consume(' :+') res.addChild(Node("+")) res.addChild(T()) res.addChild(E'()) '''break''' '''case''' '$', ')' : '''break''' '''default ''' : <font color="red">error</font>("unexpected char") '''return ''' res

F() : '''Node''' Node res = Node("F") '''switch''' (curToken) '''case''' n : consume(n) res.addChild(Node(curToken)) <font color="green">// <tex>\mathtt{curToken}</tex> подпадает под шаблон <tex>n</tex>, поэтому запишем его в <tex>\mathtt{value}</tex> вершины</font> '''break''' '''case''' '(' : consume('(') res.addChild(Node("(")) res.addChild(E()) consume(')') res.addChild(Node(")")) '''default''' : <font color="red">error</font>("unexpected char ") '''return''' res Функции для <tex>T</tex> и <tex>T'</tex> строятся аналогично. === Дерево разбора === Рассмотрим дерево разбора для выражения <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> последним сыном к этому нетерминалу.  Продолжая в том же духе, мы построим всё дерево разбора данного выражения. [[Файл: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 = ct '''downto''' 1 st.push(<tex>X_k</tex>) вывести в выходной поток нетерминал, отвечающий <tex>A</tex> '''else''' <font color="red">error</font>("expectedunexpected 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 + cTE'</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> nextToken|} Теперь можно построить часть таблицы <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>|}

E'() res = Node("E'") switch(curToken) case '+' : consume('+') nextToken() 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' [[Файл: if (curToken != 'n') error("expected n") nextToken() resParse_stack.addChild(Node("n")) break case '(' : consume('(') res.addChild(Node("(")) res.addChild(E()) consume(')') res.addChild(Node(")")) default : error("unexpected char") return respng|500px]]

Функции для T и T' строятся аналогично== Примечания ==<references/>== Источники информации ==* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 288 {{---}} 294.