А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 84
Текст из файла (страница 84)
Построение дерева разбора и его аннотирование. Этот метод работает для любого нециклического СУО. С аннотированными деревьями разбора мы уже знакомились в разделе 5.1.2. 2. Построение дерева разбора, добавление действий и выполнение действий в прямом порядке обхода. Этот подход работает для любого 1 -атрибутного определения.
Преобразование 1.-атрибутного СУО в СУТ рассматривалось в разделе 5.4.5; в частности, в нем рассматривались вопросы вставки действий в продукции на основе семантических правил такого СУО. В этом разделе мы рассмотрим другие методы трансляции в процессе синтаксического анализа. 3.
Использование синтаксического анализатора, работающего методам рекурсивного спуска, с одной функцией для каждого нетерминала. Функция для нетермннала А получает наследуемые атрибуты А в качестве аргументов и возвращает синтезируемые атрибуты А. 4. Генерация кода "на лету" с применением синтаксического анализатора„ работающего методом рекурсивного спуска. 5.
Реализация СУТ вместе с Ы-синтаксическим анализатором. Атрибуты хранятся в стеке синтаксического анализа, а правила выбирают требующиеся им атрибуты из известных позиций в стеке. 423 5.5. Реализация 1.-атрибутных СУО б. Реализация СУТ вместе с Ей-синтаксическим анализатором.
Этот метод может показаться неожиданным, поскольку СУТ для 1-атрибутного СУО обычно содержит действия в средине продукций, и в процессе 1.а-синтаксического анализа мы не можем знать точно, какая именно продукция используется, пока не построим все ее тело. Однако, как мы увидим, если лежащая в основе грамматика принадлежит к классу 1.1., то всегда можно провести как синтаксический анализ, так и трансляцию в восходящем направлении. 5.5.1 Трансляция в процессе синтаксического анализа методом рекурсивного спуска Синтаксический анализатор, работающий методом рекурсивного спуска, для каждого нетерминала А имеет отдельную функцию А (об этом говорилось в разделе 4.4.1). Можно расширить синтаксический анализатор и превратить его в транслятор, если следовать следующим правилам.
а) Аргументами функции А являются наследуемые атрибуты нетерминала А. б) Возвращаемое функцией А значение представляет собой набор синтезируемых атрибутов нетерминала А. В теле функции А требуется как выполнить синтаксический анализ, так и обработать атрибуты. 1. Принимается решение о том, какая продукция используется для развертывания А.
2. Когда это необходимо, проверяется каждый терминал входного потока. Будем считать, что возврат не требуется, но перейти к синтаксическому анализу методом рекурсивного спуска с возвратом можно путем восстановления позиции во входном потоке при ошибке, как описано в разделе 4.4.1. 3. В локальных переменных сохраняются значения всех атрибутов, необходимые для вычисления наследуемых атрибутов нетерминалов в теле продукции или синтезируемых атрибутов нетерминала заголовка. 4. Вызываются функции, соответствующие нетерминалам в теле выбранной продукции, с передачей им корректных аргументов.
Поскольку лежащее в основе СУО является 1.-атрибутным, все необходимые для передачи атрибуты к этому моменту уже вычислены и сохранены в локальных переменных. 424 Глава 5. Синтаксически управляемая трансляция ягг!Ия Я(1аЬе! Иехг) ( я!Нпй Ясоне, Ссоре; /* Локальные переменные с фрагментами кода "! 1аЬе1 Ы, т'2;!* Локальные метки *! !1' ( Текущий входной символ = — токен ттЫ!е ) ( Перемещение по входному потоку; Проверить наличие '(' во входной строке и перейти к новой ПОЗИЦИИ; 11 = пею()' А2 = лги(); Ссоре = С(лехб Т2); Проверить наличие ')' во входной строке и перейти к новой позиции; Ясоне = Я(Е1); ге1пгп("1аЪе1 "~11В1~~Ссойе~11" 1аЪе1" 1112~~3сойе); е!яе!* Инструкции других видов */ Рис.
5.29. Реализация конструкции в!61е при помощи синтаксического анализатора, работающего методом рекурсивного спуска Пример 520. Рассмотрим СУО и СУТ для конструкции тчЫ!е из примера 5.19. Набросок псевдокода значимой части функции Я показан на рис. 5.29. Здесь функция Я показана как хранящая и возвращающая длинные строки. На практике было бы более эффективно, если бы функции наподобие Я и С возвращали указатели на записи, представляющие эти строки. Тогда инструкция гегпгп в функции Я не выполняла бы показанную конкатенацию строк, а вместо этого строила бы запись или, возможно, дерево записей, выражающее конкатенацию строк, представленных Ясоне и Ссоре, метками 1,1 и В2, а также двух строк "1аЪе1".
Пример 5.21. Теперь вернемся к СУТ на рис. 5.26 для текстовых боксов. Сначала мы обратимся к синтаксическому анализу, поскольку грамматика, лежащая в основе СУТ на рис. 5.26, неоднозначна. Приведенная далее преобразованная грамматика делает отношение смежности и индексирование правоассоциативными, при этом оператор кцЬ имеет более высокий приоритет, чем смежность: Я вЂ” В в - тв,)т т — к ьт~к Р—. (В) ~ 1ехт 425 5.5. Реализация 1.-атрибутных СУО Даа новых нетерминала, Т и В, выполняют те же функции, что и слагаемые и сомножители в выражениях. Здесь "сомножитель", генерируемый Е, представляет собой либо бокс в скобках, либо строку.
"Слагаемое", генерируемое Т, представляет собой "множитель*' с последовательностью индексов, а бокс, генерируемый „— последовательность смежных "слагаемых". Атрибуты В переходят к Т и г, поскольку эти новые нетерминалы также обозначают боксы; они введены исключительно во вспомогательных целях.
Таким образом, и Т, и Е имеют наследуемый атрибут рз и синтезируемые атрибуты лг и Ыр, с семантическими действиями, которые могут быть получены из СУТ на рис. 5.26. Грамматика пока что не готова для нисходящего синтаксического анализа, поскольку продукции для В и Т имеют общие префиксы. Рассмотрим, например, Т. Нисходящий синтаксический анализатор не может выбрать одну из двух продукций для Т, просматривая только один символ из входного потока.
К счастью, можно воспользоваться разновидностью левой факторизации, рассматривавшейся в разделе 4.3.4. В случае СУТ понятие общего префикса применимо также н к действиям. Обе продукции для Т начинаются с нетерминала Г, наследующего атрибут ря от Т. Псевдокод на рис. 5.30 для Т(рв) включает код г (рз). После применения левой факторизации к Т вЂ” г яцЬ Т1 ~ и остается только один вызов Е; в псевдокоде показан результат подстановки кода Е вместо этого вызова. Функция Т будет вызвана функцией В как Т (10.0) (этот вызов здесь не показан). Функция возвращает пару, состоящую из значений высоты и глубины бокса, генерируемого нетерминалом Т; на практике она возвращает запись, содержащую высоту и глубину. Функция Т начинается с проверки наличия левой скобки — в этом случае используется продукция Š— (В). Функция сохраняет значения, которые возвращает функция В, но если после В не следует правая скобка, то это означает, что мы столкнулись с синтаксической ошибкой, обработка которой здесь не показана.
В противном случае, если текущий входной символ — 1ехг, функция Т использует функции дега и дерр для определения высоты и глубины этого текста. Затем Т выясняет, является ли следующий бокс индексом, и если является, то соответствующим образом изменяет кегль. Для вычислений используются действия, связанные с продукцией  — В яцЬ В на рис. 5.26 и вычисляющие высоту и глубину большого бокса.
В противном случае функция просто возвращает значения, вычисленные функцией Е:(61,г(1). и 5.5.2 Генерация кода "на лету" Построение длинных строк кода, являющихся значениями атрибутов, как это было сделано в примере 5.20, нежелательно по ряду причин, включая время, 42б Глава 5. Синтаксически управляемая трансляция (йоа1, йоат) Т(йоа1 рв) ( йоаг 61, 62, д1, д2; /* Локальные переменные для высоты и глубины */ /* Начало кода г (рв) */ 11 ( Текуший символ == '(' ) ( Перемещение по входному потоку; (61, д1) = В(рв); Ы (Текущий символ 1= ')' ) Синтаксическая ошибка: требуется ')', Перемещение по входному потоку; е!ае 11 ( Текущий символ == гехт ) ( Обозначим значение техб/ехия/ как 1; Перемешение по входному потоку; 61 =- яе/Н/(рв, 1); д1 = де//зр(рв, 1); е1ае Синтаксическая ошибка: требуется гех1 или *)', /* Конец кода Е(рв) к/ Ы ( Текущий символ == япЬ ) ( Перемещение по входному потоку; (62, д2) = Т(0.7*рв) гегпгп (шах(61, 62 — 0.25 * рв), гпах(д1, д2 + 0.25 * рв)); гегпгп (61, д1); Рис.
5.30. Рекурсивный спуск для текстовых боксов необходимое для копирования и перемешения длинных строк. В распространенных случаях, таких как наш пример с генерацией кода, вместо этого можно инкрементно генерировать части кода с записью в массив или выходной файл при помощи действий из СУТ. Для этого требуется, чтобы выполнялось следующее. 1. Главный (гпа(п) атрибут для одного или нескольких нетерминалов. Для удобства будем считать, что все главные атрибуты представляют собой строковые значения. В примере 5.20 таковыми были атрибуты Я.соде и С.соде; прочие атрибуты не были главными. 2. Главные атрибуты являются синтезируемыми. 3.
Правила для вычисления главных атрибутов гарантируют следующее. а) Главный атрибут представляет собой конкатенацию главных атрибутов нетерминалов, имеющихся в теле соответствующей продукции, 427 5.5. Реализация 1.-атрибутных СУО Типы главных атрибутов Наше упрощающее предположение о том, что главные атрибуты представляют собой строки, слишком ограничительное. На самом деле типы главных атрибутов должны иметь значения, которые могут быть построены путем конкатенации элементов. Например, список обьектов любого типа вполне годится в качестве главного атрибута, поскольку список может быть представлен таким образом, что к его концу можно эффективно добавлять новые элементы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
