3622
правки
Изменения
м
Нет описания правки
Node res = Node("A")
'''switch''' (curToken) : <font color="green">// принимаем решение в зависимости от текущего токена строки</font>
'''case''' <tex>\mathrm{FIRST}(\alpha_1) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ setminus \varepsilon \in \mathrm{FIRST}(\alpha_1))</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) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ setminus \varepsilon \in \mathrm{FIRST}(\alpha_2))</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")
'''function''' consume(c: '''char''')
'''if''' curToken != c
<font color="red">error</font>("expected Expected $c but found $curToken" + c)
nextToken()
=== Дерево разбора ===
Рассмотрим дерево разбора для выражения <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> последним сыном к этому нетерминалу.
Продолжая в том же духе, мы построим всё дерево разбора данного выражения.
Нерекурсивный синтаксический анализатор смотрит на текущий токен <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>, помещая символы правила на стек в обратном порядке,
* во всех остальных случаях парсер выдаёт сообщение об ошибке.
'''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")
