Главная Промышленная автоматика.

1} Утверждение не очень четко сформулировано и, если его понимать буквально, для LR (й)-грамматики неверное.- /7рил. ред.

ару к аАу. Так как Л дает р независимо от w, то LR (/е)-усло-вие говорит о том, что в FlRST((ti;.) содержится информация, достаточная для определения того, что ар за один шаг выводится из аЛ. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, работая с LR (ку грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор. Если начальный символ 5 не встречается в правых частях правил, то в определении LR (ку грамматики вместо 5 можно взять S, а именно G(N, 2, Р, 5) будет LR (/г)-грамматикой, если из трех условий

(1) SlaAw.aw,

(2) S=> уВх:ау,

(3) FIRST, () = FIRSTi/)

следует, что аАу = уВх.

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

Пример 5.22. Рассмотрим грамматику G с правилами

S ~Sa\a

Если игнорировать ограничение, касающееся появления начального символа в правых частях правил, и пользоваться вторым определением, то G придется считать ЕН(0)-грамматикой.

Однако, согласно правильному определению, G не LR (0)-грамматика, так как из трех условий

(1) S:b,rSarS,

(2) S-:GrSGrSa,

(3) FlRST,(e)-FIRST(,H-e

не следует, что SaS. Применяя определение к этой ситуа-пни, имеем ае, p-S, ш -г, y-i>, Л =-5, fl = S, хе и /--0. Проблема здесь заключается в том, что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видя символа, стоящего после 5 (т. е. наблюдая „нулевое" количество символов). В соответствии с интуицией G не должна быть LR(0)-гpaммaтикoй и она не будет ею, если пользоваться первым определением. Это определение мы и будем использовать На протяжении всей книги. □

В данном разделе мы покажем, что для каждой LR (й)-грам-матики G(N, 2, Р, S) можно построить детерминированный правый анализатор, который ведет себя следующим образом.

(1) Зная ХХз.-.Ху и первые k символов цепочки X+j... XfW, можно не сомневаться, что правый конец основы не будет достигнут до тех пор, пока не станет / - г).

(2) Зная ар и не более k символов цепочки w, всегда можно определить, что р - основа и ее надо свернуть к А.

(3) Если a. j -S, то можно уверенно сигнализировать о тол1, что входную цепочку следует допустить.

Заметим, что, проходя по последовательности а, а.,..., а, мы вначале видим только цепочку FIRSTj (а,) - FIRST;; (г). На каждом шаге цепочка символов, на которые мы „заглядываем вперед" (аванцепочка), состоит из к или менее терминальных символов.

Теперь перейдем к определению LR ()-грамматйКи, но прежде введем простое понятие пополненной грамматики.

Определение, Пусть 6 = (N, 2, Р, 5)-КС-грамматика. Пополненной грамматикой, полученной из G, будем называть грамматику G(NLI{5, 2, Ри{5-5}, 5). Другими словами, это просто G с новым начальным правилом 5-5, где S - новый начальный символ, не принадлежащий N. Будем считать, что 5-5--пулевое правило грамматики G, а остальные правила занумерованы числами 1,2, ..., р. Это начальное правило добавляется для того, чтобы свертку, в которой используется нулевое правило, можно было интерпретировать как сигнал о том, что цепочка допускается.

Дадим точное определение LR (/г)-грамматикн.

Определение. Пусть G(N, 2, Р, S) - КС-грамматика я G= (N, 2, Р, S) - полученная из нее пополненная грамматика. Будем называть G ЬЩкуграмматикой для кО, если из условий

(1) S =CrAwG,r¥,

(2) 8:ЬгУВх:0га,?,у,

(3) FlRST,(E£;)-FIRST,(t/)

следует, что аАууВх (т.е. ау, А = В и х = у).

Грамматика G называется -грамматикой, если она LЩky грамматика для некоторого kQ.

Интуитивно это определение говорит о том, что если сфьо и ар-правовыводимые цепочки пополненной грамматики, у которых FIRST([2/)==FIRST(f/), и Л-р -последнее правило, использованное в правом выводе цепочки ap[£j. то правило Л--*-р должно использоваться также в правом разборе при свертке



Прежде всего, этот анализатор строится по пополненной грамматике С. Ведет он себя во многом так же, как анализатор типа „перенос -свертка", введенный в примере 5.21, за исключением того, что после каждого символа грамматики в магазин будет записываться специальный информационный символ, называемый ЬН(й)-таблицей. Эти ЬН(й)-таблицы помогут определять,

Действие

Переход

Рис. 5,9. LR (])-анализатор для грамматики g (i -свертка, при которой примеиеио i-e правило, S -перенос, л-допуск. Л" -ошибка).

ЧТО надо делать на очередном шаге - свертку или перенос, и в случае свертки - какое правило при этом применить.

По-видимому, наилучший способ описать поведение LR{k)-анализатора - это рассмотреть подходящий пример.

Возьмем грамматику G из примера 5.21, которая, как легко проверить, является 11Н(1)-грамматикой. Пополненная грамматика G состоит из правил

5 -SaSb, S

(0) (1) (2)

ЬН(1)-анализатор для грамматики G приведен на рис. 5.9.

ЬН(й)-анализатор для КС-грамматики G -это не что иное, как множество строк большой таблицы, каждая строка которой называется LR(fe)-тaблиueй. Одна строка, здесь это Г,,, выделяется в качестве начальной ЬН(й)-таблицы. Каждая ЁК(/г)-таблица состоит из двух функций - функции действия f и функции переходов g:

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

(1) Аргументом функции действия / служит цепочка и G (она называется аванцепочкой), а соответствующее значение f [и] - один из символов „действий": перенос, свертка i, ошибка или допуск.

(2) Аргументом функции переходов g служит символ X 6 N U 2, а соответствующее значение g (Х) - либо имя некоторой LR(fe)-таблицы, либо ошибка.

Сейчас мы не будем объяснять, как построить такой анализатор, а отложим это до разд. 5.2.3 и 5.2.4.

LR-анализатор ведет себя так же, как алгоритм типа „перенос-свертка", используя в процессе работы магазин, входную и выходную ленты. Вначале магазин содержит начальную LR(ft)-таблицу Tq и ничего больше. На входной ленте находится анализируемая цепочка, а выходная лента вначале пустая. Если предположить, что надо разобрать входную цепочку aabb, то начальной конфигурацией анализатора будет {Т, aabb, е). Затем разбор будет осуществляться согласно следующему алгоритму.

Алгоритм 5.7. LR (й)-а л г о р и т м разбора.

Вход. Множество LR(ft)-тaблиц для LR(ft)-rpaMMaTHKH G-(N, 2, Я, S) с таблицей ТЖ", выделенной в качестве начальной, и входная цепочка z*, которую надо разобрать.

Выход. Если zL{G), то правый разбор цепочки z в грамматике G, в противном случае сигнал об ошибке.

Метод. Выполнять шаги (1) и (2) до тех нор, пока не будет допущена входная цепочка или не встретится сигнал об ошибке. В случае допуска цепочка на выходной ленте представляет собой правый разбор цепочки z.

(1) Определяется аванцепочка и, состоящая из k очередных входных символов (или менее чем k символов, если обрабатывается конец входной цепочки).

(2) Функция действия / таблицы, расположенной наверху магазина, применяется к аванцепочке и.

(а) Если / (w)= перенос, то следующий входной символ, скажем а, переносится со входа в магаз1Ш. К а применяется функция переходов g верхней таблицы магазина и определяется новая таблица, которую надо поместить наверху магазина. После этого вернуться к шагу (]). Если следующего входного символа нет или значение g (а) не определено, остановиться и выдать сигнал об ошибке.

(б) Если / (и):=свертка i и А ->а-правило с номером i, то из верхней части магазина устраняются 2а[символов) и на

*) Если a = Ai ... ху, то в данный момент верхняя часть магазина имеет Д tqxitix2 ... xtf. Устраняй из магазина 2 а символов, мы устраняем основу вместе с промежуточными LR-тэблицами.



выходной ленте записывается номер правила /. Наверху магазина оказывается тогда новая таблица Т\ и ее функция переходов применяется к Л для определения следующей таблицы, которую надо поместить наверху магазина. Помещаем Л и эту новую таблицу наверху магазина и переходим к шагу (1).

(в) Если / (п) = ошибка, разбор прекращается (на практике надо перейти к процедуре исправления ошибок).

(г) Если / (и) ~ допуск, остановиться и объявить цепочку, записанную на выходной ленте, правым разбором первоначальной входной цепочки. . □

Пример 5.23. Пусть алгоритм 5.7 начинает работу в началь-ной конфигурации (Т,ааЬЬ, е). Будем пользоваться LR(1)-Ta6-лицами, приведенными на рис. 5.9. Здесь аванцепочкой служит п. Значением функции действия таблицы на цепочке а будет свертка 2, где 2 - номер правила S-e. На шаге (26) надо устранить из магазина 2е-О символов и выдать номер 2. Верхней таблицей в магазине все еще остается Г. Так как функция переходов таблицы Гц на аргументе S принимает значение Г,, то наверху магазина помещаем ST--это приводит к конфигурации (T,ST, ааЪЪ, 2).

Пройдем еще раз через этот цикл. Аванцепочкой по-прежнему служит а. Значением функции действия таблицы на а будет перенос, так что символ а переносим со входа в магазин. Функция переходов таблицы Т- на аргументе а принимает значение Т, так что после этого шага получится кояитуmyin [ТSTаТ, abb,2),

Продолжая б том же духе, LR-аналпзатор сделает такую последовательность тактов:

(Г„ ааЬЬ,еУг~{Т,8Т,, ааЬЬ, 2)

+ {T,ST,aT„ abb, 2) [-{T,ST,aT,ST,, abb, 22) [-(T,STaT.ST,aT„ bb, 22) y-{T,ST,aTlST,aT,ST„ bb, 222) + iT,ST,aT,ST,aT,ST,bT„ b, 222) + (T,ST,aT,ST„ b, 2221) [~{T,ST,aT,ST,bT,, e, 2221) \-{T,ST„ e, 22211)

Заметим, что эта последовательность шагов по существу совпадает с той, что была в примере 5.21, а ЕК(1)-таблицы как раз поясняют способ, которым в том примере принимались решения. □

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

нее можно построить LR(/г)-aнaлизaтop. Но сначала вернемся к основному определению LR (/г)-грамматики и изучим некоторые его следствия.

Чтобы доказать, что для LR(/e)-rpaMMaTHKH алгоритм 5.7 правильно осуществляет разбор, надо значительно развить теорию LR()-TpaMMaTHK. Убедимся сначала в том, что из определения LR(fe)-rpaMMaTHKH фактически вытекают наши интуитивные представления о том, какой должна быть детерминированно право-анализируемая грамматика. Пусть дана такая правовыводимая цепочка aw пополненной ЕН(/г)-грамматнки, что aAwfiW, Покажем, что после чтения ар и FIRST([2/) не может быть никаких недоразумений по поводу

(1) позиции правого конца основы,

(2) позиции левого конца основы,

(3) свертки, которую нужно сделать для данной выделенной основы.

(1) Допустим, что существует другая правовыводимая цепочка гфу, для которой FlRSTfe(i/) FIRSTfc(tcj), но у можно записать Б виде У1У2У3, где В- f/g -правило и apf/Bf/g -правовыводимая цепочка, т. с. Sapf/Sf/g apf/jf/a/;,. Такой случай явно исключается определением Ы(/г)-грамматики. Это станет очевидным, если положить в этом определении х= у и yBapyiB. Правый конец основы мог бы оказаться левее конца цепочки р, т. е. могла бы найтись другая правовыводимая цепочка yBvy, для которой S-Уз-правило, FlRSTfc( )-FIRSTfc(i£i) и yBvy У1У2У = У- Этот случай тоже исключается, если в определении LR(fe)-rpaMMaTHKH положить уВ=уВ и x-vy,

(2) Допустим теперь, что положение правого конца основы правовыводимой цепочки известно, но есть еще сомнения относительно левого конца. Иначе говоря, допустим, чтоаЛсеи аЛ/- такие правовыводимые цепочки, что FIRSTj(cC) = FIRST(f/) и o.Awaw, аАу,ау = а{у. Однако в LR(ft)-oпpeдeлeнии требуется, чтобы было аЛ аЛ, так чторр и Л Л. Поэтому левый конец основы определяется однозначно.

(3) Недоразумений типа (3) тоже не может быть, потому что, как уже отмечалось, Л -Л. Таким образом, нетерминал, которым надо заменить основу, всегда определяется однозначно.

Дадим теперь несколько примеров LR- и пе LR-грамматнк.

Пример 5.24. Пусть - праволинейная грамматика с правилами

SC\D CaC\b DaD\c

Покажем, что Gj-LR(])-rpaMMaTHKa i). *) На самом деле это ЬК(0)-грамматика.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.004