А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 66
Текст из файла (страница 66)
Пример 4.35. Рассмотрим расширенную грамматику выражений, множества пунктов и функция сото которой представлены на рис. 4.31. Очевидно, что строка Е+ Т* является активным префиксом этой грамматики. Автомат на рис. 4.31 32З Глава 4. Синтаксический анализ Пункты как состояния НКА Недетерминированный конечный автомат АГ для распознавания активных префиксов может быть построен путем рассмотрения пунктов в качестве состояний. Существует переход из А — гт . Х)3 в А — аХ )3, помеченный Х, и переход из А — а. В)3 в  — "у, помеченный е. В таком случае с~.ояже (1) для множества пунктов (состояний М) 1 в точности представляет собой е-замыкание множества состояний НКА, определенного в разделе 3.7.1.
Таким образом, Оото (1, Х) дает переход из 1 для символа Х в ДКА, построенном из М при помощи метода построения подмножеств. При таком подходе процедура йеикт (С') на рнс. 4.33 представляет собой процедуру построения подмножества, примененную к НКА АГ, состояниями которого являются пункты.
после чтения Е + Т* будет находиться в состоянии 7. Это состояние содержит пункты Т вЂ” ~ ТвГ (Е) à — Ы Они в точности являются допустимыми пунктами для Е + Тя. Чтобы увидеть, почему это так, рассмотрим следующие три правые порождения: Е' Е' — Е Е+Т тт Е+ТвГ тт — Е+ Т*(Е) Е тт Е+Т Е+Т*Г в та Е+ТвЫ Е' =ь Е тт — Е+Т тт => Е+ТвЕ 4.6.6 Упражнения к разделу 4.6 Упражнение 4.6.1. Опишите все активные префиксы следующих грамматик: а) грамматика Я вЂ” О Я 1 ! О 1 из упражнения 4.2.2, а; ! б) грамматика 5 — Я Я+ ~ Я Я* ~ а из упражнения 4.2.1; Первое порождение показывает допустимость Т вЂ” Тя К второе — допустимость Е -+ (Е), а третье — допустимость à — Ы.
Можно показать, что других допустимых пунктов для Е + Т* не существует, хотя мы и не будем доказывать здесь этот факт. и 329 4.6. Введение в 1.К-анализ: простой 1.К 1 в) грамматика  — В (В) ~ е из упражнения 4.2.2, в. Упражнение 4.6.2. Постройте 5ЬК-множества пунктов для (расширенной) грам- матики из упражнения 4.2.1. Вычислите функцию оото для этих множеств пунк- тов.
Приведите таблицу синтаксического анализа для этой грамматики. Принад- лежит ли эта грамматика к классу БЬК? Упражнение 4.6.3. Приведите действия вашей таблицы синтаксического анализа из упражнения 4.6.2 для входной строки аа * а+. Упражнение 4.6.4. Для каждой из (расширенных) грамматик из упражнений 4.2.2, а — ж: а) постройте 5ЬК-множества пунктов и их функции бОТО; б) укажите конфликты действий в ваших множествах пунктов; в) постройте таблицы БЬК-анализа, если таковые существуют. Упражнение 4.6.5. Покажите, что грамматика  — ~ АаАЬ)ВЬВа А  — ~ е принадлежит классу ЬЬ (1), но не ВЬК (1). Упражнение 4.6.6.
Покажите, что грамматика  — э" А)А А — а принадлежит классу Я.К (1), но не 1.Ь (1).  — А;Ь; А1 ~ ау А; ~ау для1<1<и, для 1 < г, ~' < и и 1 ~ 1 Покажите, что а) С„имеет 2из — и продукций; б) С„имеет 2" + из + и множеств 1.К (0)-пунктов; !! Упражнение 4.6.7. Рассмотрим семейство грамматик С„, определяемое следующим образом: ззо Глава 4. Синтаксический анализ в) С„принадлежит классу Я.К (1).
Что говорит проведенный анализ о возможном размере ).й-анализаторов? ! Упражнение 4.6.8. Допустим, что отдельные пункты можно рассматривать как состояния недетерминнрованного конечного автомата, в то время как множества допустимых пунктов являются состояниями детерминированного конечного автомата (см. врезку "Пункты как состояния НКА" в разделе 4.6.5). Для грамматики о — Я Я+ ~ Я 5* ~ а из упражнения 4.2.1 сделайте следующее. а) Изобразите диаграмму переходов (НКА) для допустимых пунктов этой грамматики в соответствии с правилами из упомянутой врезки.
б) Примените метод построения подмножеств (алгоритм 3.20) к вашему НКА из части а. Каков размер получившегося ДКА по сравнению с множеством 1.К (О) пунктов грамматики? !! в) Покажите, что во всех случаях применение метода построения подмножеств к НКА, полученному из допустимых пунктов грамматики, дает множества ЕК (0)-пунктов. ! Упражнение 4.6.9. Ниже приведена неоднозначная грамматика Я вЂ” АЯ(Ь А — Я А(а Постройте для данной грамматики ее набор множеств ).К (О)-пунктов. Если мы попытаемся построить таблицу (.К-анализа для данной грамматики, то получим некоторые конфликты действий.
Какие именно? Предположим, что мы пытаемся использовать таблицу синтаксического анализа недетерминированно, выбирая при конфликте возможное действие. Приведите все возможные последовательности действий для входной строки аЬаЬ. 4.7 Более мощные ЕК-анализаторы В этом разделе мы расширим рассмотренные методы (,й-анализа использованием предпросмотра одного символа входного потока. Существует два различных метода. 1. Канонический 1 К, или просто (.й-метод, использующий предпросмотр символа (или символов).
Этот метод использует большое множество пунктов, именуемых (.К (1)-пунктами. ЗЗ1 4.7. Более мощные ЬК-анализаторы 2. Ьй с предпросмотром, или ЬАЬй Поо1сайеад Ь11)-метод, основанный на множестве пунктов ЬВ(0) и имеющий существенно меньше состояний, чем типичный анализатор, основанный на Ьй (1)-пунктах. Путем аккуратного добавления предпросмотров в ЬК (О)-пункты ЬАЬК позволяет работать с существенно большим количеством грамматик, чем БЬК, и при этом строить таблицы синтаксического анализа, которые не больше БЬй-таблиц. ЬАЬ — это метод, выбираемый в большинстве случаев. После рассмотрения обоих этих методов мы завершим наше обсуждение вопросом о том, каким образом можно сжать Ьй-таблицы при работе в средах с ограниченной памятью.
4.7.1 Канонические 1 К(1)-Пункты Сейчас мы представим наиболее общий метод построения таблиц Ьй синтаксического анализа для грамматики. Вспомним, что в БЬй-методе состояние г вызывает свертку в соответствии с продукцией А — а, если множество пунктов 1, содержит пункт [А — а ], а текущий входной символ а входит в го~.ьоц'(А). В некоторых ситуациях, однако, когда состояние г находится на вершине стека, допустимый префикс,Згт в стеке таков, что за ДА ни в какой правосентенциальной форме не может следовать а.
Таким образом, свертка в соответствии с продукцией А — а оказывается некорректной при входном символе а. Пример 4.36. Рассмотрим пример 4.34, в котором в состоянии 2 имелся пункт )1 — Бз соответствующий упомянутой выше продукции А — гт, а а может быть символом = из множества кои.ов(Л). Таким образом, синтаксический анализатор БЬй должен вызывать в состоянии 2 при очередном входном символе = свертку в соответствии с продукцией Л вЂ” Т (в связи с наличием в состоянии 2 пункта о' — Ь = П может также использоваться перенос).
Однако в грамматике из примера 4.34 не существует правосентенциальной формы, которая начинается с П = . Таким образом, в состоянии 2, соответствующем единственному допустимому префиксу Ь, не должна использоваться свертка этого Т, в )1. Можно хранить в состоянии больший объем информации, который позволит отбрасывать такие некорректные свертки в соответствии с продукциями А — о. Разделяя при необходимости состояния, можно добиться того, что каждое состояние Ьй-анализатора будет точно указывать, какие входные символы могут следовать за основой а, для которой возможна свертка в А. Дополнительная информация вносится в состояние путем такого переопределения пунктов, чтобы они включали в качестве второго компонента терминальный символ.
Общим видом пункта становится [А — а 13, а], где А — гг13 — продукция, а а — терминал или маркер конца входной строки 3. Такой объект называется Ьй [1)-пунктом. Здесь 1 означает длину второго компонента, именуемого ЗЗ2 Глава 4. Синтаксический анализ предлросмотром (1оока(зев) пункта." Предпросмотр не влияет на пункт вида [А - гк. Д,а], где Д не равно с, но пункт [А - о,а] приводит к свертке в соответствии с продукцией А — ск, только если очередной входной символ равен а. Таким образом, свертка в соответствии с продукцией А -+ сз применяется только при входном символе а, для которого [А — ск, а] является ЬК(1)-пунктом из состояния на вершине стека. Множество таких а всегда является подмножеством Роь1.озн (А), но может быть истинным подмножеством, как в примере 4.36.
Формально мы говорим, что 1.К (1)-пункт [А — ск Д, а] допустйм (ча!Ы) для активного префикса 7, если существует порождение Я =~ бАю =ь даДю, где ст ст 1) у=ба; 2) либо а является первым символом ю, либо ю — с, а а — 8. Пример 4.37. Рассмотрим грамматику Я вЂ” В  — а В[Ь Существует правое порождение 5 =~ ааВаЬ =~ аааВаЬ. Мы видим, что пункт тп ст [ — а В, а] допустйм для активного префикса у = ааа, если положить в приведенном выше определении Б = аа, А = В, ю = аЬ, сз = а и Д = В.
Существует также правое порождение Я =~ ВаВ =~ ВааВ. Из него видно, что пункт ст 7 "т [ — а В, й] является допустимым для активного префикса Ваа. П 4.7.2 Построение множеств 1.К(1)-Пунктов Метод построения набора множеств допустимых 1.Гс (1)-пунктов, по сути, тот же, что и для построения канонического набора множеств 1,Гс(0)-пунктов. Нам надо только модифицировать две процедуры — сьОЯже и ботО. Чтобы разобраться в новом определении операции о.оя1кд (в частности, почему Ь должно быть в р1КЗт(Да)), рассмотрим пункт вида [А — сз ВД, а] в множестве пунктов, допустимых для некоторого активного префикса у. Тогда существует правое порождение Я ~ ЬАах ~ ЬгкВДах, где 7 = бсз.
Предположим, что ст ст Дах порождает строку терминалов Ьу. Тогда для каждой продукции вида  — з1 для некоторого з1 мы имеем порождение Я =~ 7ВЬу ~ уз1Ьу. Таким образом, ст ст [ — з1, Ь] является допустимым для 7. Заметим, что Ь может быть первым терминалом, порожденным из Д, либо возможно, что Д порождает с в порождении Дах ~ Ьр, и, следовательно, Ь может представлять собой а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
