А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
16.1.7. Почему в предыдущей задаче важно, что мы рассматриваем только правые выводы? Ответ. В противном случае следовало бы учитывать преобразова- ния, происходящие внутри слова, стоящего слева от K. 16.1.8. Для данной грамматики постройте алгоритм, который по любому слову выясняет, каким из множеств Лев(K) оно принадлежит. (Замечание для знатоков. Существование такого алгоритма | и да- же конечного автомата, то есть индуктивного расширения с конечным числом значений, см. раздел 1.3 , | вытекает из предыдущей задачи, так как построенная в ней грамматика имеет специальный вид: в пра- вых частях всего один нетерминал, причём он стоит у левого края. Тем не менее мы приведём явное построение.) Решение. Будем называть ситуацией данной грамматики одно из её правил, в правой части которого отмечена одна из позиций (до первой буквы, между первой и второй буквой, . . . , после последней буквы). Например, правило K → L t M N (K, L, M, N | нетерминалы, t | терминал) порождает пять ситуаций K → L t M N K → L t M N K → L t M N K → L t M N K → L t M N (позиция указывается знаком подчёркивания). Будем говорить, что слово S согласовано с ситуацией K → U V, если S кончается на U, то есть S = TU при некотором T, и, кроме того, T при- надлежит Лев(K). (Смысл этого определения примерно таков: в стеке S 298 16. Синтаксический разбор слева направо (LR) подготовлена часть U для будущей свёртки UV в K.) В этих терминах ЛевКонт(K → X) | это множество всех слов, согласованных с ситуацией K → X , а Лев(K) | это множество всех слов, согласованных с ситуацией K → X (где K → X | любое правило для нетерминала K). Эквивалентное определение в терминах LR-процесса: S согласовано с ситуацией K → U V, если существует успешный LR-процесс, в котором события развиваются так: ∙ в ходе процесса в стеке появляется слово S, и оно оканчивается на U; ∙ некоторое время S не затрагивается, а справа от него появляет- ся V; ∙ UV сворачивается в K; ∙ процесс продолжается и успешно завершается. 16.1.9. Докажите эквивалентность этих определений. [Указание. Если S = TU и T принадлежит Лев(K), то можно получить в стеке сначала T, потом U, потом V, потом свернуть UV в K и затем успешно завершить процесс. (Мы используем несколько раз тот факт, что из любого нетерминала что-то да выводится: благодаря этому мы можем добавить в стек любое слово.)] Наша цель | построение алгоритма, распознающего принадлеж- ность произвольного слова к Лев(K). Рассмотрим функцию, сопоста- вляющую с каждым словом S (из терминалов и нетерминалов) множе- ство всех согласованных с ним ситуаций. Это множество назовём со- стоянием, соответствующим слову S. Будем обозначать его Сост(S). Достаточно показать, что функция Сост(S) индуктивна, то есть что значение Сост(SJ), где J | терминал или нетерминал, может быть вы- числено, если известно Сост(S) и символ J. (Мы видели ранее, как при- надлежность к Лев(K) выражается в терминах этой функции.) Значение Сост(SJ) вычисляется по таким правилам: (1) Если слово S согласовано с ситуацией K → U V, причём слово V начинается на букву J, то есть V = JW, то SJ согла- совано с ситуацией K → UJ W. 16.1. LR-процессы 299 Это правило полностью определяет все ситуации с непустой левой половиной (то есть не начинающиеся с подчёркивания), согласованные с SJ. Осталось определить, для каких нетерминалов K слово SJ принад- лежит Лев(K). Это делается по двум правилам: (2) Если ситуация L → U V согласована с SJ (согласно прави- лу (1)), а V начинается на нетерминал K, то SJ принадлежит Лев(K). (3) Если SJ входит в Лев(L) для некоторого L, причём L → → V | правило грамматики и V начинается на нетерминал K, то SJ принадлежит Лев(K). Заметим, что правило (3) можно рассматривать как аналог правила (2): в указанных в (3) предположениях ситуация L → V согласована с SJ, а V начинается на нетерминал K. Корректность этих правил в общем-то очевидна, если хорошень- ко подумать. Единственное, что требует некоторых пояснений | это то, почему с помощью правил (2) и (3) обнаружатся все терминалы K, для которых SJ принадлежит Лев(K). Попытаемся это объяснить. Рас- смотрим правый вывод, в котором SJ стоит слева от K. Откуда мог взяться в нём нетерминал K? Если правило, которое его породило, по- родило также и конец слова SJ, то принадлежность SJ к Лев(K) будет обнаружена по правилу (2). Если же K было первой буквой слова, поро- ждённого каким-то другим нетерминалом L, то | благодаря правилу (3) | достаточно установить принадлежность SJ к Лев(L). Осталось применить те же рассуждения к L и так далее. В терминах LR-процесса то же самое можно сказать так. Сначала нетерминал K может участвовать в нескольких свёртках, не затраги- вающих SJ (они соответствуют применению правила (3) ), но затем он обязан подвергнуться свёртке, затрагивающей SJ (что соответствует применению правила (2) ). Осталось выяснить, какие ситуации согласованы с пустым словом, то есть для каких нетерминалов K пустое слово принадлежит Лев(K). Это определяется по следующим правилам: (1) начальный нетерминал таков; (2) если K таков и K → V | правило грамматики, причём слово V начинается с нетерминала L, то и L таков. 300 16. Синтаксический разбор слева направо (LR) 16.1.10. Проделайте описанный анализ для грамматики E → E + T E → T T → T * F T → F F → x F → ( E ) (задающей тот же язык, что и грамматика примера 3, с. 272 ). Решение. Множества Сост(S) для различных S приведены в таблице на с. 301 . Знак равенства означает, что множества ситуаций, являющи- еся значениями функции Сост(S) на словах, стоящих слева и справа от знака равенства, одинаковы. Правило определения Сост(SJ), если известны Сост(S) и J (здесь S | слово из терминалов и нетерминалов, J | терминал или нетерминал), таково: надо найти Сост(S) в правой колонке, взять соответствую- щее ему слово T в левой колонке, приписать к нему J и взять множество, стоящее напротив слова TJ (если слово TJ в та- блице отсутствует, то Сост(SJ) пусто). 16.2. LR(0)-грамматики Напомним, что наша основная цель | это поиск вывода заданного слова, или, другими словами, поиск успешного LR-процесса над ним. Во всех рассматриваемых нами грамматиках успешный LR-процесс (над данным словом) единствен. Искать этот единственный успешный про- цесс мы будем постепенно: в каждый момент мы смотрим, какой шаг возможен следующим. Для этого на грамматику надо наложить допол- нительные требования, и сейчас мы рассмотрим простейший случай так называемых LR(0)-грамматик. Мы уже знаем: (1) В успешном LR-процессе возможна свёртка по правилу K → U при содержимом стека S тогда и только тогда, когда S принадлежит ЛевКонт(K → U) или, другими словами, когда слово S согласовано с ситуацией K → U . 16.2. LR(0)-грамматики 301 Слово S Сост(S) пустое E → E+T E → T T → T*F T → F F → x F → (E) E E → E +T T E → T T → T *F F T → F x F → x ( F → ( E) E → E+T E → T T → T*F T → F F → x F → (E) E+ E → E+ T T → T*F T → F F → x F → (E) T* T → T* F F → x F → (E) (E F → (E ) E → E +T (T = T (F = F (x = x (( = ( E+T E → E+T T → T *F E+F = F E+x = x E+( = ( T*F T → T*F T*x = x T*( = ( (E) F → (E) (E+ = E+ E+T* = T* К задаче 16.1.10 302 16. Синтаксический разбор слева направо (LR) Аналогичное утверждение про сдвиг гласит: (2) В успешном LR-процессе при содержимом стека S воз- можен сдвиг с очередным символом a тогда и только тогда, когда S согласовано с некоторой ситуацией K → U aV. 16.2.1. Докажите это. [Указание. Пусть произошёл сдвиг и к стеку S добавилась буква a. Рассмотрите первую свёртку, затрагивающую эту букву.] Рассмотрим некоторую грамматику и произвольное слово S из тер- миналов и нетерминалов. Если множество Сост(S) содержит ситуацию, в которой справа от подчёркивания стоит терминал, то говорят, что для слова S возможен сдвиг. Если в Сост(S) есть ситуация, в которой справа от подчёркивания ничего нет, то говорят, что для слова S воз- можна свёртка (по соответствующему правилу). Говорят, что для сло- ва S возникает конфликт типа сдвиг/свёртка, если возможны и сдвиг, и свёртка. Говорят, что для слова S возникает конфликт типа свёрт- ка/свёртка, если есть несколько правил, по которым возможна свёртка. Грамматика называется LR(0)-грамматикой, если в ней нет кон- фликтов типа сдвиг/свёртка и свёртка/свёртка ни для одного слова S. 16.2.2. Является ли приведённая выше грамматика LR(0)-грамма- тикой? Решение. Нет, не является. Для слов T и E+T имеются конфликты типа сдвиг/свёртка. 16.2.3. Являются ли LR(0)-грамматиками такие: (а) T → 0 T → T1 T → TT2 T → TTT3 (б) T → 0 T → 1T T → 2TT T → 3TTT Решение. Являются, см. таблицы на с. 303 { 304 (конфликтов нет). Эта задача показывает, что LR(0)-грамматики могут быть как ле- ворекурсивными, так и праворекурсивными. 16.2.4. Пусть дана LR(0)-грамматика. Докажите, что у любого сло- ва существует не более одного правого вывода. Постройте алгоритм проверки выводимости в LR(0)-грамматике. 16.2. LR(0)-грамматики 303 Слово S Сост(S) пустое Т → 0 T → T1 T → TT2 T → TTT3 0 Т → 0 Т Т → Т 1 T → T T2 T → T TT3 Т → 0 T → T1 T → TT2 T → TTT3 T1 T → T1 TT T → TT 2 T → TT T3 T → T 1 T → T T2 T → T TT3 T → 0 T → T1 T → TT2 T → TTT3 TT2 T → TT2 TTT T → TTT 3 T → TT 2 T → TT T3 T → T 1 T → T T2 T → T TT3 Т → 0 T → T1 T → TT2 T → TTT3 TT0 = 0 TTT3 T → TTT3 TTT2 = TT2 TTTT = TTT TTT0 = 0 (а) Слово S Сост(S) пустое T → 0 T → 1Т T → 2ТТ T → 3ТТТ 0 Т → 0 1 Т → 1 T T → 0 T → 1Т T → 2ТТ T → 3ТТТ 2 T → 2 TT T → 0 T → 1Т T → 2ТТ T → 3ТТТ 3 T → 3 TTT T → 0 T → 1Т T → 2ТТ T → 3ТТТ (б), начало К задаче 16.2.3 304 16. Синтаксический разбор слева направо (LR) Слово S Сост(S) 1T T → 1T 10 = 0 11 = 1 12 = 2 13 = 3 2T T → 2T T T → 0 T → 1Т T → 2ТТ T → 3ТТТ 20 = 0 21 = 1 22 = 2 23 = 3 3T T → 3T TT T → 0 T → 1Т T → 2ТТ T → 3ТТТ 30 = 0 31 = 1 32 = 2 33 = 3 2TT T → 2TT 2T0 = 0 2T1 = 1 2T2 = 2 2T3 = 3 3TT T → 3TT T T → 0 T → 1Т T → 2ТТ T → 3ТТТ 3T0 = 0 3T1 = 1 3T2 = 2 3T3 = 3 3TTT T → 3TTT 3TT0 = 0 3TT1 = 1 3TT2 = 2 3TT3 = 3 (б), окончание 16.2. LR(0)-грамматики 305 Решение. Пусть дано произвольное слово. Будем строить LR-про- цесс над ним по шагам. Пусть текущее состояние стека LR-процесса равно S. Нам надо решить, делать сдвиг или свёртку (и если свёрт- ку, то по какому правилу). Согласно определению LR(0)-граммати- ки, в нашем состоянии S возможен либо только сдвиг, либо толь- ко свёртка (причём лишь по одному правилу). Таким образом, поиск возможных продолжений LR-процесса происходит детерминированно (на каждом шаге можно определить, какое действие только и воз- можно). 16.2.5. Что произойдёт, если анализируемое слово не имеет вывода в данной грамматике? Ответ. Либо на некотором шаге не будет возможен ни сдвиг, ни свёртка, либо все возможные сдвиги будет иметь неподходящий оче- редной символ. Замечания. 1. При реализации этого алгоритма нет необходимости каждый раз заново вычислять множество Сост(S) для текущего значе- ния S. Эти множества можно также хранить в стеке (в каждый момент хранятся множества Сост(T) для всех начал T текущего слова S). 2. На самом деле само слово S можно не хранить | достаточно хранить множества ситуаций Сост(T) для всех его начал T (включая само S). В алгоритме проверки выводимости в LR(0)-грамматике мы ис- пользуем не всю информацию, которую могли бы. В этом алгорит- ме для каждого состояния известно заранее, что в нём возможен то- лько сдвиг или только свёртка (причём в последнем случае извест- но, по какому правилу). Более изощрённый алгоритм мог бы при- нимать решение о выборе между сдвигом и свёрткой, посмотрев на очередной символ (Next). Глядя на состояние, можно сказать, при каких значениях Next возможен сдвиг (это те терминалы, ко- торые в ситуациях этого состояния стоят непосредственно за под- чёркиванием). Сложнее воспользоваться информацией о символе Next для решения вопроса о том, возможна ли свёртка. Для этого есть упрощённый метод (грамматики, к которым он применим, называ- ют SLR(1)-грамматиками [сокращение от Simple LR(1)]) и полный метод (более сложный, но использующий всю возможную информа- цию; грамматики, к которым он применим, называют LR(1)-грам- матиками). Есть и промежуточный класс грамматик, называемый LALR(1). 306 16. Синтаксический разбор слева направо (LR) 16.3. SLR(1)-грамматики Напомним, что для любого нетерминала K мы определяли (с. 288 ) множество Послед(K) тех терминалов, которые могут стоять непосред- ственно за K в выводимом (из начального нетерминала) слове; в это мно- жество добавляют также символ EOI, если нетерминал K может стоять в конце выводимого слова. 16.3.1. Докажите, что если в данный момент LR-процесса послед- ний символ стека S равен K, причём процесс этот может в дальнейшем успешно завершиться, то Next принадлежит Послед(K). Решение. Этот факт является непосредственным следствием опре- деления (вспомним соответствие между правыми выводами и LR-про- цессами). Рассмотрим некоторую грамматику, произвольное слово S из терми- налов и нетерминалов и терминал x. Если множество Сост(S) содержит ситуацию, в которой справа от подчёркивания стоит терминал x, то говорят, что для пары ⟨S, x⟩ возможен сдвиг. Если в Сост(S) есть си- туация K → U , причём x принадлежит Послед(K), то говорят, что для пары ⟨S, x⟩ SLR(1)-возможна свёртка (по правилу K → U). Говорят, что для пары ⟨S, x⟩ возникает SLR(1)-конфликт типа сдвиг/свёртка, если возможны и сдвиг, и свёртка. Говорят, что для пары ⟨S, x⟩ возникает SLR(1)-конфликт типа свёртка/свёртка, если есть несколько правил, по которым возможна свёртка. Грамматика называется SLR(1)-грамматикой, если в ней нет SLR(1)-конфликтов типа сдвиг/свёртка и свёртка/свёртка ни для од- ной пары ⟨S, x⟩. 16.3.2. Пусть дана SLR(1)-грамматика. Докажите, что у любого слова существует не более одного правого вывода. Постройте алгоритм проверки выводимости в SLR(1)-грамматике. Решение. Аналогично случаю LR(0)-грамматик, только при выборе между сдвигом и свёрткой учитывается очередной символ (Next). 16.3.3. Проверьте, является ли приведённая выше на с. 300 грамма- тика (с нетерминалами E, T и F) SLR(1)-грамматикой. Решение. Да, является, так как оба конфликта, мешающие ей быть LR(0)-грамматикой, разрешаются с учётом очередного символа: и для слова T, и для слова E+T сдвиг возможен только при Next = *, а символ * не принадлежит ни Послед(E) = {EOI, +, )}, ни Послед(T) = {EOI, +, *, )}, и поэтому при Next = * свёртка невозможна. 16.4. LR(1)-грамматики, LALR(1)-грамматики 307 16.4. LR(1)-грамматики, LALR(1)-грамматики Описанный выше SLR(1)-подход используют не всю возможную ин- формацию при выяснении того, возможна ли свёртка. Именно, он от- дельно проверяет, возможна ли свёртка при данном состоянии стека S и отдельно | возможна ли свёртка по данному правилу при данном символе Next. Между тем эти проверки не являются независимыми: обе могут дать положительный ответ, но тем не менее свёртка при стеке S и очередном символе Next невозможна. В LR(1)-подходе этот недостаток устраняется. LR(1)-подход состоит вот в чём: все наши определения и утвержде- ния модифицируются так, чтобы учесть, какой символ стоит справа от разворачиваемого нетерминала (другими словами, чему равен Next при свёртке). Пусть K → U | одно из правил грамматики, а t | некоторый тер- минал или спецсимвол EOI (который мы домысливаем в конце вход- ного слова). Определим множество ЛевКонт(K → U, t) как множество всех слов, которые являются содержимым стека непосредственно пе- ред свёрткой U в K в ходе успешного LR-процесса, при условии Next = t (в момент свёртки). Если отбросить у всех слов из ЛевКонт(K → U) их конец U, то полу- чится множество всех слов, которые могут появиться в правых выводах перед нетерминалом K, за которым стоит символ t. Это множество (не зависящее от того, какое из правил K → U для нетерминала K выбрано) мы будем обозначать Лев(K, t). 16.4.1. Напишите грамматику для порождения множеств Лев(K, t). Решение. Её нетерминалами будут символы ⟨ЛевK t⟩ для каждого нетерминала K и для каждого терминала t (а также для t = EOI). Её правила таковы. Пусть P | начальный нетерминал исходной грамма- тики. Тогда в новой грамматике будет правило ⟨ ЛевP EOI⟩ → (пустое слово). Каждое правило исходной грамматики порождает несколько правил но- вой. Например, для правила K → L u M N (L, M, N | нетерминалы, u | терминал) в новую грамматику мы доба- вим правила ⟨ ЛевL u⟩ → ⟨ЛевK x⟩ 308 16. Синтаксический разбор слева направо (LR) (для всех терминалов x); ⟨ ЛевM s⟩ → ⟨ЛевK y⟩ L u (для всех s, которые могут начинать слова, выводимые из N, и для всех y, а также для всех пар s = y, если из N выводимо пустое слово); ⟨ ЛевN s⟩ → ⟨ЛевK s⟩ L u M (для всех терминалов s). 16.4.2. Как меняется определение ситуации? Решение. Ситуацией называется пара [ситуация в старом смысле, терминал или EOI] 16.4.3. Как изменится определение согласованности? Решение. Слово S из терминалов и нетерминалов согласовано с си- туацией [K → U V, t] (здесь t | терминал или EOI), если S кончается на U, то есть S = TU, и, кроме того, T принадлежит Лев(K, t). 16.4.4. Каковы правила для индуктивного вычисления множества Сост(S) ситуаций, согласованных с данным словом S? Ответ. (1) Если слово S согласовано с ситуацией [K → U V, t], причём слово V начинается на букву J, то есть V = JW, то слово SJ согласовано с ситуацией [K → UJ W, t]. Это правило полностью определяет все ситуации с непустой левой половиной (то есть не начинающиеся с подчёркивания), согласованные с SJ. Осталось определить, для каких нетерминалов K и терминалов t слово SJ принадлежит Лев(K, t). Это делается по двум правилам: |