) L-диаграммер, упоминаемый в упр. 18, тоже может следить за несколькими выводами в подходящей LR-грамматике, ио делает это менее „прямым" способом.

(2) Если условие в (1) не выполнено, но д содержит вершину, из которой выходит дуга, помеченная нетерминалом, то

(д, aw$, у$)\--{д\ aw$, д"у)

где / = {(л» 01 .из (d, i)q выходит дуга, помеченная А] н q" = {{d, i) I из [d, i) g выходит дуга, помеченная нетерминалом}.

(3) Если не выполнены условия ни в (1), ни в (2), но д содержит заключительную вершину или вершину, из которой

выходит дуга, помеченная е (обозначим через д множество этих вершин), то

(д, aw$, у$)Н(, aw$, у$)

где у = д"у и g = {(d, /) из [d, i)g" в [d, j) ведет дуга, помеченная Аид содержит вершину диаграммы d}.

Языком, распознаваемым синхронным распознавателем Mq, назовем множество

L{Ma) = {we\{{{ds, 1)}, w$, S)h-*({(s. )}. $)}

где ((5, ft) -заключительная вершина начальной диаграммы d-.

Пример 6. Рассмотрим синхронный распознаватель Ма„ соответствующий КС-грамматике с правилами

S~A\B А ~аАЬ\е В~аВс\е

Его КС-диаграммы изображены на рис. Д.З. Для входной цепочки аЬ% распознаватель Mq сделает такую последовательность тактов:

«fe $)Н({(л, 1), [dn. 1)}, аЪ%, S)

Ь(((л, 2), (dj,, 2)\,b%, {(ds, 1)}$)

[-({(л, \)AdB. b$, i(d, 2), {dj„2)}{(ds, 1)}$)

3), (d, 3)}, b$, {(d, {)}$)

4)}, , {{ds, 1)}$) h({{ds, 2)}, $, $)

Нетрудно убедиться, что L (Мс,) - L (Gg) - {a"b"\n0\ \J

Распознаватель Mq назовем адекватным (грамматике G) если L(A1g) = L(G). yf h

Упр. 19. Покажите, что если синхронный распознаватель адекватен грамматике G, не содержащей бесполезных нетер-лшналов, то G не леворекурсивна.

из начальной вершины, помечены разными входными символами, а все дуги, выходящие из незаключнтельиой вершины, помечены парами {d, г,), [d, i), {d, i,) для fe> 1, обозначающими

заключительные вершины некоторой диаграммы d.

Очевидно, что L-диаграммер является детерминированным распознавателем.

**Упр. 18. Покажите, что для каждого детерминированного КС-языка существует распознающий его L-диаграммер.

Рассмотренные до сих пор детерминированные нисходящие анализаторы с магазинной памятью строят только один начальный отрезок левого вывода, совместимый с обработанной частью входной цепочки. В [Алгол 68] (гл. 1) описан анализатор (назовем его синхронным), который пытается синхронно следить за несколькими левыми выводами i).

Определение. Синхронным распознавателем Mq, соответствующим КС-грамматике 6~(N, 2, Р, S), назовем пятерку (2, N, D, ds, Q), где (2, N, D, (5) -КС-диаграммер, соответствующий грамматике G, а Q - множество состояний, элементами которого служат множества вершин диаграмм из D. Множество Q является также магазинным алфавитом распознавателя Мд.

Конфигурация распознавателя Mq имеет вид (д, ш$, у$), где qeQ, 6*, yQ*, $CUQ. Далее в пунктах (1), (2) и (3) определяется один такт работы синхронного распознавателя. Эти пункты аналогичны соответственно пунктам (а), (б) и (в, г) в определении КС-диаграммера. Однако существенное различие состоит в том, что, во-первых, состояниями здесь служат множества вершин, во-вторых, даже из одной вершины возможен одновременный переход за один такт по нескольким дугам и, в-третьих, синхронный распознаватель сразу определяется как детерминированный автомат, тогда как диаграммер становится детерминированным, вообще говоря, при дополнительных условиях (например, если выполнено условие разделенности).

Пусть дана конфигурация {д, aw, у$), где а1, либо a = w = e.

(1) Если множество д содержит вершину, из которой выходит дуга, помеченная а 2, то

{д, aw$, у$)1-(9\ w$, у$) где g==\{d, j)\ дуга, выходящая из (d, i)g и помеченная а, ведет в {d, j)}.

