Алгоритм синтаксического анализа простого предшествования

Каждый такт работы анализатора начинается с определения отношения предшествования, которое выполняется для пары, образованной из верхнего символа стека и крайнего левого символа входной строки.

Возможны следующие варианты.

1) Ни одно из отношений не определено. Тогда входная цепочка отвергается.

2) Для пары символов определено отношение <• или , тогда выполняется перенос.

При переносе анализатор записывает символ <• в стек, если соответствующее отношение выполняется для данной пары, после чего переносит в стек левый символ входной цепочки. Во входной цепочке осуществляется сдвиг (переход) к следующему символу.

3) Для пары определено отношение • >, тогда выполняется свертка.

При выполнении свертки, анализатор работает следующим образом.

3.1 Просматривает символы в стеке, пока не обнаружит символ <•. Выделяет подцепочку, состоящую из просмотренных символов (без знака <•). Снимает со стека найденные символы.

3.2 Ищет правило вывода грамматики, правая часть которого совпадает с подцепочкой, выделенной на предыдущем шаге. Если такое правило найдено, переход к следующему шагу, иначе – к последнему шагу 4.

3.3 Исключает из стека найденные на первом шаге подцепочку и символ <•. В итоге образуется пара, состоящая из символа на верхушке стека и нетерминального символа из левой части продукции, найденной на шаге 3.2.

3.4 Ищет отношение предшествования, выполняющееся для пары, образованной на предыдущем шаге (это только <• или ).

Если ни одно отношение предшествования не выполнено, входная цепочка отвергается.

В противном случае в стек записывается символ <•, если для пары выполнено данное отношение, и символ из левой части продукции. На этом свертка заканчивается.

4) Анализируются цепочки, записанные в стеке и на входной ленте. Если в стеке находится цепочка $ <• S, где S – стартовый символ грамматики, а на входной ленте только маркер конца строки $, то входная цепочка принимается (допускается). В противном случае – цепочка отвергается.

Дата добавления: 2014-12-27