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

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

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

2.19 показан результат применения этих правил к грамматике на рис. 2.16. Так же, как схема трансляции получается в результате расширения грамматики, синтаксически управляемый транслятор может быть получен расширением предикгивного анализатора. Алгоритм для решения этой задачи приведен в разделе 5.4. В настоящий момент достаточно следующего ограниченного построения. 1. Построить предиктивный анализатор, игнорируя действия в продукциях. 2. Скопировать действия из схемы трансляции в анализатор. Если действие в продукции р находится после символа грамматики Х, то оно копируется после кода, реализующего Х.

В противном случае, если это действие располагается в начале продукции, оно копируется непосредственно перед кодом, реализующим продукцию. Такой транслятор будет построен в разделе 2.5. 2.4.5 Левая рекурсия Анализатор, работающий методом рекурсивного спуска, может оказаться в состоянии зацикливания.

Такая проблема возникает при "леворекурсивных" продукциях наподобие ехрг — ехрг + !егт В них левый символ тела продукции идентичен нетерминалу в заголовке продукции. Предположим, что процедура для ехр» принимает решение о применении 108 Глава 2. Простой синтаксически управляемый транслятор этой продукции. Поскольку тело продукции начинается с ехрг, рекурсивно вызывается та же самая процедура. Поскольку сканируемый символ изменяется только тогда, когда он соответствует терминалу в теле продукции, между рекурсивными вызовами ехрг не происходит никаких изменений.

В результате второй вызов ехрг действует точно так же, как и первый, что означает выполнение третьего и прочих вызовов ехр» до бесконечности. Левую рекурсию можно устранить, переписав некорректную продукцию. Рассмотрим нетерминал А с двумя продукциями: А — Ась ( Д Здесь гк и ~3 — последовательности терминалов и нетерминалов, которые не начинаются с А. Например, в ехрг — ~ ехрг + Гегпз ~ Гехт нетерминал А представляет собой ехрг, строка о = +гегпз„ а строка,З = гегт. Нетерминал А и его продукция называются леворекурсивными, потому что продукция А — Агг содержит А в качестве крайнего слева символа в теле продукции.~ Повторное применение данной продукции приводит к последовательности гх справа от А, как на рис.

2.20, а. Когда А„наконец, заменяется на Д, за ним следует последовательность из нуля или большего количества и. Рнс. 2.20. Лево- н праворекурснвные способы генерации строки Тот же результат может быть достигнут (рис. 2.20, б1 путем переписывания продукции для А с использованием нового нетерминала Л: А — ДВ гг — > ггН. ( е "Н общем случае н лсворскурснвной граммкгнкс вместо продукции А Ао нсгсрмннал А может порождать Ао через промсжузочную продукцию.

2.5. Транслятор простых выражений !09 Нетерминал Л и его продукция Л вЂ” оЛ вЂ” праворекурсивные, поскольку продукция для Л содержит в теле Л в качестве крайнего справа символа. Право- рекурсивные продукции приводят к деревьям, которые растут вниз вправо, как на рис. 2.20, б. Рост деревьев вниз вправо затрудняет трансляцию выражений, содержащих левоассоциативные операторы, такие как "минус'*.

Однако в разделе 2.5.2 вы увидите, что коррекгная трансляция выражения в постфнксную запись все еще может быть получена путем аккуратного проектирования схемы трансляции. В разделе 4.3.3 мы рассмотрим более общие виды левой рекурсии и покажем, как можно устранить левую рекурсию из грамматики. 2.4.6 Упражнения к разделу 2.4 Упражнение 2.4.1. Постройте анализатор, работающий методом рекурсивного спуска, для следующих грамматик. а)Я вЂ” +ЯЯ~ — ЯЯ~а б)Я вЂ” Я(Я)Я ~с в)Я вЂ” ОЯ! ( 01 2.5 Транслятор простых выражений С помощью методов, описанных в трех последних разделах, мы построим синтаксически управляемый транслятор в виде рабочей программы на )ача, которая будет транслировать арифметические выражения в постфиксную запись.

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

