Главная » Просмотр файлов » Теория синтаксического анализа, перевода и компиляции - Том 2

Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 18

Файл №943929 Теория синтаксического анализа, перевода и компиляции - Том 2 (Теория синтаксического анализа, перевода и компиляции) 18 страницаТеория синтаксического анализа, перевода и компиляции - Том 2 (943929) страница 182013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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)-ситуаций для одной болыпой грамматики.

Характеристики

Тип файла
DJVU-файл
Размер
3,44 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее