Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 18
Текст из файла (страница 18)
Правда, аозннкаег вопрос: что делать, если грамматика такова, что множества ГОП.О(У недостаточно для разрешения конфликта, возникающего между действиями прн разборе нз-за про. тнворечява«-ги множеств ЕК(0)-ситуаций? Известно несколько методов, и мы нх нзучиьг, прежде чем закончить исследование ЕК (О)-подхода к построению анализаторов, Один из метадоч состоят в том, что для разрешения неоднозначности можно по- 97 4 п.п .д.ю п..з гл.
т. методы оптнмнздцни синтдкснчпских Анализ*горов пытаться использовать локальный контеист. Если мог метод не приведет к успеху, можно попробовать расщепить каное-то множество ситуаций на несколько подмножеств. В каждом нз этих подмножеств для однозначного определения действия можно воснольюваться локальным контекстом. Пропллюстрируем на примерах оба метода. Пример 7.28.
Рассмотрим Ы(1)-грамьгатику с правилами (1) 5 Аа (2) 5 ИЛЬ <З) 5 сЬ (4) 5 Аса (б) А с Несмотря на то, что язык Ц6) состоит всего из четырех це. почек, грамматика 6 не является ЗЕВ(й).грамматикой ни для какого Ь) О. Каноническая систсьта множеств Е)((0)-ситуаций для 6 приведена на рис. 7.38. Вторые компоненты опущены и я Лет 5' 5 5 Аа( ААЬ(.сЬ( аса А с рт| 5' 5. .4»: 5 А.а Ае. 5 — а.АЬ)К са А с рт' 5 сь А с.
Рм 5 Аа е(ет 5 — аА.Ь Ятт 5 -а. А с ре: 5 ТЬ. Ам 5 — аль. Ате. '5 аса. Рис. 7.ЬВ. Канепмчесде» спсмме мпсжеете 1 й(О)-стттуеппй, т.т, методы пОстРОения тя(тт АнчлизАторов Ыы видны, что достичь (, иа А, можно, только имея в магазине с. Если свернуть с в Л, то по правилам грамматики полу- Рес. 7.39. Граф бОТО. чнм, что за А может идти только а. Поэтому таблица То построенная по А„содержит однозначную функцию действия: а Ь е ат т,т диалогично из графа бОТО видно, что достттчь Ат из а(е можно, только имея в магазине Ас. В таком контексте если с сзеритть к А, то за А чожет илти только Ь. Поэтому таблица Т„ построенная по А„содержит функцию лействня а Ь с ситраций [Л- ат.()т), [Л вЂ” а, В,),..., [Л вЂ” а„й„) для кра Стн Обпэпаасим А Мт (3т)а, (1,( (ап.йм ЗДЕСЬ дна Прстиворечивых множества ситуаций: А„и п(т.
Более того, поскольку РОЕЕОТР(А) -[а, Ь), алгоритм 7.10 не построит по А, и .(, однозначные действия для аванцепочек Ь и а соотжчствейно. Тем ие менее исследуем фуикцяю СОТО, определенную на множествах ситуаций и изображенную графически яа рис. 7.39'). ') Зпметем, юс чтет граф — еап«лнчеслттэ, дете е обмен случае граф переспдее седерл пт ппелм. Остальяые 1.)((1).таблицы для 6 можно получить непосредственно ~то алгоритму 7.10.
(З Грамнатика нз примера 7.26 не является ЗЕ)(-грамматикой. Однако для разрешения всех неоднозначиостев при разборе мы смогли использовать в множестве Ы(0)-стттуаттий заглядывание эперед. Класс ь)т(й).грамматттк, для которых всегда ьюжно таким е' Рр гл т методы оптнмизлции сннтлксичсских гнглизгтогог способом построить ьв-анализаторы, называется классом СК(Д).
граммащик г загрядыгалием илн, короче, классом СА(.К(Ь)-грамматнк') (более точное определение дано в упр. 7.4.11). 1А).К(й). грамматики образуют наиболее шврокнй естественный подкдасс СК(й)-грамматик, для которого заглядывание на Ь сныволов позволяет разрешать конфликты, возникающие при разборе, с помощью канонической системы лг", множеств СК(0)-снтувций. Ааанцепочки можно найти либо непосредственно по графу бОТО для РГ"„Лпбо СЛНВ МНОжЕСтВа СК(й)-Сктуацай С ОдИНаКОВЫМИ ядраМИ.
).АСК-грамматнкн включают в себя все БЕК-грамматика, но не пенная ЕК-грамматнка является САЕК-грамматикой. Приведен теперь пример, когда для получения однозначных действий разбора множество ситуаций,.расщепляется". Пример 7.27. Рассмотрим 1К(1)-грамматику с правилами (1) Я Аа (2) 3 даЬ (5) В ВЬ (4) 5 АВа (б) А с (6) В а Эта грамматика совершенно аналогична грамматике нз прнллера 7.26, но она не является САСК-грамматикой. Каноничесная система множеств 1 К(0)-снтуацнй для пополненной грамматики Ал' 5' 5 и(л: А и.
5 Аа В и 5 .аАЬ Ал' 5 Аа. 5 ВЬ и(В 5 ВЬ 5 Лва и(в: 5 аА Ь А .г .АЫ 5 ав а В г Алв' 5 аАЬ. и(л: У 5 0лл: 5 ад А и(м 5 А.а Ал' 5 В.Ь Ал: 5 аАЬ 5 аяа А .с В с Рис. 7.40. Кананилесггя снстенг ююмгетг ЩО)-сетугааа. приведена нв рнс. 7.40.
Множество Щ„противоречиво, потому что неизвестно, по какому правилу нужно свертывать: по А с яли по В с. Твк как РОЫОТлг(А)=-РОССО)й)(В) (а, Ь), нам ') От звгл. Ьюклвегв ) д(ь).— Прим, игргг. 100 т 4 методы псстровння лн)л).лнллизлтогов пе удастся устранить неоднозначность, использун в начестве аванцепочек эти множества. Следовательно, 0 не является 61 К(1)- грамматакой.
Анализ правнл грамматики показывает, что есла в магазине содержится только с н очередной входной снмвол есть а, то для сверткн символа с нужно применить правило А с. Если очередным входным синвололл служит Ь, то нужно воспользоваться правилом В с. Но если в магазине запнсанн цепочна дс и очередной входной символ есть а, то для свертки с нужно применять правило В с, а если очередным входным символом служит Ь -правило А с. функцня бОТО для множества ситуаций приведена на рнс. 7.41. К сожалению, А, досткжклю нз Ал н тогда, когда Ряс. 7.41 ГраФ ООТО.
в магазине содержится с, к тогда, когда там зал)ксана цепочка дс, Поэтому Кл не уточняет, какая яз этих двух цепочек записана в ллвгазине, н, значит, 6 не является САСК(1)-гралгматикой. Тем не менее для О лложно построить ЕК(1)-анализатор, заменяя их, такнми двуми одннаковымн множествамн г', и А"„что щ; доствжнмо только из А„а 4; — только непосредственно нз Ал. Эти новые множества ситуаций дают необходкллую дополнительную информапию о том, чтб содержится в магазине, По и(; и А; можно построить такие таблицы соднозначнымн функциями действия: а Ь а а' гл г методы оптимизации синтхксичвскнх хнхлизлтогав Функции перехода в таблицах Т; и Т, "всегда принилгают значения ошибка.
7.4.3. Расщенпание грамматини В настоян!ем разделе мы изучим другой метод построения ЕЯ-анализаторов. Он не так прост в применении, как метод 3!Я, но работает в случаях, когда метод Эьк не приводиг к успеху. Мы будем расщеплять грамматику 6 = (Х, Е, Р, 5) на нескольно грвмматик-компонент, рассматривая некоторые нетерминальные символы как терминальные. Пусть Х' ~ Х вЂ так множество „расщепляющих" нетерминалов. Для каждого А нз Х' можно найти эраммпщику.компонвншу бл с начальным впмволгм А, воспользовавшись с.чедуюшнм алгорйтмом.
Алга ритм 7.11. Расщепление грамматики. Влад. КС-грамматика 0=(Х, В, Р, 5) н подмножество Х' множества Х. Выход. Множество грамматик-компонент б„для каждого А Е Х', Метод. Для каждого А РХ' построить бв так: (П В правых частях всех правил из Р заменить каждый не- терминал ВЕХ' на В, Обозначим через Х множество (В)В 0 Х') и через Р новое множество правил. (2) Положим ба =-(Х вЂ” Х'0(А), ВПХ, Р, А).
(3) Применить алгоритм 2В для исключения из бл бесполезных нетерминвлов и правил. Получившаяся н результате грамматииа и есть бв. 'сз Мы займемся сейчас задачей построения Е)((1)-анализаторов для всех грамматик-компонент и объединения этих анализаторов. Для различных компонент можно, вообще говоря, строить анализаторы разных типов.
Например, для разбора выражений можно применить анализатор операторного предшествованпя, а зсе остальное разбирать с помогцью !.Е(1)-анализатора. Представляет интерес вопрос о талл, как можно распространить методы настоян!его раздела иа различные типы анализаторов. Пример 7.28. Пусть 6,— наша обычная грамматика и Х' =- =(Е, Т) — множество расщепляющих нетермииалов.
Тогда Р состоит из правил Е Е+Т)Т Т Тлр)Р Р (Е))а лпэ гл. методы пастгаэния Таким образом, бэ=((Е), (Е, Т, +), (Е Е+Т)Т), Е) и бг=((Т, Р), (Т, Е, (,), ал), (Т- ТяР)Р, Р (Е))а), Т). П Опишем теперь метод построения Е)7(1)-анализаторов для некоторых болыпих грамматик. Этот метод состоит в том, что сначала данная грамматика расщепляется на ряд меньших грамматик. Если для каждой грамллатики-компоненты удается найти систему непротиворечивых множеств ЕХ(1)-сигуа!лий и если удовлетворя!отса некоторые условия, связывающие эти множества, то для исходной грамматики множество ьк(1)-ситуаций строится путем объединения множеств ситуаций для грамматик-кочпонент. Основная идея метода таиова: построение систем множеств !.)((1).ситуаций для нескольких меньших грамматик и последующее их объединение обычно требует значительна меньшей работы, чем построение канонической систелгы множеств Е)((1)-ситуаций для одной болыпой грамматики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