Синтаксически управляемая схема трансляции часто служит в качестве спецификации транслятора. Схема на рис. 2.21 (повторяющая схему на рис. 2.!5) определяет выполняемую трансляцию. Зачастую грамматика, лежащая в основе данной схемы, требует модификации перед тем, как сможет быть разобрана предиктивным анализатором. В частности, грамматика, лежащая в основе схемы, представленной на рис. 2.21, леворекурсивна, а, как вы видели в предыдущем разделе, предиктивный анализатор не может обработать леворекурсивную грамматику. Мы оказываемся на распутье: с одной стороны, нам нужна грамматика, которая упрощает трансляцию, а с другой стороны, нам нужна совсем другая грамматика, которая упрощает синтаксический анализ.

Решение заключается в том, Глава 2. Простой синтаксически управляемый транслятор ехрг — ехрг + гехт 1 рпп1('+') ) ехрг — Гегт ( рпп1('-') ) гегт ( рпп1('О') ) ( рпп1('1') ) гегт — О 9 1 рпп1('9') ) Рнс. 2.21. Действия для трансляции в постфнксную запись чтобы начать с грамматики с простой трансляцией и осторожно и аккуратно преобразовать ее в упрощающую синтаксический анализ. Путем устранения левой рекурсии из схемы на рис. 2.21 мы можем получить грамматику, подходящую для использования в предиктивном трансляторе, работающем методом рекурсивного спуска.

2.5.1 Абстрактный и конкретный синтаксис Хорошим отправным пунктом для проектирования транслятора служит структура данных, которая называется абстрактным синтаксическим деревом или деревом абстрактного синтаксиса (аЬз)гас1 лунгах 1гее). В абстрактнам синтаксическом дереве для выражения каждый внутренний узел представляет оператор; его дочерние узлы представляют операнды этого оператора. В общем случае любая программная конструкция может быть обработана путем создания оператора для данной конструкции и рассмотрения семантически значащих компонентов конструкции в качестве операндов этого оператора. В абстрактном синтаксическом дереве для выражения 9-5+2 на рис.

2.22 корень представляет оператор +. Поддеревья корня представляют подвыражения 9-5 и 2. Группирование 9-5 в качестве операнда отражает порядок вычисления операторов с одинаковым уровнем приоритетов слева направо. Поскольку — и + имеют один и тот же приоритет, 9-5+2 эквивалентно (9-5)+2. Абстрактные синтаксические деревья, или просто синтаксические деревья, похожи на деревья разбора, но в синтаксическом дереве внутренние узлы представляют программные конструкции, в то время как в дереве разбора внутренние узлы представляют нетерминалы. Многие негерминалы грамматики представляют программные конструкции, но некоторые из них являются "вспомогательными" того или иного вида, такими, как представляющие множители, слагаемые или другие разновидности выражений. В синтаксическом дереве эти вспомогательные узлы обычно не нужны и потому опускаются.

Чтобы подчеркнуть различия, дерево 2.5. Транслятор простых выражений Рнс. 2.22. Сннтакснче- ское дерево лля выраже- ния 9-5+2 разбора иногда называют конкретным синтаксическим деревом, а лежащую в его основе грамматику — конкретным синтаксисом языка программирования. В синтаксическом дереве на рис. 2.22 каждый внутренний узел связан с оператором без "вспомогательных" узлов для одинарных продукций (продукция, тело которой содержит только один нетерминал, и ничего более) наподобие ехрг — гегт или е-продукций наподобие гехг— Желательно, чтобы схема трансляции бьиа основана на грамматике, деревья разбора которой, насколько это можно, близки к синтаксическим деревьям. Группировка подвыражений грамматикой на рис.

2.21 аналогична их группировке в синтаксических деревьях. Например, подвыражения оператора сложения представпены в теле продукции ехрг+ ге«т членами ехрг и ге«т. 2.5.2 Адаптация схемы трансляции Метод устранения левой рекурсии, набросок которой приведен на рнс. 2.20, может быть применен и к продукциям, содержащим семантические действия. Сначала распространим этот метод на множественные продукции.

В нашем примере А представляет собой ехрг и для ехрг у нас имеются две леворекурсивные продукции и одна, таковой не являющаяся. Метод устранения левой рекурсии трансформирует продукции А — Ао ~ А)3 ~ т в А — ТЙ Й вЂ” ~ ОЙ~~ЗЙ~ е Затем требуется преобразовать продукции с внедренными действиями, а не только с терминалами и нетерминалами. Семантические действия, внедренные в продукции, просто переносятся при преобразовании так же, как если бы они были терминалами. П2 Глава 2.

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

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