А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

Такой вид грамматики будет рассматриваться в разделе 2.4.5. 98 Глава 2. Простой синтаксически управляемый транслятор + гепп (рпп(('+')) геи, Рис. 2.13. Для семантического действия создается дополнительный лист гепп (рппг('+'Ц 2 (рпп!('2')) ехрг (рппг('-'Ц серг — гепп г гепп 5 (рппг('5')) 9 (рппг('9')) Рис. 2.14. Действия при трансляции 9-5+2 в 95-2+ 1рйп(1'+')) 1рйп(('-')) ехрг — ехргг + Гегт ехрг — ехргг — гегт ехрг — е Еепп ге) т — О гегт — 1 1рйп(('О')) 1рйп(1'1')) гегт — 9 1рг(п(1' 9') ) Рис. 2.15. Действия при трансляции в постфиксную запись Здесь нижний индекс у гехгг так же, как и ранее, присутствует для того, чтобы отличить нетерминал геег в теле продукции от экземпляра гезг в ее заголовке.

При изображении дерева разбора для схемы трансляции мы указываем действие путем добавления дополнительного дочернего узла и проведения от него пунктирной линии к узлу, соответствующему заголовку продукции. Например, часть дерев» разбора для приведенных выше продукции и действия показана на рис. 2.13. Узел семантическою действия не имеет дочерних узлов, так что действие выполняется при первом посещении узла. 99 2.3.

Синтаксически управляемая трансляция Пример 2.12. Дерево разбора на рис. 2.14 содержит инструкции печати в дополнительных листьях, которые присоединены пунктирными линиями ко внутренним узлам дерева разбора. Схема трансляции показана на рис. 2.15. Лежащая в ее основе грамматика генерирует выражения, состоящие из цифр, разделенных знаками "плюс" и "минус". Действия в телах продукций транслируют такие выражения в постфиксную запись при обходе дерева в глубину слева направо и выполнении каждой инструкции печати при посещении соответствующего листа. Корень дерева на рис.

2.14 представляет первую продукцию на рис. 2.! 5. При обратном порядке обхода сначала выполняются все действия в крайнем слева поддереве корня для левого операнда, который, как и корень, помечен как ехрг. Затем посещается лист +, в котором не выполняются никакие действия, после чего выполняются действия в поддереве правого операнда ~егт и, наконец, выполняется семантическое действие 1рпп11'+ )) в дополнительном узле.

Поскольку продукции для гепп в правой части имеют только одну цифру, эта цифра выводится действиями данных продукций. Не требуется никакой вывод в случае продукции ехрг — гегт, а в действиях первых двух продукций выводится только соответствующий оператор. При обходе в обратном порядке выполняющиеся действия на рис. 2.14 выводят строку 95-2+. и Обратите внимание, что хотя схемы на рис. 2.10 и 2.15 дают одну и ту же трансляцию, их построение отличается. На рис. 2.10 узлам дерева разбора назначаются строковые атрибуты, в то время как схема на рис. 2.15 выводит трансляцию инкрементно, посредством семантических действий.

Семантические действия в дереве разбора на рис. 2.14 транслируют инфиксное выражение 9-5+2 в 95-2+ путем вывода каждого символа ровно один раз, без привлечения дополнительной памяти для трансляции подвыражений. При инкрементном выводе описанным способом становится важен порядок, в котором выполняется вывод символов. Реализация схемы трансляции должна гарантировать, что семантические действия выполняются в том же порядке, в котором они встречаются при обходе дерева разбора в обратном порядке.

Реализация не обязана реально строить дерево разбора (зачастую оно и не строится), но должна гарантировать такое выполнение семантических действий, как если бы дерево разбора было построено, а затем выполнены действия при обходе этого дерева разбора в обратном порядке. 2.3.6 Упражнения к разделу 2.3 Упражнение 2.3.1. Постройте схему синтаксически управляемой трансляции, которая транслирует арифметические выражения из инфиксной записи в префиксную, в которой оператор находится перед операндами; например, — ху представляет собой префиксную запись для х — у. Изобразите аннотированное дерево разбора для входных строк 9-5+2 и 9-5*2.

Глава 2. Простой синтаксически управляемый транслятор Упражнение 2.3.2. Постройте схему синтаксически управляемой трансляции, которая транслирует арифметические выражения из постфиксной записи в инфиксную. Изобразите аннотированное дерево разбора для входных строк 95-2* и 952*-. Упражнение 2.3.3. Постройте схему синтаксически управляемой трансляции, ко- торая транслирует целые числа в числа, записанные римскими цифрами. Упражнение 2.3.4.

Постройте схему синтаксически управляемой трансляции, которая транслирует числа, записанные римскими цифрами, в обычную десятичную запись. Упражнение 2.3.5. Постройте схему синтаксически управляемой трансляции, которая транслирует постфиксные арифметические выражения в эквивалентные префиксные арифметические выражения. 2.4 Разбор Разбор (рагз(пя) представляет собой процесс, определяющий, может ли некоторая строка терминалов быть сгенерирована данной грамматикой.

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

В следующем разделе приведена законченная программа на языке программирования эача, реализующая схему трансляции на рис. 2.15. Альтернативный способ состоит в использовании программного инструментария для генерации транслятора непосредственно на основе схемы трансляции. В разделе 4.9 описывается такой инструмент — тасс; он может реализовать схему трансляции на рис.

2.15 без какой-либо модификации. Для любой контекстно-свободной грамматики существует анализатор, который требует для разбора строки из п терминалов время, не превышающее О (пз). Однако, в целом, кубическое время слишком велико; к счастью, для реальных языков программирования можно разработать грамматику, обрабатываемую существенно быстрее. Для разбора почти всех встречающихся на практике языков достаточно линейного алгоритма. Анализаторы языков программирования почти всегда делают один проход входного потока слева направо, заглядывая вперед на один терминал, и по ходу просмотра строят части дерева разбора.

Большинство методов разбора делится на два класса — нисходящие (сверху вниз, юр-боип) и восходящие (снизу вверх, Ьопош-цр). Эти термины связаны )О) 2А. Разбор с порядком, в котором строятся узлы дерева разбора. В нисходящих анализаторах построение начинается от корня по направлению к листьям, в то время как при восходящем методе — от листьев по направлению к корню. Популярность нисходящих анализаторов обусловлена тем фактом, что построить эффективный анализатор вручную проще с использованием нисходящих методов.

Однако восходящий разбор может работать с большим классом грамматик и схем трансляции, так что программный инструментарий для генерации анализаторов непосредственно на основе грамматик часто использует восходящие методы. 2.4.1 Нисходящий анализ Знакомство с нисходящим анализом начнем с рассмотрения грамматики, которая хорошо подходит для методов разбора этого типа. Позже в этом разделе будет рассмотрено построение нисходящих анализаторов в общем случае. Приведенная на рис. 2.16 грамматика генерирует подмножество инструкций С или )ача.