Рие. Д.З. КС-диаграммы синхронного распознавателя.

что переход от синхронного распознавателя к соответствующему анализатору нетривиален: для получения разбора может понадобиться еще один проход (об этом см. в [Алгол 68]).

5.2. ДЕТЕРМИНИРОВАННЫЙ ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ

В предыдущем разделе мы рассмотрели класс гра.мматик, для которых возможен детерминированный нисходящий синтаксический анализ с чтением входной цепочки слева направо. Существует аналогичный класс грамматик, для которых тоже возможен детерминированный анализ с чтением цепочки слева направо, но анализ восходящий. Они называются LR-граммати-ками и их изложение будет во многом параллельно изложению LL-грамматик предыдущего раздела.

5.2.1. Разбор с помощью детерминированного алгоритма типа «перенос - свертка»

В гл. 4 было показано, что восходящий разбор можно провести, чередуя свертки и переносы, с помощью двух магазинов. Разбор типа „перенос-свертка" состоит в переносе входных символов в магазин, пока в.его верхней части не окажется основа. В этот момент делается свертка основы. Если не попадается ошибок, то процесс повторяется до тех пор, пока вся входная цепочка не будет прочитана, а в магазине останется один начальный символ грамматики. В гл. 4 мы изложили работающий именно таким образом алгоритм с возвратами, который мог вначале неправильно выбирать свертки для некоторых

основ, но в конце концов делал правильные выборы. В этом разделе будет изучен большой класс грамматик, для которых всегда возможен детерминированный безвозвратный анализ такого типа. Это LR(fe)-rpaMMaTHKH, образующие наиболее широкий класс грамматик, анализируемых естественным образом снизу вверх с помощью детерминированного преобразователя с магазинной памятью. Буква L в названии ЬК()-грамматик указывает на то, что входная цепочка читается слева (left) направо, R - на То, что выдается правый (right) разбор, а k - число входных символов, на которые алгоритм „заглядывает вперед".

В дальнейшем мы исследуем разные подклассы ЬН(й)-грам-матик, в том числе грамматики предшествования и грамматики ограниченного правого контекста.

Пусть ах - правовыводимая цепочка какой-то грамматики, причем а-либо пустая цепочка, либо оканчивается нетерминальным символом. Тогда а называется открытой частью цепочки ах, а X-замкнутой частью. Границу между а и л: назовем рубежом. Эти определения замкнутой и открытой части правовыводимой цепочки не следует путать с аналогичными определениями законченной и незаконченной части левовыводимой цепочки.

Алгоритм разбора типа „перенос-свертка" можно рассматривать как программу расширенного детерминированного МП-преобразователя, который проводит разбор снизу вверх. Для данной ВХОДНОЙ цепочки w МП-преобразователь моделирует в обратном порядке ее правый вывод. Допустим, что

S = a rttj r...:,aw

- правый вывод цепочки w. Каждая правовыводимая цепочка а-распределяется в памяти ДМП-преобразователя так, что ее открытая часть хранится в магазине, а замкнутая - на входной ленте справа от головки. Например, если а = аЛх, то аЛ будет в магазине (причем Л -верхний символ), а х-это еще не прочитанная часть первоначальной входной цепочки.

