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

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

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

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

Структура и значение Оператор Я1 в этом операторе, в свою очередь, является сокращенным услов- ным оператором 11 Ь2 1Ьеп Яз, в то время как операторы Я2 и Лэ — это про- стейшие атомарные в данной грамматике операторы ь | и к2 соответственно. Именно это отражает блок-схема этого фрагмента, построенная по дереву в соответствии с семантическими правилами б;~(табл.

3.9). Табл ица 3.9. Атрибутная грамматика б~ условного оператора Семантика продукций Продукции Пояснения ! ! ! Г 1 ! з ! 5о — АГА Феи 51 е!вел; „- состоит в ~ оператоусловие О Йо 5'о-иГ Ь Феи 5, ратора. е о ложно ! !Я з ! это простейший оператор л Другое дерево вывода той же цепочки и ее интерпретация в соответствии с этим деревом представлена на рис. 3.13.

В соответствии с ним вся цепочка, рассматриваемая как один оператор 50, представляет собой неполный условный оператор и 01 Феп Я!. Оператор Я! в этом операторе„в свою очередь, является полным условным оператором Ы 02 1Ьеп Я2 е!ве Яэ, а операторы Ь и Яз — это атомарные в данной грамматике операторы ь1 и м. Именно это отражает блок-схема этого фрагмента, построенная по дереву в соответствии с семантическими правилами табл. 3.9. ! ! ~о ! Г 1 31 ! ~ ! ! ! ! о ! Г ! ! ! ! ! Выполнение оператора 5о состоит в выполнении оператора 5,, если условие 6 истинно, либо ~; в про- чае 108 Глава 3 Рис.

3.12. Одно из возможных деревьев вывода цепочки И 01 Феп Г 02 Феп з1 е!ве з2 и соответствующая ее интерпретация Рис. З.13. Второе дерево вывода цепочки Ы Ь1 Фей 002 Феп з1 е1ве з2 и соответствующая ее интерпретация Итак, две разные интерпретации цепочки 11 Ь1 1Ьеп Ю о 1Ьеп ь1еЬе к2„постро- енные по одной и той же атрибутной грамматике, определяют совершенно разные вычисления. Возможны различные решения, позволяющие сделать грамматику условных операторов однозначной. Наиболее простое и очевидное — потребовать "закрывающей скобки" после условного оператора. Служебным словом, выполняющим роль закрывающей скобки, может быть либо епд, либо 6 — симметрично "открывающей скобке" и. Такая грамматика, в которой окончание ус- Структура и значение ловного оператора фиксировано, будет недвусмысленной, даже если разрешить использовать последовательность операторов после 1Ьеп и е!яе: 0';~.

Ь' — +Ы о !Ьеп А е1яе Е 6 ~ !Г О |Ьеп А й ~ г Использование служебных слов типа од и 6 в качестве закрывающих скобок при записи вложенных конструкций широко распространено в информатике, особенно в специальных языках. Например, можно встретить в качестве закрывающей скобки оператора саяе служебное слово еяас (входной язык системы верификации ЯМУ (тоде! сЬесЫпд) Университета Карнеги-Меллон). Введение дополнительных служебных слов, конечно, изменяет язык. В некоторых случаях можно построить недвусмысленную эквивалентную грамматику для данного языка, который порождается двусмысленной грамматикой. Рассмотрим, например, язык условных операторов.

Построим для него недвусмысленную грамматику, в которой для строки Ы Ь~ $Ьеп Ы 02 1Ьеп ю1 еЬе ю. возможно единственное синтаксическое дерево, подобное представленному на рис. 3.13. Общее правило для решения этой неоднозначности состоит в том, что каждое е1яе сопоставляется ближайшему "незанятому" Феп. Иными словами, оператор, который стоит между реп и еЬе, должен быть сбалансирован, т.

