Алгоритм “сдвиг-свертка” для грамматики простого предшествования. Данный алгоритм выполняется МП-автоматом с одним состоянием. Отношения предшествования служат для того, чтобы определить в процессе выполнения алгоритма, какое действие - сдвиг или свертка - должно выполняться на данном шаге и однозначно выбрать правило при свертке. В начальном состоянии автомата считывающая головка обозревает первый символ, в конец цепочки помещен символ ^к.
Разбор считается законченным (алгоритм завершается), если считывающая головка автомата обозревает символ ^н и при этом больше не может быть выполнена свертка. Решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в конечном состоянии, когда в стеке находятся начальный символ грамматики S и символ ^н. Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка. Тогда входная цепочка не принимается.
Алгоритм состоит из следующих шагов:
Шаг 1. Поместить в верхушку стека символ ^н.
Шаг 2. Сравнить символ, находящийся на вершине стека, с текущим символом ленты.
Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.
Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (если символов, связанных отношением =, на верхушке стека нет, то для правила используется один, верхний символ). Если разбор не закончен, то вернуться к шагу 2.
Ошибка в процессе выполнения алгоритма возникает, когда невозможно выполнить очередной шаг - например, если не установлено отношение предшествования между двумя сравниваемыми символами (на шагах 2 и 4) или если не удается найти нужное правило в грамматике (на шаге 4). Тогда выполнение алгоритма немедленно прерывается.
Алгоритм “сдвиг-свертка” для грамматики операторного предшествования в целом похож на алгоритм для грамматик простого предшествования. Он выполняется тем же МП-автоматом и имеет те же условия завершения и обнаружения ошибок. Основное отличие состоит в том, что при работе со стеком в этом алгоритме не принимаются во внимание находящиеся в нем нетерминальные символы, и при сравнении ищется ближайший к верхушке стека терминальный символ. Однако после выполнения сравнения и определения границ основы при поиске правила в грамматике нетерминальные символы следует, безусловно, принимать во внимание.
Шаг 1. Поместить в верхушку стека символ ^н.
Шаг 2. Сравнить символ, находящийся на вершине стека, игнорируя все нетерминальные символы, с текущим символом ленты.
Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.
Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека (опять же игнорируя нетерминальные символы) все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (при выборе правила нетерминальные символы должны учитываться). Если разбор не закончен, то вернуться к шагу 2.
Конечная конфигурация автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования.
Пример построения распознавателя для грамматики операторного предшествования.
Рассмотрим в качестве примера грамматику G ({S,B,T,J},{ -, &, ^, (, ), p }, P,S) (терминальные символы выделены жирным шрифтом):
P: S ® - B (правило 1)
B ® T | B & T (правила 2 и 3)
T ® J | T ^ J (правила 4 и 5)
J ® ( B ) | p (правила 6 и 7)
Видно, что эта грамматика является грамматикой операторного предшествования.
Построим множества крайних левых и крайних правых символов L (U), R (U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.
На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L t(U), R t(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.
Таблица 2.
Множества крайних правых и крайних левых символов грамматики (по шагам построения)
Символ | Шаг 1 (начало построения) | Последний шаг (результат) | ||
(U) | L(U) | R(U) | L(U) | R(U) |
J | (p | ) p | (p | ) p |
T | J T | J | J T (p | J) p |
B | T B | T | T B J (p | T J) p |
S | - | B | - | B T J) p |
Таблица 3.
Множества крайних правых и левых терминальных символов грамматики (по шагам построения)
Символ | Шаг 1 (начало построения) | Последний шаг (результат) | ||
(U) | Lt(U) | Rt(U) | Lt(U) | Rt(U) |
J | (p | ) p | (p | ) p |
T | ^ | ^ | ^ (p | ^) p |
B | & | & | & ^ (p | & ^) p |
S | - | - | - | - & ^) p |
На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики (табл. 4).
Таблица 4.
Матрица предшествования грамматики
Символы | - | & | ^ | ( | ) | p | ^к |
- | < | < | < | < | > | ||
& | > | < | < | > | < | > | |
^ | > | > | < | > | < | > | |
( | < | < | < | = | < | ||
) | > | > | > | > | |||
p | > | > | > | > | |||
^н | < |
Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа &. В правиле грамматики B ® B & T (правило 3) этот символ стоит слева от нетерминального символа T. В множество L t(T) входят символы: ^ (p. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа &. В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество R t(B) входят символы: & ^) p. Ставим знак > в клетках матрицы, соответствующим этим символам, в столбце для символа &. Больше символ & ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом.
Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Тогда получим следующий вид правил:
P: E ® - E (правило 1)
E ® E | E & E (правила 2 и 3)
E ® E | E ^ E (правила 4 и 5)
E ® ( E ) | p (правила 6 и 7)
Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования. Само преобразование выполняется только с целью более эффективного выполнения алгоритма разбора, в который уже заложены необходимые данные о порядке применения правил при создании матрицы предшествования.
Рассмотрим работу алгоритма распознавания на примерах. Последовательность разбора будем записывать в виде последовательности конфигураций МП-автомата из трех составляющих: не просмотренная автоматом часть входной цепочки, содержимое стека и последовательность правил грамматики. Так как автомат имеет только одно состояние, то для определения его конфигурации достаточно двух составляющих - положения считывающей головки во входной цепочке и содержимого стека, - но последовательность номеров правил несет дополнительную полезную информацию, которая должна быть затем использована компилятором на последующих этапах для семантической обработки и для генерации кода объектной программы. (Кроме того, последовательность примененных правил делает пример более наглядным).
Будем обозначать такт автомата символом ¸. Введем также дополнительное обозначение ¸п, если на данном такте выполнялся перенос, и ¸с, если выполнялась свертка.
Последовательности разбора цепочек входных символов будут, таким образом, иметь вид:
Пример 1. Входная цепочка -p&p^(p).
{ -p&p^(p) ^к; ^н; Æ} ¸п { p&p^(p) ^к; ^н -; Æ} ¸п { &p^(p) ^к; ^н -p; Æ} ¸с { &p^(p) ^к; ^н - E; 7} ¸п { p^(p) ^к; ^н - E &; 7} ¸п { ^(p) ^к; ^н - E &p; 7} ¸с { ^(p) ^к; ^н - E & E; 7,7} ¸п { (p) ^к; ^н - E & E ^; 7,7} ¸п { p) ^к; ^н - E & E ^(; 7,7} ¸п { ) ^к; ^н - E & E ^(p; 7,7} ¸с { ) ^к; ^н - E & E ^( E; 7,7,7} ¸п
{^к; ^н - E & E ^( E ); 7,7,7} ¸c {^к; ^н - E & E ^ E; 7,7,7,6} ¸с {^к; ^н - E & E; 7,7,7,6,5} ¸п
{^к; ^н - E; 7,7,7,6,5,3} ¸с {^к; ^нE; 7,7,7,6,5,3,1}
Пример 2. Входная цепочка -p^p(p).
{ -p^p(p) ^к; ^н; Æ} ¸п { p^p(p) ^к; ^н -; Æ} ¸п { ^p(p) ^к; ^н -p; Æ} ¸с { ^p(p) ^к; ^н - E; 7} ¸п
{ p(p) ^к; ^н - E ^; 7} ¸п { (p) ^к; ^н - E ^p; 7} - ошибка! (нет отношения для пары символов { p, ( })
Пример 3. Входная цепочка -p^p&p.
{ -p^p&p ^к; ^н; Æ} ¸п { p^p&p ^к; ^н -; Æ} ¸п { ^p&p ^к; ^н -p; Æ} ¸с { ^p&p ^к; ^н - E; 7} ¸п
{ p&p ^к; ^н - E ^; 7} ¸п { &p ^к; ^н - E ^p; 7} ¸с { &p ^к; ^н - E ^ E; 7,7} ¸с { &p ^к; ^н - E; 7,7,5} ¸п
{ p ^к; ^н - E &; 7,7,5} ¸п {^к; ^н - E &p; 7,7,5} ¸с {^к; ^н - E & E; 7,7,5,7} ¸с {^к; ^н - E; 7,7,5,7,3} ¸c
{^к; ^нE; 7,7,5,7,3,1}
Пример 4. Входная цепочка -p&p^p.
{ -p&p^p ^к; ^н; Æ} ¸п { p&p^p ^к; ^н -; Æ} ¸п { &p^p ^к; ^н -p; Æ} ¸с { &p^p ^к; ^н - E; 7} ¸п
{ p^p ^к; ^н - E &; 7} ¸п { ^p ^к; ^н - E &p; 7} ¸с { ^p ^к; ^н - E & E; 7,7} ¸п { p ^к; ^н - E & E ^; 7,7} ¸п
{^к; ^н - E & E ^p; 7,7} ¸с {^к; ^н - E & E ^ E; 7,7,7} ¸с {^к; ^н - E & E; 7,7,7,5} ¸п {^к; ^н - E; 7,7,7,5,3} ¸c
{^к; ^нE; 7,7,7,5,3,1}
Два последних примера наглядно демонстрируют, что приоритет операций, установленный в грамматике, влияет на последовательность разбора и последовательность применения правил.