Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

8. Во всем множестве правил Р грамматики G(VT,VN,P,S) ищется правило, у которого правая часть совпадает с цепочкой γ (по условиям грамматик предшествования все правые части правил должны быть различны, поэтому может быть найдено или одно такое правило, или ни одного). Если правило найдено, то в стек помещается нетерминальный символ из левой части правила, иначе, если правило не найдено, это значит, что входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке. Следует отметить, что при выполнении свертки считывающая головка автомата не сдвигается и текущий входной символ a iостается неизменным. После выполнения свертки необходимо вернуться к шагу 2.

После завершения алгоритма решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в состоянии, когда в стеке находятся начальный символ грамматики S и символ

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

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Это преобразование заключается в том, что все нетерминальные символы в правилах грамматики заменяются на один нетерминальный символ (чаще всего – целевой символ грамматики).

Построенная в результате такого преобразования грамматика называется остовной грамматикой, а само преобразование – остовным преобразованием [1, 7].

Остовное преобразование не ведет к созданию эквивалентной грамматики и выполняется только для упрощения работы алгоритма (который при выборе правил все равно игнорирует нетерминальные символы) после построения матрицы предшествования. Полученная в результате остовного преобразования грамматика может не являться однозначной, но все необходимые данные о порядке применения правил содержатся в матрице предшествования и распознаватель остается детерминированным. Поэтому остовное преобразование может выполняться без потерь информации только после построения матрицы предшествования. При этом также необходимо следить, чтобы в грамматике не возникло неоднозначностей из-за одинаковых правых частей правил, которые могут появиться в остовной грамматике. Вывод, полученный при разборе на основе остовной грамматики, называют результатом остовного разбора, или остовным выводом.

По результатам остовного разбора можно построить соответствующий ему вывод на основе правил исходной грамматики. Однако эта задача не представляет практического интереса, поскольку остовной вывод отличается от вывода на основе исходной грамматики только тем, что в нем отсутствуют шаги, связанные с применением цепных правил, и не учитываются типы нетерминальных символов. Для компиляторов же распознавание цепочек входного языка заключается не в нахождении того или иного вывода, а в выявлении основных синтаксических конструкций исходной программы с целью построения на их основе цепочек языка результирующей программы. В этом смысле типы нетерминальных символов и цепные правила не несут никакой полезной информации, а напротив, только усложняют обработку цепочки вывода. Поэтому для реального компилятора нахождение остовного вывода является даже более полезным, чем нахождение вывода на основе исходной грамматики. Найденный остовной вывод в дальнейших преобразованиях уже не нуждается. [4]

В общем виде последовательность построения распознавателя для КС-грамматики операторного предшествования G(VT,VN,P,S) можно описать следующим образом:

1. На основе множества правил грамматики Р построить множества крайних левых и крайних правых символов для всех нетерминальных символов грамматики

2. На основе множества правил грамматики Р и построенных на шаге 1 множеств L(U) и R(U) построить множества крайних левых и крайних правых терминальных символов для всех нетерминальных символов грамматики

: L t(U) и R t(U).

3. На основе построенных на шаге 2 множеств L t(U) и R t(U) для всех терминальных символов грамматики