А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 18
Текст из файла (страница 18)
При этом каждый элемент списка представляет собой список множителей, разделенных знаками * и /. Обратите внимание, что любое выражение в скобках является множителем, поэтому с помощью скобок можно создать выражение с любым уровнем вложенности (и, соответственно, произвольной высотой дерева). о Пример 2.7. Ключевые слова позволяют распознавать инструкции, поскольку большинство из них начинается с ключевого слова или специального символа. Теперь рассмотрим бинарные операторы * и /, которые имеют наивысший приоритет. Поскольку эти операторы левоассоциативны, продукции подобны продукциям для списков, которые также левоассоциативны: 88 Глава 2. Простой синтаксически управляемый транслятор Обобщение грамматики выражений из примера 2.6 Можно рассматривать множитель Дасгог) как выражение, которое не может быть "разорвано" никаким оператором.
Под этим мы понимаем то, что размещение оператора с любой стороны от множителя не может привести к тому, что операндом этого оператора может стать часть множителя — таким операндом может быть только оператор целиком. Если множителем является выражение в скобках, то от разрыва его защищают скобки; если множитель представляет собой отдельный операнд, то понятно, что он также не может быть разорван. Член (мпл), не являющийся одновременно множителем, представляет собой выражение, которое может быть разорвано оператором с более высоким приоритетом, но не с менее высоким.
Выражение, не являющееся ни членом, ни множителем, может быть разорвано любым оператором. Эту идею можно обобщить для п уровней приоритетов. Нам нужно п + 1 нетерминалов. Первый, подобно ~асгог в примере 2.6, не может быть разобран ни в коем случае. Обычно тела продукций для этого нетерминала являются отдельными операндами или выражениями в скобках.
Затем, для каждого уровня приоритетов имеется по одному нетерминалу, представляющему выражения, которые могут быть разорваны операторами данного или более высокого уровня. Обычно пролукции для этих нетерминалов имеют тела, представляющие использование операторов на данном уровне приоритета, плюс одно тело, которое представляет собой нетерминал для следующего по высоте уровня приоритета.
Исключениями из этого правила являются присваивания и вызовы процедур. Инструкции, определяемые (неоднозначной) грамматикой, показанной на рис. 2.8, являются корректными инструкциями 1ача. В первой продукции для яплг терминал Ы представляет любой идентификатор. Продукции для ехргезз1ол не показаны. Инструкции присваивания, определяемые первой продукцией, являются корректными инструкциями 1ача, хотя )ача рассматривает = как оператор присваивания, который может находиться внутри выражения. Например, 1ача разрешает использование присваивания а=Ь=с, запрещенное данной грамматикой.
Нетерминал зплм генерирует (возможно, пустой) список инструкций. Вторая продукция для птм генерирует пустой список е. Первая продукция генерирует (возможно, пустой) список инструкций, за которым следует инструкция. Размещение точек с запятой — достаточно тонкий вопрос. Они располагаются в конце каждого тела продукции, которое не заканчивается зппп Подобный под- 89 2.2. Определение синтаксиса хгтг Ь1 = ехргехаоп; и ( ехргехйоп ) зтп' И ( ехргехйоп ) хоп( е!яе зтп зчЬа!е ( ехргеххгоп ) зйиг оо х~тс и Ьне ( ехргехиоп ) р (Итй) Рис.
2.8. Грамматика для подмножества инструкций )ача ход предотвращает накопление точек с запятой после таких инструкций, как Ы и и Ьае, которые заканчиваются вложенными подынструкциями. Когда вложенная инструкция представляет собой присваивание или цикл оо-тчЫ1е, точка с запятой генерируется как часть подынструкции. и 2.2.7 Упражнения к разделу 2.2 Упражнение 2.2.1. Рассмотрим контекстно-свободную грамматику Я вЂ” ЯЯ+ ~ ЯЯ* ~ а а) Покажите, как данная грамматика генерирует строку аа+а*. б) Постройте дерево разбора для данной строки. в) Какой язык генерирует данная грамматика? Обоснуйте свой ответ. Упражнение 2.2.2. Какой язык генерируется каждой из следующих грамматик? В каждом случае обоснуйте свой ответ.
а)Я вЂ” ОЯ1 ! 01 б)Я вЂ” +ЯЯ(-ЯЯ)а в)Я вЂ” «5(5)Я! г)Я вЂ” аЯЬЯ ! ЬЬа5 ) е д) Я а ! 5+3 ! ЯЯ 1Яе!(Я) Упражнение 2.2.3. Какие из грамматик в упражнении 2.2.2 неоднозначны? 90 Глава 2. Простой синтаксически управляемый транслятор Упражнение 2.2.4. Постройте однозначные контекстно-свободные грамматики для каждого из следующих языков. В каждом случае покажите корректность вашей грамматики. а) Арифметические выражения в постфиксной записи. б) Левоассоциативный список идентификаторов, разделенных запятыми. в) Правоассоциативный список идентификаторов, разделенных запятыми. г) Арифметические выражения, состоящие из целых чисел и идентификаторов с четырьмя бинарными операторами +, —, *, /. ! д) Добавьте унарные "плюс" и "минус" к арифметическим операторам из е.
Упражнение 2.2.5. а) Покажите, что все бинарные строки, генерируемые приведенной далее грамматикой, имеют значения, делящиеся на 3. Указание: воспользуйтесь индукцией по количеству узлов в дереве разбора. пит — 11 ! 1001 ! пит 0 ! пит пит б) Генерирует ли эта грамматика все бинарные строки, значения которых делятся на 3? Упражнение 2.2.6. Постройте контекстно-свободную грамматику для записи чи- сел римскими цифрами. 2.3 Синтаксически управляемая трансляция Синтаксически управляемая трансляция выполняется путем присоединения правил или программных фрагментов к продукциям грамматики. Рассмотрим, например, выражение ехрг, генерируемое продукцией ехрг — ехрг, + 1егт Здесь ехрг представляет собой сумму подвыражений ехрг, и гегт.
(Нижний индекс в ехрг, используется только для того, чтобы различать ехрг в теле продукции и в ее заголовке.) Можно транслировать ехрг, воспользовавшись его структурой, как показано в следующем псевдокоде: Трансляция ехргб Трансляция ~егт; Обработка +; 91 2.3. Синтаксически управляемая трансляция Используя вариант такого псевдокода и обрабатывая + путем создания соответствующего узла, в разделе 2.8 мы построим синтаксическое дерево для ехрг путем построения синтаксических деревьев для ехргз и гехт. Для удобства в качестве примера в этом разделе будет рассмотрена трансляция инфиксных выражений в постфиксные.
В этом разделе вводятся две концепции, связанные с синтаксически управляемой трансляцией. ° Атрибуты. Атрибут представляет собой некоторую величину, связанную с программной конструкцией. Примерами атрибутов являются типы данных выражений, количество команд в генерируемом коде, расположение первой команды в генерируемом для конструкции коде, а также многое другое.
Поскольку мы используем грамматические символы (нетерминалы н терминалы) для представления программных конструкций, следует распространить понятие атрибутов не толью на конструкции, но и на символы, их представляющие. ° (Синтаксически управляемые) схемы трансляции. Схема трансляции — это запись присоединенных к продукциям грамматики программных фрагментов. Эти фрагменты выполняются при использовании продукции в процессе синтаксического анализа. Объединенный результат выполнения всех этих фрагментов в порядке, определяемом синтаксическим анализом, и есть трансляция программы, к которой применяется этот процесс анализЫсинтеза. Синтаксически управляемая трансляция будет использоваться во всей этой главе для трансляции инфиксных выражений в постфиксные, для вычисления выражений и для построения синтаксических деревьев для программных конструкций.
Более подробно синтаксически управляемый формализм рассматривается в главе 5. 2.3.1 Постфиксная запись Примеры в этом разделе посвящены трансляции в постфиксную запись. Постфиксная запись (роягбх по~айоп) выражения Е может быть индуктивно определена следующим образом. 1. Если Е является переменной или константой, то постфиксная запись Е представляет собой само Е. 2. Если Š— выражение вида Е~ ор Ез, где ор — произвольный бинарный оператор, то постфиксная запись Е представляет собой Е' Е' ор, где Е', и Е~ — постфиксные записи для Е~ и Ез соответственно.
92 Глава 2. Простой синтаксически управляемый транслятор 3. Если Š— выражение в скобках вида (Е1), то постфиксная запись для Е такова же, как и постфнксная запись для Еп Пример 2.8. Постфиксная запись для ( 9-5 ) +2 представляет собой 95-2+. Согласно правилу (1) трансляция 9, 5 и 2 представляет собой сами эти константы.
По правилу (2) 9-5 транслируется в 95-. Тот же вид согласно правилу (3) имеет и трансляция (9-5). Получив результат трансляции подвыражения в скобках, можно применить правило (2) для трансляции всего выражения, где ( 9-5) выступает в роли Еы а 2 — в роли Ез, и получить результат 95-2+. В качестве другого примера для 9-(5+2) постфнксная запись имеет вид 952+-, т.е. 5+2 сначала транслируется в 52+, а затем это выражение становится вторым аргументом знака "минус*'. а Скобки в постфиксной записи не используются, поскольку последовательность и арность (ап(у) — количество аргументов — операторов допускают только единственный способ декодирования постфиксного выражения.
"Фокус" заключается в последовательном сканировании постфиксной строки слева направо, пока не встретится оператор. Затем выполняется поиск слева соответствующего количества операндов и найденный оператор выполняется с этими операндами. Результат выполнения замещает операнды и оператор, после чего процесс поиска слева направо очередного оператора продолжается. Пример 2.9. Рассмотрим постфиксное выражение 952+-3*. Сканируя слева направо, первым мы встретим знак "плюс". Слева от него мы обнаруживаем операнды 5 и 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
