Изменения

Перейти к: навигация, поиск

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

197 байт добавлено, 13:48, 12 августа 2015
Нерекурсивный нисходящий парсер: более подробные пояснения случаев в тексте к картинке
Нерекурсивный синтаксический анализатор смотрит на текущий токен <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>, помещая символы правила на стек в обратном порядке,
* во всех остальных случаях парсер выдаёт сообщение об ошибке.
Анонимный участник

Навигация