А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
Почему? Решение. Можно предполагать, что все процедуры вызываются при b=true. 15.3. Алгоритм разбора для LL(1)-грамматик В этом разделе мы рассмотрим ещё один метод проверки выводимо- сти в КС-грамматике, называемый по традиции LL(1)-разбором. Вот его идея в одной фразе: можно считать, что в процессе вывода мы всегда заменяем самый левый нетерминал и нужно лишь выбрать одно из правил; если нам повезёт с грамматикой, то выбрать правило мож- но, глядя на первый символ выводимого из этого нетерминала слова. Говоря более формально, дадим такое Определение. Левым выводом (слова в грамматике) называется вы- вод, в котором на каждом шаге замене подвергается самый левый из нетерминалов. 15.3. Алгоритм разбора для LL(1)-грамматик 287 15.3.1. Для каждого выводимого слова (из терминалов) существует его левый вывод. Решение. Различные нетерминалы заменяются независимо; если в процессе вывода появилось слово . . . 𝐾 . . . 𝐿 . . ., где 𝐾, 𝐿 | нетермина- лы, то замены 𝐾 и 𝐿 можно производить в любом порядке. Поэтому можно перестроить вывод так, чтобы стоящий левее нетерминал заме- нялся раньше. (Формально говоря, надо доказывать индукцией по дли- не вывода такой факт: если из некоторого нетерминала 𝐾 выводится некоторое слово 𝐴, то существует левый вывод 𝐴 из 𝐾.) 15.3.2. В грамматике с 4 правилами (1) E → (2) E → TE (3) T → (E) (4) T → [E] найдите левый вывод слова 𝐴=[()([ ])] и докажите, что он единствен. Решение. На первом шаге можно применить только правило (2): E → TE Что будет дальше с T? Так как слово 𝐴 начинается на [, то может примениться только правило (4): E → TE → [E]E Первое E должно замениться на TE (иначе вторым символом была бы скобка ]): E → TE → [E]E → [TE]E и T должно заменяться по (3): E → TE → [E]E → [TE]E → [(E)E]E Далее первое E должно замениться на пустое слово (иначе третьей бук- вой слова будет ( или [ | только на эти символы может начинаться слово, выводимое из T): E → TE → [E]E → [TE]E → [(E)E]E → [()E]E и далее . . . → [()TE]E → [()(E)E]E → [()(TE)E]E → [()([E]E)E]E → → [()([ ]E)E]E → [()([ ])E]E → [()([ ])]E → [()([ ])] 288 15. Контекстно-свободные грамматики Что требуется от грамматики, чтобы такой метод поиска левого вывода был применим? Пусть, например, на очередном шаге самым левым нетерминалом оказался нетерминал 𝐾, т. е. мы имеем слово ви- да 𝐴𝐾𝑈, где 𝐴 | слово из терминалов, а 𝑈 | слово из терминалов и нетерминалов. Пусть в грамматике есть правила 𝐾 → 𝐿𝑀𝑁 𝐾 → 𝑃 𝑄 𝐾 → 𝑅 Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор, глядя на первый символ той части входного слова, которая выводится из 𝐾𝑈. Рассмотрим множество Нач(𝐿𝑀𝑁) тех терминалов, с которых на- чинаются непустые слова, выводимые из 𝐿𝑀𝑁. (Это множество равно Нач(𝐿), объединённому с Нач(𝑀), если из 𝐿 выводится пустое слово, а также с Нач(𝑁), если из 𝐿 и из 𝑀 выводится пустое слово.) Что- бы описанный метод был применим, надо, чтобы Нач(𝐿𝑀𝑁), Нач(𝑃 𝑄) и Нач(𝑅) не пересекались. Но этого мало. Ведь может быть так, на- пример, что из 𝐿𝑀𝑁 будет выведено пустое слово, а из слова 𝑈 будет выведено слово, начинающееся на букву из Нач(𝑃 𝑄). Следующие опре- деления учитывают эту проблему. Напомним, что определение выводимости в КС-грамматике было да- но только для слова из терминалов. Оно очевидным образом обобщается на случай слов из терминалов и нетерминалов. Можно также говорить о выводимости одного слова (содержащего терминалы и нетерминалы) из другого. (Если говорится о выводимости слова без указания того, откуда оно выводится, то всегда подразумевается выводимость в грам- матике, т. е. выводимость из начального нетерминала.) Для каждого слова 𝑋 из терминалов и нетерминалов через Нач(𝑋) обозначаем множество всех терминалов, с которых начинаются непу- стые слова из терминалов, выводимые из 𝑋. (В случае, если из любого нетерминала выводится хоть одно слово из терминалов, не играет роли, рассматриваем ли мы при определении Нач(𝑋) слова только из терми- налов или любые слова. Мы будем предполагать далее, что это условие выполнено.) Для каждого нетерминала 𝐾 через Послед(𝐾) обозначим множество терминалов, которые встречаются в выводимых (в грамматике) словах сразу же за 𝐾. (Не смешивать с Посл(𝐾) предыдущего раздела!) Кроме того, в Послед(𝐾) включается символ EOI, если существует выводимое слово, оканчивающееся на 𝐾. 15.3. Алгоритм разбора для LL(1)-грамматик 289 Для каждого правила 𝐾 → 𝑉 (где 𝐾 | нетерминал, 𝑉 | слово, содержащее терминалы и нетерми- налы) определим множество направляющих терминалов, обозначаемое Напр(𝐾 → 𝑉 ). По определению оно равно Нач(𝑉 ), к которому добавле- но Послед(𝐾), если из 𝑉 выводится пустое слово. Определение. Грамматика называется LL(1)-грамматикой, если для любых правил 𝐾 → 𝑉 и 𝐾 → 𝑊 с одинаковыми левыми частями мно- жества Напр(𝐾 → 𝑉 ) и Напр(𝐾 → 𝑊 ) не пересекаются. 15.3.3. Является ли грамматика K → K # K → (выводимыми словами являются последовательности диезов) LL(1)- грамматикой? Решение. Нет: символ # принадлежит множествам направляющих символов для обоих правил (для второго | поскольку # принадлежит Послед(𝐾)). 15.3.4. Напишите LL(1)-грамматику для того же языка. Решение. K → # K K → Как говорят, «леворекурсивное» правило заменено на «праворекур- сивное». Следующая задача показывает, что для LL(1)-грамматики суще- ствует не более одного возможного продолжения левого вывода. 15.3.5. Пусть дано выводимое в LL(1)-грамматике слово 𝑋, в ко- тором выделен самый левый нетерминал 𝐾: 𝑋 = 𝐴𝐾𝑆, где 𝐴 | слово из терминалов, 𝑆 | слово из терминалов и нетерминалов. Пусть суще- ствуют два различных правила грамматики с нетерминалом 𝐾 в левой части, и мы применили их к выделенному в 𝑋 нетерминалу 𝐾, затем продолжили вывод и в конце концов получили два слова из терминалов, начинающихся на 𝐴. Докажите, что в этих словах за началом 𝐴 идут разные буквы. (Здесь к числу букв мы относим EOI.) 290 15. Контекстно-свободные грамматики Решение. Эти буквы принадлежат направляющим множествам раз- личных правил. 15.3.6. Докажите, что если слово выводимо в LL(1)-грамматике, то его левый вывод единствен. Решение. Предыдущая задача показывает, что на каждом шаге ле- вый вывод продолжается однозначно. 15.3.7. Грамматика называется леворекурсивной, если из некоторо- го нетерминала 𝐾 выводится слово, начинающееся с 𝐾, но не совпада- ющее с ним. Докажите, что леворекурсивная грамматика, в которой из каждого нетерминала выводится хотя бы одно непустое слово из тер- миналов и для каждого нетерминала существует вывод (начинающий- ся с начального нетерминала), в котором он встречается, не является LL(1)-грамматикой. Решение. Пусть из 𝐾 выводится 𝐾𝑈, где 𝐾 | нетерминал, а 𝑈 | непустое слово. Можно считать, что это левый вывод (другие нетерми- налы можно не заменять). Рассмотрим вывод 𝐾 𝐾𝑈 𝐾𝑈𝑈 . . . (знак обозначает несколько шагов вывода) и левый вывод 𝐾 𝐴, где 𝐴 | непустое слово из терминалов. На каком-то шаге второй вы- вод отклоняется от первого, а между тем по обоим путям может быть получено слово, начинающееся на 𝐴 (в первом случае это возможно, так как сохраняется нетерминал 𝐾, который может впоследствии быть за- менён на 𝐴). Это противоречит возможности однозначного определе- ния правила, применяемого на очередном шаге поиска левого вывода. (Однозначность выполняется для выводов из начального нетермина- ла, и надо воспользоваться тем, что 𝐾 по предположению встречается в таком выводе.) Таким образом, к леворекурсивным грамматикам (кроме тривиаль- ных случаев) LL(1)-метод неприменим. Их приходится преобразовы- вать в эквивалентные LL(1)-грамматики | или пользоваться другими методами распознавания. 15.3.8. Используя сказанное, постройте алгоритм проверки выво- димости слова из терминалов в LL(1)-грамматике. Решение. Мы следуем описанному выше методу поиска левого вы- вода, храня лишь часть слова, находящуюся правее уже прочитанной 15.3. Алгоритм разбора для LL(1)-грамматик 291 части входного слова. Другими словами, мы храним слово S из терми- налов и нетерминалов, обладающее такими свойствами (прочитанную часть входа обозначаем через A): 1) слово AS выводимо в грамматике; 2) любой левый вывод входного слова проходит через стадию AS Эти свойства вместе будем обозначать «(И)». Вначале A пусто, а S состоит из единственного символа | началь- ного нетерминала. Если в некоторый момент S начинается на терминал t и t = Next, то можно выполнить команду Move и удалить символ t, являющийся начальным в S, поскольку при этом AS не меняется. Если S начинается на терминал t и t ̸= Next, то входное слово не- выводимо | ибо по условию любой его вывод должен проходить через AS. (Это же справедливо и в случае Next = EOI.) Если S пусто, то из условия (И) следует, что входное слово выводимо тогда и только тогда, когда Next = EOI. Остаётся случай, когда S начинается с некоторого нетерминала K. По доказанному выше все левые выводы из S слов, начинающихся на символ Next, начинаются с применения к S одного и того же правила | того, для которого Next принадлежит направляющему множеству. Если таких правил нет, то входное слово невыводимо. Если такое правило есть, то нужно применить его к первому символу слова S | при этом свойство (И) не нарушится. Приходим к такому алгоритму: s := пустое слово; error := false; {error => входное слово невыводимо;} {not error => (И)} while (not error) and not ((Next=EOI) and (S пусто)) do begin if (S начинается на терминал, равный Next) then begin Move; удалить из S первый символ; end else if (S начинается на терминал, не равный Next) then begin error := true; end else if (S пусто) and (Next <> EOI) then begin error := true; end else if (S начинается на нетерминал и Next входит в направляющее множество одного из правил для этого нетерминала) then begin применить это правило 292 15. Контекстно-свободные грамматики end else if (S начинается на нетерминал и Next не входит в направляющее множество ни одного из правил для этого нетерминала) then begin error := true; end else begin {так не бывает} end; end; {входное слово выводимо <=> not error} Алгоритм заканчивает работу, поскольку при появлении терминала в начале слова S происходит чтение со входа или остановка, а бесконеч- ный цикл сменяющих друг друга нетерминалов в начале S означал бы, что грамматика леворекурсивна. (А мы можем предполагать, согласно предыдущей задаче, что это не так: нетерминалы, не встречающиеся в выводах, а также нетерминалы, из которых не выводится непустого слова, несложно удалить из грамматики.) Замечания. ∙ Приведённый алгоритм использует S как стек (все действия про- изводятся с левого конца). ∙ Действия двух последних вариантов внутри цикла не приводят к чтению очередного символа со входа, поэтому их можно зара- нее предвычислить для каждого нетерминала и каждого символа Next. После этого на каждом шаге цикла будет читаться очеред- ной символ входа. ∙ При практической реализации удобно составить таблицу, в ко- торой записаны варианты действий в зависимости от входного символа и первого символа S, и небольшую программу, выполня- ющую действия в соответствии с этой таблицей. 15.3.9. При проверке того, относится ли данная грамматика к типу LL(1), необходимо вычислить Послед(𝑇 ) и Нач(𝑇 ) для всех нетермина- лов 𝑇 . Как это сделать? Решение. Пусть, например, в грамматике есть правило 𝐾 → 𝐿 𝑀 𝑁. Тогда Нач (𝐿) ⊂ Нач (𝐾), Нач (𝑀) ⊂ Нач (𝐾), если из 𝐿 выводимо пустое слово, Нач (𝑁) ⊂ Нач (𝐾), если из 𝐿 и 𝑀 выводимо пустое слово, 15.3. Алгоритм разбора для LL(1)-грамматик 293 Послед (𝐾) ⊂ Послед (𝑁), Послед (𝐾) ⊂ Послед (𝑀), если из 𝑁 выводимо пустое слово, Послед (𝐾) ⊂ Послед (𝐿), если из 𝑀 и 𝑁 выводимо пустое слово, Нач (𝑁) ⊂ Послед (𝑀), Нач (𝑀) ⊂ Послед (𝐿), Нач (𝑁) ⊂ Послед (𝐿), если из 𝑀 выводимо пустое слово. Подобные правила позволяют шаг за шагом порождать множества Нач(𝑇 ), а затем и Послед(𝑇 ), для всех терминалов и нетерминалов 𝑇 . При этом началом служит EOI ∈ Послед (𝐾) для начального нетерминала 𝐾 и 𝑧 ∈ Нач (𝑧) для любого терминала 𝑧. Порождение заканчивается, когда приме- нение правил перестаёт давать новые элементы множеств Нач(𝑇 ) и Послед(𝑇 ). 16. СИНТАКСИЧЕСКИЙ РАЗБОР СЛЕВА НАПРАВО (LR) Сейчас мы рассмотрим ещё один метод синтаксического разбора, называемый LR(1)-разбором, а также некоторые упрощённые его ва- рианты. 16.1. LR-процессы Два отличия LR(1)-разбора от LL(1)-разбора: во-первых, строится не левый вывод, а правый, во-вторых, он строится не с начала, а с конца. (Вывод в КС-грамматике называется правым, если на каждом шаге замене подвергается самый правый нетерминал.) 16.1.1. Докажите, что если слово, состоящее из терминалов, выво- димо, то оно имеет правый вывод. Нам будет удобно смотреть на правый вывод «задом наперёд». Опре- делим понятие LR-процесса над словом 𝐴. В этом процессе, помимо 𝐴, будет участвовать и другое слово 𝑆, которое может содержать как тер- миналы, так и нетерминалы. Вначале слово 𝑆 пусто. В ходе LR-процесса разрешены два вида действий: (1) можно перенести первый символ слова 𝐴 (его называют очередным символом и обозначают Next) в конец слова 𝑆, удалив его из 𝐴 (это действие называют сдвигом); (2) если правая часть одного из правил грамматики оказалась концом слова 𝑆, то разрешается заменить её на нетерминал, стоящий в ле- вой части этого правила; при этом слово 𝐴 не меняется. (Это дей- ствие называют свёрткой, или приведением.) Отметим, что LR-процесс не является детерминированным: в одной и той же ситуации могут быть разрешены разные действия. 16.1. LR-процессы 295 Говорят, что LR-процесс на слове 𝐴 успешно завершается, если сло- во 𝐴 становится пустым, а в слове 𝑆 остаётся единственный нетерми- нал | начальный нетерминал грамматики. 16.1.2. Докажите, что для любого слова 𝐴 (из терминалов) успеш- но завершающийся LR-процесс существует тогда и только тогда, когда слово 𝐴 выводимо в грамматике. В ходе доказательства установите вза- имно однозначное соответствие между правыми выводами и успешно завершающимися LR-процессами. Решение. При сдвиге слово 𝑆𝐴 не меняется, при свёртке слово 𝑆𝐴 подвергается преобразованию, обратному шагу вывода. Этот вывод будет правым, так как сворачивается конец 𝑆, а в 𝐴 все символы | терминальные. Таким образом, каждому LR-процессу соответствует правый вывод. Обратное соответствие: пусть дан правый вывод. Пред- ставим себе, что за последним нетерминалом в слове стоит перегород- ка. Применив к этому нетерминалу правило грамматики, мы должны сдвинуть перегородку влево (если правая часть правила кончается на терминал). Разбивая этот сдвиг на отдельные шаги, получим процесс, в точности обратный LR-процессу. Поскольку в ходе LR-процесса все изменения в слове 𝑆 происходят с правого конца, слово 𝑆 называют стеком LR-процесса. Задача построения правого вывода для данного слова сводится, та- ким образом, к правильному выбору очередного шага LR-процесса. Нам нужно решить, будем ли мы делать сдвиг или свёртку, и если свёртку, то по какому правилу | ведь подходящих правил может быть несколько. В LR(1)-алгоритме это решение принимается на основе 𝑆 и первого символа слова 𝐴; если используется только 𝑆, то говорят о LR(0)-алгоритме. (Точные определения см. ниже.) Пусть фиксирована грамматика, в которой из любого нетерминала можно вывести какое-либо слово из терминалов. (Это ограничение мы будет всегда предполагать выполненным.) Пусть K → U | одно из правил грамматики (K | нетерминал, U | слово из терминалов и нетерминалов). Определим множество слов (из терминалов и нетерминалов), называемое левым контекстом правила K → U. (Обозначение: ЛевКонт(K → U).) По определению в него входят все слова, которые являются содержимым стека непосредственно перед свёрткой U в K в ходе некоторого успешно завершающегося LR-про- цесса. 16.1.3. Переформулируйте это определение на языке правых выво- дов. 296 16. Синтаксический разбор слева направо (LR) Решение. Рассмотрим все правые выводы вида ⟨ начальный нетерминал⟩ XKA → XUA, где A | слово из терминалов, X | слово из терминалов и нетерминалов. Все возникающие при этом слова XU и образуют левый контекст прави- ла K → U. Чтобы убедиться в этом, следует вспомнить, что мы предпо- лагаем, что из любого нетерминала можно вывести какое-то слово из терминалов, так что правый вывод слова XUA может быть продолжен до правого вывода какого-то слова из терминалов. 16.1.4. Все слова из ЛевКонт(K → U) кончаются, очевидно, на U. До- кажите, что если у всех них этот конец U отбросить, то полученное множество слов не зависит от того, какое из правил для нетерминала K выбрано. (Это множество обозначается Лев(K).) Решение. Из предыдущей задачи ясно, что Лев(K) | это всё, что может появиться в правых выводах левее самого правого нетермина- ла K. 16.1.5. Докажите, что в предыдущей фразе можно отбросить слова «самого правого»: Лев(K) | это всё то, что может появляться в правых выводах левее любого вхождения нетерминала K. Решение. Продолжив построение правого вывода, все нетерминалы справа от K можно заменить на терминалы (а слева от K при этом ничего не изменится). 16.1.6. Постройте грамматику, содержащую для каждого нетер- минала K исходной грамматики нетерминал ⟨ЛевK⟩, причём следую- щее свойство должно выполняться для любого нетерминала K исходной грамматики: в новой грамматике из ⟨ЛевK⟩ выводимы все элементы Лев(K) и только они. (При этом терминалы и нетерминалы исходной грамматики являются терминалами новой.) Решение. Пусть P | начальный нетерминал грамматики. Тогда в новой грамматике будет правило ⟨ ЛевP⟩ → (пустое слово) Для каждого правила исходной грамматики, например, правила K → L t M N (L, M, N | нетерминалы, t | терминал), 16.1. LR-процессы 297 в новую грамматику мы добавим правила ⟨ ЛевL⟩ → ⟨ЛевK⟩ ⟨ ЛевM⟩ → ⟨ЛевK⟩ L t ⟨ ЛевN⟩ → ⟨ЛевK⟩ L t M и аналогично поступим с другими правилами. Смысл новых правил таков: пустое слово может появиться слева от P; если слово X может появиться слева от K, то X может появиться слева от L, XLt может по- явиться слева от M, XLtM | слева от N. Индукцией по длине правого вывода легко проверить, что всё, что может появиться слева от како- го-то нетерминала, появляется в соответствии с этими правилами. |