Допустим, что a. j = ySz и на шаге a- i=a/ применено правило S->р(/, причем ураЛ и yzx. Имея в магазине цепочку аЛ, МП-преобразователь перенесет несколько (возможно, ни одного) символов с левого конца цепочки х в магазин. Пока не обнаружит правый конец основы цепочки а. К этому моменту в магазин будет перенесена цепочка у.

Затем МП-преобразователь должен локализовать левый конец основы. Как только он это сделает, он заменит основу (Здесь ею будет цепочка у), занимающую верхнюю часть магазина, подходящим нетерминалом (здесь нетерминалом В) и ъы-Дзст Номер правила В-у. Теперь в магазине окажется yS,

Упр. 20. Покажите, что если G -псевдоразделенная грамматика, то соответствующие простой МП-распознаватель и синхронный распознаватель Ма эквивалентны (и, значит, если слаборазделснная грамматика, то Мо адекватен G).

Из упр. 20 и 3 следует, что проблема распознавания адекватности синхронного распознавателя неразрешима. Заметим еще,

и правый вывод

(2) 5-

SaSaSbb SaSabb r> Saabb aabb

Разберем цепочку aabb, используя магазин и применяя операции переноса и свертки. Символ $ будет служить концевым маркером входной цепочки и дна магазина.

Работу алгоритма разбора типа „перенос-свертка" опишем в терминах конфигураций, представляющих собой тройки вида (аХ, X, п), где

а Z образует непрочитанную часть входа. Эти цепочки являются соответственно открытой и замкнутой частями правовыводимой цепочки

Заметим, что основа цепочки гхАх никогда не может лежать целиком внутри а, хотя она может быть полностью внутри т. е. а,. 1 может иметь вид аАхВх и к ней можно применить правило вида В-у, где хухх, чтобы получить а. Так как цепочка л может быть очень длинной, то может потребоваться много операций переноса, прежде чем а,- будет сведена к а .

Итак, в ходе разбора алгоритм типа „перенос-свертка" должен принимать решения трех типов. Во-первых, перед каждым шагом надо определить, перенести ли в магазин входной символ или делать свертку. Это решение фактически состоит в выяснении того, где в правовыводимой цепочке находится правый конец основы.

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

Грамматика, в которой никакие два различные правила не имеют одинаковых правых частей, называется детерминированна (или однозначно) обратимой или просто обратимой. Нетрудно показать, что каждый контекстно-свободный язык порождается по крайней мере одной обратимой КС-грамматикой.

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

Пример 5.21. Рассмотрим грамматику G с правилами (!) SSaSb

(1) аХ-содержимое магазина, причем X -верхний символ;

(2) л; -непрочитанная часть входной цепочки;

(3) л - ВЫХОД к данному моменту.

Эти конфигурации имеют тот же вид, что и конфигурации расширенного МП-преобразователя, только в них опущено состояние и магазин предшествует входу. В разд. 5.3.1 мы дадим формальное описание алгоритма типа „перенос-свертка".

Вначале алгоритм находится в конфигурации (.% aabb$, е). Ему надо догадаться, что основой правовыводимой цепочки aabb является входящая в нее на левом конце пустая цепочка е и что эту основу надо свернуть к 5. Отложим пока описание самого механизма, обеспечивающего распознавание основы. Итак, алгоритм должен перейти в конфигурацию {S, aabb% 2). После этого он перенесет в магазин входной символ, перейдя в конфигурацию ($Sg, abb$, 2). Затем догадается, что наверху магазина находится основа е и сделает свертку, перейдя в конфигурацию {$SaS, abb%, 22). Продолжая в том же духе, алгоритм сделает такую последовательность тактов:

($, aabb%, е) Н ($S, aabb%, 2) l-(?Sa, abb%, 2) b($5aS, abb%, 22) 1-($5а5л, bb%, 22) Н($5й5а5, 7;?$, 222) \-{%SaSaSb, b, 222) \~{$SaS, b, 2221) \-i$SaSb, $, 2221) h($5. $, 22211) К допуск □

5.2.2. LR ()-грамматики

В этом разделе мы опишем широкий класс грамматик, для которых всегда можно построить детерминированные правые анализаторы. Он состоит из LR(fe)-rpaMMaTHK.

Говоря неформально, грамматика будет ЕН(А)-грамматикой, если для произвольного правого вывода 5 га г-а ... /д -в каждой правовыводимой цепочке а-, читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя при этом не более чем до k-ro символа, расположенного справа от правого конца этой основы.

Допустим, что a-y=-aAw и а=ат, где р-основа цепочки а.. Допустим далее, что аР = XXg...Х. Если КС-грамма-нка является ЬК(й)-грамматикой, можно быть уверенным в следующем: