Главная » Просмотр файлов » Карпов - Основы построения трансляторов (2005)

Карпов - Основы построения трансляторов (2005) (943926), страница 28

Файл №943926 Карпов - Основы построения трансляторов (2005) (Карпов - Основы построения трансляторов (2005)) 28 страницаКарпов - Основы построения трансляторов (2005) (943926) страница 282013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 28)

Нетерминал Х, в этой грамматике может быть заменен двумя цепочками: Š— >Я~ Явет А. Построенная непосредственно по этим правилам синтаксическая диаграмма не дает однозначного решения, по какому пути происходило движение при порождении заданной строки терминалов (рис. 5.21). Рис.

5.21. Синтаксическая диаграмма Воспользуемся удобным приемом эквивалентного преобразования синтаксической диаграммы, который называется факлгоуяаси~ией — объединением одинакового префикса двух ветвей (рис. 5.22, а). Чтобы избежать лишней рекурсии, эту синтаксическую диаграмму лучше представить в виде рис. 5.22, о). Рис. 5.22. Факторизация Построенная по такой преобразованной диаграмме распознающая процедура для Х, сначала обратится к распознающей процедуре, проверяющей, выводится ли начальный префикс входной терминальной строки из нетерминала Я (которую, конечно, надо еще построить).

Далее, если очередным терминалом является терминал вел, то процедура возвращается к проверке выводимости продолжения терминальной цепочки из Я, в противном случае распознавание цепочки, выводимой из Е, завершается. Очевидно, что процедура для распознавания цепочек, выводящихся из Х., должна быть рекурсивной: она должна вызывать процедуру Ь; которая в процессе своей работы будет вызывать саму процедуру Л. Итак, синтаксический анализатор, построенный для грамматики рекурсивного спуска, состоит из набора рекурсивных процедур, каждая из которых соответствует одному нетерминальному символу грамматики и строится непосредственно по синтаксической диаграмме этого нетерминала. Синтаксическая диа- 182 Глава 5 грамма является скелеиоя, отражающим поток управления в построенной по ней распознающей процедуре. Процедура, соответствующая нетерминалу Ж, получает на вход остаток терминальной цепочки и пытается определить, выводится ли префикс этой цепочки из нетерминала Х, вызывая при необходимости процедуры, соответствующие другим нетерминалам грамматики.

Вернемся к построению синтаксических диаграмм для нетерминалов грамматики языка Милан. Синтаксическая диаграмма для Л рис. 5.22, б имеет единственное разветвление. Выбор пути по ней будет однозначным при любой входной терминальной цепочке, если ни в одной цепочке языка Милан после строки, выводящейся из нетерминала Х„не будет стоять терминал ьеш. Это, конечно, можно проверить по грамматике Милана.

В главе 4 была определена функция Г01.10%(Щ, которая для нетерминала Ж определяет множество терминальных символов, которые могут встретиться в цепочках языка после цепочек, выводящихся из Х Для грамматики языка Милан Г0110%(Е) = = (епд, од, 6~, следовательно, преобразованная синтаксическая диаграмма для нетерминала Х гарантирует однозначное распознавание своих цепочек. По правилам грамматики Милана для нетерминала Я: 5 — +Ы ам Е ~ и ЬИе В Йо А ой ~ ЫВ йеп А й ~ ~1Л 1Ьеп А еЬе А й ~ итйе!Ь Е гЬ после несложной факторизации этих правил ~сл.

главу 4) построим следую- щую синтаксическую диаграмму (рис. 5.23). Рис. 5.23. Синтаксическая диаграмма По этой синтаксической диаграмме распознающая процедура строится про- сто: в каждом разветвлении синтаксической диаграммы все альтернативные ветви начинаются с различных терминальных символов. Не возникает сложностей при построении синтаксической диаграммы и для нетерминала В с единственным правилом порождения В-+Е ге1 Е Здесь нет альтернатив, и соответствующая процедура распознавания строится легко. Нисходящие методы синтаксического анализа Более сложно построить синтаксическую диаграмму, удовлетворяющую требованиям однозначности выбора пути при распознавании терминальной строки для нетерминала Е.

Действительно, правила для Е включают прямую левую рекурсию: Е-ЕО~БТ~ Т В соответствии с правилами эквивалентного преобразования грамматик с левой рекурсией ~си. главу 4) можно построить эквивалентные правила без левой рекурсии, введя дополнительный новый нетерминал: Е-+ ТЕ' Е'-+ой ТЕ' ~ е Теперь синтаксическая диаграмма для Е может быть построена так„как показано на рис. 5.24. Рис.

5.24. Синтаксическая диаграмма для Е Такая синтаксическая диаграмма ясно представляет конструкцию ВЫРАЖЕН ИЕ как последовательность термов между которыми стоят операции типа сложения. Очевидно, что выбор пути в единственном разветвлении этой синтаксической диаграммы будет однозначным по входной терминальной цепочке, если ни в одной цепочке языка Милан после строки, выводящейся из нетерминала Е, не будет стоять терминал ой (т. е.

после того как конструкция ВЫРАЖЕНИЕ закончится, очередным терминалом не может быть операция типа сложения). Формально, для грамматики языка Милан с эквивалентно преобразованными правилами для нетерминала Е, ГОЬ10%(Е) =-,'гЬ, ге1~и ГОЬЬО%(В)вГОЬЬОФ®иГОЬЬОФ(Л) = ~~гЬ, ге1, зев, до, реп. епд, од„й~~. Следовательно, синтаксическая диаграмма для нетерминала Е гарантирует однозначное распознавание своих цепочек. Аналогичное преобразование требуется для нетерминала Т.

Правила, содержащие прямую левую рекурсию: Т-+То1т Р ~ Р можно заменить эквивалентными Т вЂ” +Р Т' Т'-+опт Т' ~ е Построение синтаксической диаграммы для нетерминала Р не вызывает трудностей. Окончательный набор синтаксических диаграмм для языка Милан, удовлетворяющих требованию однозначности соответствующих распознающих процедур, будет иметь вид (рис. 5.25). Рис. 6.25. Синтаксические диаграммы Милана для метода рекурсивного спуска Примененные здесь приемы устранения левой рекурсии (в подграмматике арифметических выражений) и левой факторизации (для условных операторов) часто могут помочь в приведении произвольной грамматики к виду, для которого возможно использование метода рекурсивного спуска.

Построение распознающей процедуры по синтаксическим диаграммам описано здесь неформально. Более формально такое построение может быть выполнено в соответствии с показанной в главе 2 связью синтаксических диаграмм и конечных автоматов. Для каждой синтаксической диаграммы можно построить конечный автомат, а по нему стандартным алгоритмом распознающую процедуру. Например, построим такой автомат для нетерминала 5 грамматики языка Милан (рис. 5.26). Этот автомат отличается от обычного конечного автомата тем, что кроме терминальных символов на переходах могут встречаться и нетерминальные Нисходящие методы синтаксического анализа символы. При распознавании входной цепочки, если из текущего состояния выходит дуга, помеченная нетерминалом Ж, то это означает передачу управления процедуре, имитирующей функционирование автомата Ж.

Очевидно, что такие автоматы и распознающие процедуры по ним могут быть построены для каждого нетерминального символа (каждой синтаксической диаграммы). Выполнение распознавания цепочек языка набором соответствующих процедур возможно, если при наличии альтернативных переходов из каждого состояния все такие переходы помечены различными терминалами или, возможно, только один из переходов помечен пустым символом. Этот переход выбирается в случае, когда входной символ не совпадает ни с одним символом, помечающим альтернативные переходы.

Рис. 5.26. Автомат для нетерминала Я грамматики языка Милан В следующем разделе мы рассмотрим, как использовать полученные на рис, 5.25 синтаксические диаграммы для построения транслятора Милана методом рекурсивного спуска. 5.7. Трансляция языка Милан методом рекурсивного спуска Распознавание входной цепочки методом рекурсивного спуска начинается с запуска распознающей процедуры, соответствующей начальному символу грамматики.

В процессе распознавания эта процедура просматривает входную цепочку символ за символом и при необходимости обращается к другим распознающим процедурам. Если цепочка действительно принадлежит языку, порождаемому заданной грамматикой, работа алгоритма благополучно закончится, результатом работы распознающих процедур будет 'ДА, входная цеиочка ириоадлежти языку". Но где же структура входной цепочки, на основе которой мы хотели построить семантические вычисления? После работы распознающих процедур кро- меДА или НЕГ мы ничего другого не получим! Структура распознаваемой цепочки неявно определяется тем потоком управления„который реально был активизирован в процессе ее распознавания.

Если мы хотим эту структуру получить после распознавания в явном виде, мы можем по ходу распознавания эту структуру строить, например, в форме дерева вывода либо в виде последовательности применяемых правил подстановки. Однако, очевидно, при трансляции структура входной цепочки нам не важна сама по себе — она нужна только как основа для подключения семантических процедур.

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

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

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

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