Мы используем выделенные полужирным шрифтом терминалы !Г и !ог для ключевых слов хХ и аког соответственно, чтобы подчеркнуть, что эти последовательности символов рассматриваются как единицы, т.е. отдельные терминальные символы. Далее, терминал ехрг представляет выражения; более полная грамматика использовала бы нетерминал ехрг и содержала бы продукции для него. Аналогично о!Пег — терминал, представляющий другие конструкции языка. кгт1 — ехрг 1 И ( ехрг ) з1т1 !ОГ ( ОР1ЕХРг 1 ор1ехрг 1 ор!ехРг ) з1т1 огпег ор1ехрг ехрг Рис. 2.16.

Грамматика дпя некоторых выражений С и )ача Построение дерева разбора (наподобие показанного на рис. 2.! 7) сверху вниз начинается с корня, помеченного стартовым нетерминалом згт1, и осуществляется многократным выполнением следующих двух шагов. 1. В узле Аг, помеченном нетерминалом А, выбираем одну из продукций для А и строим дочерние узлы А' для символов из правой части продукции. 2.

Находим следующий узел, в котором должно быть построено поддерево; обычно это крайний слева неразвернутый нетерминал дерева. 102 Глава 2. Простой синтаксически управляемый транслятор Гог ( оргекрг; оргекрг; оргекрг ) елт е ехрг ехрг огьег Рнс. 2.17. Дерево разбора, соответствующее грамматике на рис. 2.16 Для некоторых грамматик описанные выше шаги могут быть реализованы в процессе единственного прохода слева направо по входной строке.

Текущий сканируемый терминал входной строки часто называют сканируеньыг символаи или "предсимволом" (1оо(саЬеас( зушЬо1).з Изначально предсимволом является первый, т.е. крайний слева, терминал входной строки. На рис. 2.18 проиллюстрировано построение дерева разбора на рис. 2.17 для входной строки 1ог (; ехрг; ехрг 1 обжег Изначально предсимволом является терминал 1ог, и известная часть дерева разбора состоит из корня, помеченного стартовым нетерминалом л(тг на рис.

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

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