е. он не должен оканчиваться на терминал Феп, не соответствующий никакому е1яе. Это означает, что в грамматику нужно ввести еще один дополнительный нетерминальный символ, из которого могут быть выведены только "сбалансированные" операторы — либо полные операторы Ы-1ЬепеЬе, либо неусловные операторы (я). Соответствующая грамматика: 6'~.. 5 — эС ~ Ж С-+Ы О 1Ьеп С еЬе С ~ л К-+И о 1Ьеп Я ~ Ы Ь 1Ьеп С е1ке Ж Нетерминалы С и Ж имеют смысл "согласоваиоый условиый оператор" и "не- соглисоваины й условный оператор" соответственно. Очевидно, что для каждого языка построение удобной грамматики, его поро- ждающей, является искусством.

3.5. Трансляция арифметических выражений Язык, как множество цепочек над некоторым словарем, не связан жестко с какой-либо грамматикой, его порождающей. Как мы видели в главе 2, один и тот же язык может быть порожден различными грамматиками, более того, бесконечным числом возможных грамматик. Все эти грамматики будут эквивалентны между собой с точки зрения порождаемого языка. Но очевидно, Глава 3 что они могут быть вовсе не эквивалентны по всем остальным свойствам, Например, одна грамматика может быть двусмысленной, а другая нет„для одной может быть использован простой алгоритм синтаксического анализа (алгоритм восстановления вывода предложения), а для другой такой алгоритм либо очень сложен, либо его вообще не существует, в одной грамматике можно определить семантические вычисления просто, а в другой — очень сложно даже при одном и том же смысле„который мы хотим приписать порождаемым этими грамматиками предложениям.

При разработке транслятора необходимо учитывать все эти обстоятельства, В данном разделе на примере языка арифметических выражений показано, что грамматику языка во многих случаях можно "конструировать" так, чтобы она не только задавала язык, но также и обладала некоторыми желаемыми свойствами, например, семантические вычисления для предложений языка были бы просты. 3.5.1. Грамматики арифметических выражений Грамматика арифметических выражений б~. с начальным символом Е: О/; =- (х7'.

Š— и' ~ ф) ~ Е+Е ~ Š— Е! Е*Е ~ Е!Е Избавимся сначала от двусмысленности грамматики. Рассмотрим простейший вид арифметических выражений — арифметические выражения с одной операцией, которую обозначим '*'. Очевидно, для частного примера такого выражения — цепочки РРРРР— желательно иметь только одно дерево вывода, отражающее общепринятый порядок вычисления значения выражения слева направо. Рис. 3.15, а отражает желаемую структуру. Вся цепочка должна выводиться из начального символа, поэтому корень дерева помечен Е. Но что должно является двусмысленной.

Например, цепочка ю+ю' — ю ю имеет 5 различных деревьев вывода. Три из них представлены на рис. 3.14„и только одно из них— первое — отражает тот порядок выполнения операций в арифметическом выражении, который соответствует обычному пониманию его вычисления (если о считать, что семантика для Ст ~: определяется простым и естественным образом — атрибутной грамматикой табл.

3.1). —,о Таким образом, грамматика Ь ~: неприемлема для использования при трансляции, хотя она выполняет главную функцию, которая от грамматики требуется — порождает язык арифметических выражений. Попробуем построить ноо вую грамматику. эквивалентную грамматике Ст~:, но отличающуюся от нее удобством семантических вычислений, подобных тем, которые определены атрибутной грамматикой табл.

3.1: значение сложного арифметического выражения вычисляется как функция значений подвыражений, его составляющих. Структура и значение Рис. ЗЛ4. Различные деревья вывода арифметического выражения стоять в других узлах и на ребрах дерева? Очевидно, что префикс цепочки 'е ~ е ~ е ', выводящийся из? на рис. 3.15, а, имеет ту же структуру "арифметического выражения", что и вся цепочка, в отличие от оставшейся части выражения, выводящейся из ? .

Поэтому в узле дерева вместо ?~ должен стоять нетерминал Е, а в узле ? — другой нетерминал, который назовем Т (рис. 3.15, б). Искомая грамматика может иметь вид: б'~,. Š— +Е*Т~ Т Т вЂ” +е Продукция Š— +Т добавлена в грамматику для учета частного случая, когда левое подвыражение является просто операндом. Легко видеть, что для любых арифметических выражений с одной операцией грамматика 6~.. позволяет построить единственное дерево вывода (рис. 3.15, в), отражающее общепринятую семантику выполнения повторяющейся бинарной операции слева направо, которая формально выражена атрибутной семантикой табл. 3.10. Такой порядок называется левоассоциативным.

Поставим задачу построить другую грамматику того же языка бесскобочных арифметических выражений с одной-единственной операцией. Кроме того, что мы хотим иметь грамматику также недвусмысленную„попробуем построить ее так, чтобы в ней определялся порядок выполнения операций наоборот, справа налево (рис. 3.16). Легко видеть, что такая грамматика лишь Глава 3 чуть-чуть отличается от б~,. Такая атрибутная грамматика С ~, представлена 1 2 в табл. 3.11. Очевидно, что если операция '*' не ассоциативна, значение одного и того же выражения в разных атрибутных грамматиках будет разное.

Например, одно и то же выражение 8-3-2-1 в грамматике 6~, будет иметь значение 2, в то время как в грамматике б~. — значение 6 (см. рис. 3.16). Рис. 3.15. Дерево вывода и правила новой грамматики Таблица 3.10. Атрибутная грамматика арифметических выражений б~~, Структура и значение Таблица 3.11. Атрибутная грамматика арифметических выражений б'~; Рис. 3.16. Дерево вывода цепочки г * ~ * ~ * ~ в грамматике б~~ Поставим теперь задачу построения грамматики, порождающей арифметические выражения с двумя бинарными операциями. Пусть эти операции одного ранга, например, + и —.

Очевидно, что общепринятый порядок вычисления выражений с одноранговыми операциями сложения и вычитания — левоассоциативный. Такая грамматика почти не отличается от грамматики б~,. О'~:. Š— ~Е+Т~ Š— Т~ Т Т вЂ” ~~ Семантические правила для нее очевидны — они повторяют таковые для грамматики б~,. Таким образом, операции одного и того же приоритета (в данном случае '+' и ' — ') синтаксически не отличаются друг от друга, их можно заменить одной операцией (назовем ее "операция тиис~ слолсения", или 'оис'), и построить грамматику так: б~,.

Š— +Еотс Т~ Т Т вЂ” Й~ Пусть теперь две эти операции разных приоритетов, например, '+' и 'х', где 'х' обозначает умножение. Если мы добавим в грамматику б~, операцию умно- ! жения так же„как добавили операцию вычитания, мы получим грамматику, /лава 3 в которой дерево вывода цепочки определяет выполнение обеих операций слева направо независимо от приоритета операций: Е-+Е+Т~ Ехт~ Т Т вЂ” и' Эта грамматика недвусмысленна, для любой цепочки порождаемого язь.*,ка в ней строится одно-единственное дерево вывода.

Для цепочки г+г+~хгхг+~хю, например, дерево вывода будет иметь следующий вид (рис. 3.17). Рис. 3.17. Дерево вывода для цепочки ~+~+~хЫ+Ы Чем хороша и чем плоха грамматика Й~,? 5 Она хороша тем, что, во-первых, она порождает язык арифметических выражений с двумя операциями '+' и 'х' (в противном случае эта грамматика была бы бесполезна1).

Во вторых, она недвусмысленна, и даже, как мы увидим дальше, удобна для алгоритмов синтаксического анализа — т. е. построить дерево вывода цепочек порождаемого языка для этой грамматики несложно. Однако эта грамматика плоха тем, что для нее трудно построить простые семантические операции для ее продукций, обеспечивающие трансляцию. Более конкретно, невозможно построить атрибутную семантику для нее только на основе простых синтезированных атрибутов, подобно тому, как это сделано в грамматике б~:. В частности, для продукции Ь вЂ” ~Е+Т семантический атрибут "значение" нетерминала Е в левой части правила нельзя определить как сумму семантических атрибутов, определяющих значения нетерминалов в правой части правила (почему?).

Поставим проблему построения грамматики арифметических выражений с двумя операциями '+' и 'х', причем одна (например 'х') имеет больший приоритет, чем другая (например '+'). Грамматика должна быть такой, что дерево Структура и значение вывода любой цепочки должно отражать эти приоритеты (именно поэтому в этой грамматике мы надеемся определить простую удобную семантику), Рассмотрим "желаемую" структуру дерева вывода цепочки г+~+гх~хс+гхоз (рис.

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

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

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

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