ГЛАВА 2

 

Простой

однопроходный

компилятор

 

Данная глава является вводной к главам 3-8 и представляет ряд базовых технологий компиляции, проиллюстрированных разработкой рабочей программы на С, которая транслирует инфиксные выражения в постфиксную форму. Здесь основное внимание уделяется предварительной стадии компиляции, т.е. лексическому анализу, разбору и генерации промежуточного кода. Главы 9, «Генерация кода», и 10, «Оптимизация кода» посвящены вопросам генерации и оптимизации кода.

 

 

2.1. Обзор

 

Язык программирования может быть определен с помощью описания того, как должна выглядеть программа (синтаксис языка) и что она означает (семантика языка). Для определения синтаксиса языка рекомендуем широко применяемую запись, называемую контекстно-свободной грамматикой, или BNF (Backus-Naur Form, форма Бэкуса-Наура). На сегодня описание семантики языка – гораздо более сложная задача, чем описание синтаксиса; для ее решения необходимо использовать неформальные описания и примеры.

Кроме определения синтаксиса языка, контекстно-свободная грамматика используется при трансляции программ. Грамматически управляемая технология компиляции, известная также как синтаксически управляемая трансляция (syntax-directed translation), очень полезна при разработке предварительной стадии компилятора и будет широко использоваться в данной главе.

В процессе обсуждения синтаксически управляемой трансляции мы построим компилятор, переводящий инфиксные выражения в постфиксные, в которых операторы появляются после своих операндов. Например, постфиксная форма выражения 9 - 5 + 2 выглядит как 9 5 - 2 +. Постфиксная запись может быть преобразована непосредственно в компьютерный код, который выполняет все необходимые вычисления с использованием стека. Давайте начнем с построения простой программы для трансляции в постфиксную форму выражений из цифр, разделенных знаками «плюс» и «минус». После того как станет понятна основная идея, мы расширим программу для обработки более общих конструкций языка программирования. Каждый из наших трансляторов будет представлять собой расширение предыдущего.

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

как числа, идентификаторы и ключевые слова. Для такого расширенного языка мы построим лексический анализатор, который будет накапливать последовательные символы из входного потока и преобразовывать их в токены. Детально построение такого лексического анализатора будет рассмотрено в главе 3, «Лексический анализ».

 




Рис 2.1. Структура предварительной стадии компилятора

 

2.2. Определение синтаксиса

 

В этом разделе для определения синтаксиса языка будет рассмотрен способ записи, называемый контекстно-свободной грамматикой (или, для краткости, просто грамматикой). Данный способ будет использоваться как часть спецификации, предварительной стадии компилятора на протяжении всей книги.

Грамматика естественным образом описывает иерархическую структуру множества конструкций языка программирования. Например, инструкция if-else в С имеет вид

 

if (выражение) инструкция else инструкция

 

Таким образом, инструкция if-else представляет собой ключевое слово if, за которым следует открывающая круглая скобка, выражение, закрывающая скобка, инструкция, ключевое слово else и еще одна инструкция (в С нет ключевого слова then). Используя переменную expr для обозначения выражения и переменную stmt для обозначения инструкции, можно записать это структурное правило так:

 

stmt if (expr) stmt else stmt                            (2.1)

 

Здесь символ (→) можно прочесть как «может иметь вид». Такое правило называется продукцией. (production). В продукции лексические элементы вроде ключевого слова if и скобок называются токенами. Переменные типа expr и stmt представляют последовательность токенов1 и называются нетерминальными символами, или просто нетерминалами (nonterminals).

 

Контекстно-свободная грамматика имеет четыре компонента.

 

1.             Множествотокенов, представляющих собой терминальные символы (или просто терминалы).

2.             Множество нетерминальных символов.

3.             Множество продукций, каждая из которых состоит из нетерминала,называемого левой частью продукции, стрелки и последовательности токенов и/или нетерминалов, называемых правой частью продукции.

4.             Указание одного из нетерминальных символов как стартового, или начального.

 

Следует придерживаться правила, согласно которому грамматика определяется перечислением ее продукций, причем первая продукция указывает стартовый символ. Цифры, знаки вроде <= и выделенные полужирным шрифтом типа while являются терминальными символами. Выделенные курсивом слова являются нетерминалами, а все слова, или символы, поданные без выделения, могут рассматриваться, как токены2. Для удобства записи правые части продукций с одними и теми же нетерминалами слева могут быть сгруппированы с помощью символа «|» («или»).

 

 


1 Вообще говоря, нетерминал представляет множество последовательностей токенов.Прим. ред.

2 Отдельные символы, выделенные курсивом, будут использоваться и для других целей при детальном изучении грамматики в главе 4, «Синтаксический анализ». Например, они будут применяться при указании символов, которые могут представлять собой либо токены, либо нетерминалы. Однако выделенное курсивом имя из двух или более символов будет всегда означать нетерминал.

 

 


Пример 2.1

В примерах этой главы используются выражения, состоящие из цифр и знаков «плюс» и «минус», например 9 - 5 + 2 , 3 - 1 или 7. Поскольку знаки «плюс» и «минус» должны располагаться между двумя цифрами, такие выражения можно рассматривать как списки цифр, разделенных знаками «плюс» и «минус». Синтаксис используемых выражений описывает грамматика из следующих продукций:

 

list            list + digit                                       (2.2)

list            list - digit                                        (2.3)

list            digit                                                (2.4)

digit            0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9            (2.5)

 

Правые части трех продукций с нетерминалом list в левой части могут быть объединены:

 

list list + digit | list - digit | digit

 

Здесь, в соответствии с нашими соглашениями, токенами грамматики являются символы

+  -  0  1  2  3  4  5  6  7  8  9

Нетерминальными символами являются выделенные курсивом имена list и digit, при этом нетерминал list – стартовый; именно его продукция дана первой.

Продукция называется продукцией нетерминала, если он записан в левой части. Строка токенов является последовательностью из нуля или нескольких токенов. Строка, содержащая нуль токенов и записываемая как e, называется пустой.

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

 

Пример 2.2

 

Язык, определяемый грамматикой из примера 2.1, состоит из списков цифр, разделенных знаками «плюс» и «минус».

Десять продукций для нетерминала digit позволяют ему быть любым из токенов 0, 1, …, 9. Из продукции (2.4) следует, что список может состоять из одной цифры, т.е. цифра сама по себе является списком. Продукции (2.2) и (2.3) выражают тот факт, что если мы возьмем любой список и добавим к нему знак «плюс» или «минус» с последующей цифрой, то получим новый список.

Оказывается, что продукции (2.2) - (2.5) – все, что надо для определения языка. Например, можно сделать вывод, что 9 – 5 + 2 является списком, следующим образом.

 

1.             9 – список в соответствии с продукцией (2.4), поскольку 9 – цифра

2.             9–5 – список в соответствии с продукцией (2.3), так как 9 – список, а 5 – цифра.

3.             9–5+2 – список в соответствии с продукцией (2.2), поскольку 9-5 – список, а 2 – цифра.

 

Данное утверждение продемонстрируем деревом, представленным на рис. 2.2. Каждый узел дерева помечен символом грамматики. Внутренний узел и его дочерние узлы соответствуют продукции, причем узел соответствует левой части продукции, а потомки – правой. Такие деревья называются деревьями разбора (parse trees); они будут рассмотрены ниже.

 

Дерево разбора выражения 9 – 5 + 2

Рис. 2.2. Дерево разбора выражения 9 – 5 + 2 в соответствии с грамматикой из примера 2.1

 

Пример 2.3

 

Еще один пример списков – последовательность инструкций, разделенных точками с запятыми; такую последовательность можно найти в Pascal, в блоке begin-end. Однако между токенами begin и end может и не быть инструкций. Разработку грамматики для блока begin-end можно начать со следующих продукций:

 

 block     begin opt_stmts end

opt_stmts     stmt_list|e

stmt_list     stmt_list ; stmt | stmt

 

Заметьте, что правой частью для opt_stmts может являться e, т.е. пустая строка символов. Таким образом, opt_stmts может быть заменено пустой строкой, и блок может оказаться строкой из двух токенов begin end. Обратите также внимание, что продукции для stmt_list аналогичны продукциям для list в примере 2.1 (точка с запятой вместо арифметической операции и с stmt вместо digit). В данном примере не представлены продукции для stmt, но далее вкратце будут рассмотрены продукции для различных инструкций, таких как инструкции присвоения, инструкции if и др.

 

Деревья разбора

 

Дерево разбора наглядно показывает, как стартовый символ грамматики порождает строку языка. Если нетерминал A имеет продукцию AXYZ, то дерево разбора может иметь внутренний узел A с тремя потомками, помеченными слева направо как X,Y и Z.

 

 

Формально для данной контекстно-свободной грамматики дерево разбора представляет собой дерево со следующими свойствами.

 

1.       Корень дерева помечен стартовым символом.

2.       Каждый лист помечен токеном или e.

3.       Каждый внутренний узел представляет нетерминальный символ.

4.       Если A является нетерминалом и помечает некоторый внутренний узел, а X1,X2 , …, Xn – отметки его дочерних узлов, перечисленные слева направо, то AX1X2Xn – продукция. Здесь X1, X2 , …, Xn могут представлять собой как терминальные, так и нетерминальные символы. В качестве специального случая продукции A e соответствует узел A с единственным дочерним узлом e.

 

Пример 2.4

 

На рис. 2.2 корневой узел помечен нетерминалом list, стартовым символом грамматики из примера 2.1. Дочерние узлы имеют отметки list, + и digit. Заметьте, что

list list + digit

является продукцией грамматики из примера 2.1. К левому дочернему узлу применен тот же шаблон, со знаком «минус» вместо знака «плюс». Все три узла, помеченные как digit, имеют по одному дочернему узлу с метками-цифрами.

Листья дерева разбора, читаемые слева направо, образуют крону (yield) дерева, которая представляет собой строку, выведенную, или порожденную из нетерминального символа в корне дерева. На рис 2.2 порожденная строка – 9-5+2. Здесь все листья показаны на одном, нижнем, уровне; в дальнейшем выравнивать листья деревьев таким образом не будем. Они должны рассматриваться в определенном порядке слева направо: если a и b – два дочерних узла одного родителя и узел a находится слева от b, то все потомки a будут находиться слева от любого потомка b.

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

 

Неоднозначность

 

Будьте предельно внимательны при рассмотрении структуры строки, соответствующей грамматике. Очевидно, что каждое дерево порождает единственную строку (путем считывания листьев этого дерева), однако для данной строки токенов грамматика может иметь более одного дерева. Такая грамматика называется неоднозначной. Чтобы убедиться в ее неоднозначности, достаточно найти строку токенов, которая имеет более одного дерева разбора. Поскольку такая строка обычно имеет не единственный смысл, следует использовать либо однозначные (непротиворечивые), либо неоднозначные грамматики с дополнительными правилами для разрешения неоднозначностей.

 

Пример 2.5

 

Предположим, что цифры и списки в примере 2.1 не различаются. Тогда грамматику можно записать следующим образом:

 

stringstring + string | string string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 

Объединение записей для digit и list в один нетерминальный символ string═ имеет кажущийся смысл, поскольку отдельная цифра является специальным случаем списка.

Однако из рис 2.3 видно, что выражение типа 9-5+2 теперь имеет больше одного дерева разбора. В данном случае два дерева разбора соответствуют двум вариантам расстановки скобок в выражении: (9 – 5) + 2 и 9 – (5 + 2). Это второе выражение дает в результате значение 2 вместо обычного 6. Грамматика в примере 2.1 не допускает такой интерпретации.

 

 
Рис. 2.3. Два дерева разбора для выражения 9- 5 + 2

 

Ассоциативность операторов

 

По соглашению 9+5+2 эквивалентно (9+5)+2, а 9-5-2 эквивалентно (9-5)-2. Когда операнд типа 5 имеет операторы и слева, и справа, необходимо установить, какой именно оператор использует этот операнд. Мы говорим, что оператор + левоассоциативен, поскольку операнд со знаками «плюс» с обеих сторон используется левым оператором. В большинстве языков программирования четыре арифметических оператора – сложение, вычитание, умножение и деление –  левоассоциативны.

Некоторые распространенные операторы, например возведение в степень, правоассоциативны. Другим примером правоассоциативного оператора может служить оператор присвоения (=) в С, где выражение a=b=c трактуется как a= (b=c).

Строки типа a=b=c с правоассоциативным оператором генерируются следующей грамматикой.

right  letter = right | letter

letter → a | b | … | z

Различия между деревьями разбора для левоассоциативных операторов типа «-» и правоассоциативных операторов вроде «=» показаны на рис 2.4. Обратите внимание, что дерево разбора для 9-5-2 растет вниз влево, в то время как дерево разбора для a=b=c – вниз вправо.

 

 

Рис.2.4. Деревья разбора для лево- и правоассоциативных операторов

 

Приоритет операторов

 

Рассмотрим выражение 9 + 5 * 2, которое можно интерпретировать как (9 + 5) * 2 и 9 + (5 * 2). Ассоциативность + и * не позволяет разрешить эту неоднозначность. Поэтому необходимо знать о приоритетах операторов.

Мы говорим, что оператор * имеет более высокий приоритет, чем +, если * получает свои операнды раньше +. В обычной арифметике умножение и деление имеют более высокий приоритет, чем сложение и вычитание. Таким образом, 5 является множителем в умножении как в случае с 9 + 5 * 2, так и 9 * 5 + 2, т.е. эти выражения эквивалентны 9 + (5 * 2) и (9 * 5) + 2 соответственно.

 

Синтаксис выражений

 

Грамматика арифметических выражений может быть построена на основе таблицы, показывающей ассоциативность и приоритет операторов. Начнем с четырех основных арифметических операторов и таблицы приоритетов, представляющей операторы в порядке увеличения приоритетов (операторы, расположенные в одной строке, имеют одинаковый приоритет).

 

Левоассоциативные:        +        

Левоассоциативные:      *         /

 

Создадим два нетерминалаexpr и term – для этих уровней приоритета и дополнительный нетерминал factor для генерации базовых составляющих в выражениях, в данном случае – цифр и выражений в скобках.

factor digit | (expr)

Теперьрассмотрим бинарные операторы * и /, которые имеют наивысший приоритет. Поскольку эти операторы левоассоциативны, продукции подобны продукциям для списков, которые также левоассоциативны.

 

term          term * factor

|         term / factor

|         factor

 

Точно так же expr рассматривается как список элементов term, разделенных операторами сложения или умножения.

 

expr         expr + term

|         exprterm

|         term

 

В результате грамматика выглядит следующим образом.

 

expr          expr + term | expr | term | term

term          term* factor | term / factor | factor

factor           digit | ( expr )

 

Эта грамматика рассматривает выражение как список элементов, разделенных знаками + и –. При этом каждый элемент списка представляет собой список множителей, разделенных знаками * и /. Обратите внимание, что любое выражение в скобках является множителем, поэтому с помощью скобок можно создать выражение с любым уровнем вложенности (и, соответственно, произвольной высоты дерева).

Синтаксис инструкций

В большинстве языков распознать инструкции можно с помощью ключевых слов. Например, все инструкции Pascal начинаются с ключевого слова, за исключением присвоения и вызова процедур. Некоторые из инструкций Pascal определяются следующей (неоднозначной) грамматикой, в которой токен id представляет идентификатор.

stmt           id : = expr

|              if exprthenstmt

|              if exprthenstmtelsestmt

|              while expr do stmt

|              begin opt_stmts end

Нетерминальный символ opt_stmts порождает список инструкций (возможно, пустой), разделенных точками с запятой, с использованием продукций из примера 2.3.

2.3. Синтаксически управляемая трансляция

Для трансляции конструкций языка программирования компилятору, помимо генерации кода, может потребоваться отследить множество различных параметров. Например, компилятору может понадобиться информация о типе конструкции, расположении первой инструкции в целевом коде или количестве сгенерированных инструкций. Таким образом, можно говорить о некоторых абстрактных атрибутах, связанных с языковыми конструкциями, – типах, строках, адресах памяти и др.

В этом разделе будет рассмотрено синтаксически управляемое определение (syntax-directed definition), предназначенное для определения трансляции конструкций языка программирования. Синтаксически управляемое определение задает трансляцию конструкции в терминах атрибутов, связанных с ее синтаксическими компонентами. Позже синтаксически управляемые определения будут использованы для определения ряда трансляций в предварительной стадии компиляции.

Для определения трансляции воспользуемся более процедурно ориентированной записью, называемой схемой трансляции. В данной главе эти схемы используются для перевода инфиксных выражений в постфиксную запись. Более детальное обсуждение синтаксически управляемых определений и их реализации содержится в главе 5, «Синтаксически управляемая трансляция».

Постфиксная запись

Постфиксная запись (postfix notation) выражения Е может быть индуктивно определена следующим образом.

1.                 Если Е является переменной или константой, то постфиксная запись E представляет собой Е.

2.                 Если E – выражение вида E1 ор Е2,гдеор– произвольный бинарный оператор, то постфиксная запись E представляет собой E1E2 ор, где E1' и E2' – постфиксные записи для E1 и E2 соответственно.

3.                 Если E – выражение вида (E1), то постфиксная запись для E1 представляет собой также и постфиксную запись для E.

Скобки в постфиксной записи не используются; последовательность и количество аргументов операторов допускают только один способ декодирования постфиксного выражения. Например, постфиксной записью для (9-5) +2 является 95-2+, а для 9- (5+2) -952+-.

Синтаксически управляемые определения

Синтаксически управляемое определение (syntax-directed definition) использует контекстно-свободную грамматику для определения синтаксической структуры входа. С каждым символом грамматики оно связывает набор атрибутов, а с каждой продукцией - набор семантических правил для вычисления значений атрибутов, связанных с используемыми в продукциях символами. Грамматика и набор семантических правил составляют синтаксически управляемое определение.

Трансляция представляет собой отображение входного потока информации в выходной. Выход для каждого входа x определяется следующим образом. Вначале для x строится дерево разбора. Предположим, что в этом дереве узел n помечен символом грамматики X. Для указания значения атрибута a этого узла используем запись Х.а. Значение Х.а в n вычисляется с помощью семантического правила для атрибута а, связанного с X-продукцией в узле п. Дерево разбора, указывающее значения атрибутов в каждом узле, называется аннотированным (annotated).

Синтезируемые атрибуты

Об атрибуте говорят, что он синтезируемый,если его значение в узле дерева разбора определяется значениями атрибутов в дочерних узлах. Синтезируемые атрибуты хороши тем, что вычисляются в процессе одного подхода снизу вверх по дереву разбора. В этой главе используются только синтезируемые атрибуты; «наследуемые» атрибуты рассматриваются в главе 5, «Синтаксически управляемая трансляция».

Пример 2. 6

Синтаксически управляемое определение для трансляции выражений, состоящих из цифр, разделенных знаками «плюс» и «минус», в постфиксную форму показано на рис. 2.5. Связанный с каждым нетерминалом строковый атрибут t представляет постфиксную запись, для выражения, порождаемого этим нетерминалом в дереве разбора.

Продукция

Семантическое правило

eхрr expr1 + term

expr.t := expr1. t || term.t || ‘+’

expr expr1 -term

expr.t := expr1.t || term.t || ‘-‘

eхрr term

expr.t :=term.t

term 0

term.t := 0

term 1

term.t:= 1

term 9

term.t :=9

Рис. 2.5. Синтаксически управляемое определение для трансляции инфиксной записи в постфиксную.

Постфиксная форма цифры - это сама цифра. Итак, семантическое правило продукции term → 9 определяет, что при ее использовании term.t в узле дерева разбора представляет собой просто 9. При использовании продукции exprterm значение term.t становится значением expr.t.

Продукция exprexpr1 + term порождает выражение, содержащее оператор "плюс" (индекс в ехрr1 позволяет отличить левую часть выражения от правой). Левый операнд оператора сложения- expr1, а правый- term. Семантическое правило данной продукции

expr.t := expr1.t || term.t || ‘+’

определяет значение атрибута expr.t путем конкатенации постфиксных форм expr1.t и term.t левого и правого операндов, к которым затем добавляется знак «плюс». Оператор «||» в семантических правилах представляет конкатенацию строк.

На рис. 2.6 представлено аннотированное дерево разбора, соответствующее дереву на рис. 2.2. Значение атрибута t в каждом узле вычислялось с использованием семантического правила, связанного с продукцией данного узла. Значение атрибута в корне представляет собой постфиксную запись строки, порождаемой деревом разбора.

 

Рис. 2.6. Значение атрибутов в узлах дерева разбора

Пример 2.7

Рассмотрим пример с роботом, которому можно указать перемещения из исходного положения на один шаг на восток (east), север (north), запад (west) или юг (south). Последовательность таких инструкций порождается следующей грамматикой.    

seq      seq instr | begin

instr    east | north | west | south

Изменения положения робота при обработке входной последовательности

begin west south east east east north north

приведены на рис. 2.7

 

 

Рис. 2.7. Траектория перемещения робота

 

На рисунке положение робота определяется парой значений (x), где x иy ― количество шагов от стартовой позиции на восток и на север соответственно (если значение x отрицательно, то робот находится западнее стартовой позиции, если у отрицательно - южнее).

Построим синтаксически управляемое определение для трансляции последовательности инструкций в позицию робота. Для отслеживания положения робота в процессе порождения последовательности инструкций нетерминалом seq будем использовать два атрибута, seq.x и seq.y. Изначально, при генерации begin, seq.x и seq.y принимают значения 0, как показано в левом внутреннем узле дерева для последовательности begin west south (рис. 2.8).

 

Рис. 2.8. Аннотированное дерево разбора для последовательности begin west south

Изменение положения с учетом отдельных инструкций определяется атрибутами instr.dx иinstr.dy. Например, если instr принимает значение west, то instr.dx =-1, a instr.dy = 0. Предположим, что последовательность seq формируется следующей за последовательностью seq1 новой инструкцией instr . В таком случае новое положение робота определяется правилами

seq.x := seq1 .x + instr.dx

seq.y := seq1.y+instr.dy

Синтаксически управляемое определение для трансляции последовательности инструкций в позицию робота показано на рис. 2.9.

Продукция

Семантические правила

seq begin

seq.x := 0

seq.y := 0

seq seq1 instr

seq.x := seq1.x+ instr.dx

seq.у := seq1.y + instr. dy

instr east

instr.dx := 1

instr dy := 0

instr north

instr. dx := 0

instr.dy := 1.

instr west

instr.dx := -1

instr.dy := 0

instr south

instr. dx := 0

instr.dy := -1

Рис 2.9. Синтаксически управляемое определение положения робота

Рекурсивный обход дерева

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

В данной главе все трансляции могут быть реализованы применением семантических правил вычисления атрибутов в дереве разбора по определенному порядку. Обход (traversal) дерева начинается с корня и состоит в посещении каждого узла дерева в определенном порядке. В данной главе семантические правила применяются с использованием рекурсивного обхода, показанного на рис. 2.10. Он начинается в корне дерева и рекурсивно проходит в порядке слева направо по всем дочерним узлам данного узла, как показано на рис. 2.11. Семантические правила в данном узле применяются после посещения всех его потомков. Этот обход имеет также название "сперва вглубь", или "в глубину" (depth-first), поскольку в первую очередь посещаются еще не пройденные дочерние узлы.

procedure visit(n: node);      

begin

for каждый дочерний узел m узла n в порядке слева направо

do

visit (m);

применить семантические правила в узле _n

end

Рис. 2.10. Рекурсивный обход дерева «в глубину»

Рис. 2.11. Пример рекурсивного обхода дерева "в глубину"

 

 

Схемы трансляции

В этой главе для определения трансляции будет использована процедурная спецификация. Схема трансляции является контекстно-свободной грамматикой, в которой программные фрагменты, называемые семантическими действиями (semantic , actions), вставлены в правые части продукций. Схема трансляции подобна синтаксически управляемому определению, однако здесь явно указан порядок применения семантических правил. Выполнение семантических действий указывается с помощью фигурных скобок в правой части продукции:

rest -> + term { print('+') } rest1

Схема трансляции порождает выход для каждого предложения x грамматики путем выполнения действий в том порядке, в каком они появляются при обходе в глубину дерева разбора для х. Рассмотрим дерево разбора с узлом rest, представляющее указанную продукцию. Действие {print('+')} будет выполнено после обхода поддерева для элемента term,но до посещения узла rest1.

Рис. 2.12. Дополнительные листы дерева для семантических действий

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

Вывод результатов трансляции

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

Заметим, что упомянутые синтаксически управляемые определения имеют одно важное свойство. Строка, представляющая трансляцию нетерминала в левой части каждой продукции, является конкатенацией трансляций нетерминалов справа в том же порядке, что и в продукции, возможно, с некоторыми дополнительными строками между ними. Синтаксически управляемое определение, обладающее таким свойством, называется простым (simple). Рассмотрим первую продукцию и семантическое правило из синтаксически управляемого определения на рис. 2.5.

Продукция    Семантическое правило

expr ->expr1 + term expr.t := expr1.t || term.t||'+'        (2.6)

Здесь трансляция expr.t представляет собой конкатенацию трансляций expr1 и term, за которыми следует символ +. Заметим, что expr1 появляется в правой части продукции перед term.

Дополнительная строка появляется между term.t и rest1.t.

Продукция Семантическое правило

rest term rest1,        rest.t := term.t ||'+'|| rest1.t (2.7)

Однако и в этом случае нетерминал term располагается в правой части перед rest1. Простые синтаксически управляемые определения могут быть реализованы схемами трансляции, в которых действия выводят дополнительные строки в порядке их появления в определении. Действия в следующих продукциях выводят дополнительные строки в (2.6) и (2.7) соответственно.

expr      expr1+ term {print('+') }

rest       + term {print('+')} rest1

Пример 2.8

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

expr             expr + term    {print (‘+’)}

expr             expr - term      {print (‘-’)}

expr             term

term            0         {print (‘0’)}

term            1         {print (‘1’)}

...

term            9         {print (‘9’)}

Рис. 2.13. Действия, транслирующие выражения в постфиксную запись

 

Рис. 2.14. Действия, транслирующие 9-5+2 в 95-2+

На рис. 2.14 корень представляет первую продукцию рис. 2.13. При рекурсивном обходе вглубь вначале выполняем все действия в поддереве левого операнда.expr (при обходе левого поддерева корня). Затем переходим в лист +, где действия отсутствуют, осуществляем все действия в поддереве правого операнда term и, наконец, выполняем семантическое действие {print('+')} в дополнительном узле.

Продукции для term имеют в правой части только цифры, которые выводятся соответствующими действиями. Продукция exprterm не осуществляет никакого вывода, а действием для первых двух продукций является вывод соответствующего оператора. Действия, выполняемые при рекурсивном обходе дерева разбора (рис. 2.14) вглубь, приводят к выводу 95-2+.

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

2.4. Разбор

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

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

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

Большинство методов разбора делится на два типа – нисходящие (сверху вниз, top-down) и восходящие (снизу вверх, bottom-up). Это связано с порядком, в котором строятся узлы дерева разбора. При первом методе построение начинается от корня по направлению к листьям, в то время как при втором методе – от листьев по направлению к корню. Популярность анализаторов "сверху вниз" обусловлена тем фактом, что построить эффективный анализатор вручную проще с использованием методов "сверху вниз". Однако разбор "снизу вверх" может работать с большим классом грамматик и схем трансляции, так что программный инструментарий для генерации анализаторов непосредственно по грамматикам тяготеет к восходящим методам.

Нисходящий анализ

Для ознакомления с нисходящим анализом начнем с рассмотрения грамматики, которая хорошо подходит для методов разбора этого типа (позже будет рассмотрено построение нисходящих анализаторов в целом). Приведенная ниже грамматика генерирует подмножество типов языка Pascal. Для ". ." воспользуемся токеном dotdot, чтобы подчеркнуть, что данная последовательность символов трактуется как единое целое.

type                  simple

|        id

|        array [ simple ] of type

simple               integer

|        char

|        num dotdot num

Построение дерева разбора сверху вниз начинается с корня, помеченного стартовым нетерминалом, и осуществляется многократным выполнением следующих двух шагов (рис. 2.15).

1.   В узле n, помеченном нетерминалом А, выбираем одну из продукций для А и строим дочерние узлы для символов из правой части продукции.

2.   Находим следующий узел, в котором должно быть построено поддерево.

Рис. 2.15. Шаги построения дерева разбора сверху вниз

 

В некоторых грамматиках описанные шаги могут быть реализованы во время однократного сканирования входной строки слева направо. Текущий токен называют cкaнируемым символом, или "предсимволом" (lookahead symbol ≈дословно: предвиденный символ. – Прим. перев.). Изначально текущим символом является первый, т.е. самый левый токен входной строки. На рис. 2.16 проиллюстрирован анализ строки

array [ num dotdot num] of integer

Изначально текущим сканируемым символом является токен arraу, а извеcтнaя часть дерева разбора состоит из корня, помеченного как стартовый нетерминал type (рис. 2.16a). Задача состоит в построении остальной части дерева разбора таким образом, чтобы строка, порожденная деревом разбора, совпадала с входной строкой.

 

Рис. 2.16. Нисходящий анализ при сканировании входного потока слева направо

Чтобы соответствовать входной строке, нетерминал type (рис. 2.16а) должен выводить строку, начинающуюся со сканируемого символа array. В грамматике (2.8) для type имеется только одна продукция, которая способна породить такую строку. Нужно выбрать эту продукцию и построить дочерние по отношению к корню узлы, помеченные символами из правой части продукции.

На каждом из трех "снимков" (рис. 2,16) имеются стрелки, указывающие сканируемый символ входного потока и рассматриваемый узел дерева разбора. После построения всех дочерних узлов текущего узла переходим к рассмотрению самого левого дочернего узла. На рис.2.16б показан именно этот этап, когда построены дочерние по отношению к корню узлы и мы переходим к рассмотрению самого левого дочернего узла, а именно – array.

Если рассматриваемый узел дерева разбора соответствует терминалу, а этот терминал совпадает со сканируемым символом, можно продвигаться вперед как по дереву разбора, так и по входному потоку. Следующий токен из входного потока становится текущим скaниpуемым cимволом, и мы приступаем к рассмотрению следующего дочернего узла. На pис.2.16в стрелка в дeрeвe разбора перемещается к следующему дочернему по отношению к корню узлу, а стрелка во входном потоке – к следующему токену [. После следующего перемещения стрелка в дереве разбора будет указывать на узел, помеченный как нетерминал simple. При рассмотрении узла, помеченного нетерминалом, процесс выбора продукции повторяется.

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

Предиктивный анализ

Анализ методом рекурсивного спуска (recursive-descent parsing) представляет собой способ нисходящего синтаксического анализа, при котором выполняется ряд рекурсивных процедур для обработки входного потока (процедура связана с каждым нетерминальным символом грамматики). Здесь будет рассмотрен специальный вид анализа методом рекурсивного спуска, именуемый предиктивным (или предсказывающим) анализом, при котором сканируемый символ однозначно определяет процедуру, выбранную для каждого нетерминала. Последовательность процедур, вызываемых при обработке входного потока, неявно определяет его дерево разбора.

procedure match(t: token);

begin

if lookahead = t then

lookahead : = nexttoken

else error

end;═

 

procedure type;══

begin

if lookahead is in { integer, char, num } then═══

simple

else if lookahead = '↑' then begin

match('↑');match (id)══

end

else if lookahead = array then begin

match (array);match ('[');

simple; match (']'); match (of); type

end

else error

end;

 

procedure simple;

begin

if lookahead = integer then

match (integer)

else if lookahead = char then

match (char)

else if lookahead = num then begin

match(num);match(dotdot);match (num)

end═

else error

end;

 

Рис.2.17. Псевдокод предиктивного анализатора

 

Предиктивный анализатор (рис. 2,17) состоит из процедур для нетерминальных символов type и simple грамматики (2.8) и дополнительной процедуры match. В данном случае match используется для упрощения кода процедур type и simple; эта процедура переходит к следующему входному токену, если ее аргумент t совпадает со сканируемым символом. Таким образом, match изменяет переменную lookahead, которая представляет собой текущий сканируемый входной токен.

Разбор начинается с вызова процедуры для стартового нетерминала грамматики type. При том же входном потоке, что и на рис. 2.16, lookahead изначально принимает значение, равное первому токену входной строки ≈ array. Процедура type выполняет код

matсh(array);.match('['); simple;match( ']'); match(of); type ═(2.9)

который соответствует правой части продукции

type array [ simple ] of type

Заметим, что каждый терминал в правой части соответствует сканируемому символу, а каждый нетерминал правой части приводит к вызову связанной с ним процедуры.

При входном потоке, показанном на рис. 2.16, после того как выявлено соответствие токенов array и [, текущим сканируемым символом становится num. В этот момент вызывается процедура simple, в которой выполняется код

match(num);match(dotdot);match(num)

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

type simple                              (2.10)

Эта продукция используется тогда, когда текущий сканируемый символ может быть порожден из simple. Предположим, что в процессе выполнения фрагмента кода (2.9) в момент вызова процедуры type текущий сканируемый символ – integer. Для нетерминального символа type нет ни одной продукции, начинающейся с токена integer. Однако такая продукция имеется для нетерминала simple, поэтому в процедуре type при значении lookahead, равном integer, выполняется вызов процедуры simple.

Предиктивный анализ базируется на информации о том, какой первый символ может быть порожден правой частью продукции. Более строго, пусть α – правая часть продукции для нетерминала А. Определим FIRST(α) как множество токенов, которые могут появиться в качестве первого символа одной или нескольких строк, полученных из α. Если α представляет собой ε или может порождать ε, то ε также входит в FIRST(α)3. Например,

FIRST(simple)            =          { integer, char, num }

FIRST(↑id)              {↑}

FIRST(array [ simple ] of type )  =          { array }

 

 

На практике многие правые части продукций начинаются с токенов, что упрощает построение множеств FIRST. Алгоритм для построения FIRST приводится в разделе 4.4.

МножестваFIRST следует рассматривать, если имеются две продукции Аα и А → β. Анализ методом рекурсивного спуска без отката требует, чтобы множества FIRST(α) и FIRST(β) были непересекающимися. Тогда текущий сканируемый символ может использоваться для принятия решения, какая из продукций будет применена. Если сканируемый символ принадлежит множеству FIRST(α), используется продукция α; в противном случае, когда сканируемый символ принадлежит множеству FIRST(β), применяется продукция β.

________________________________________________________________

3 Продукция с ε в правой части усложняет определение первых символов, порождаемых нетерминалами. Например, если из нетерминала В можно вывести пустую строку и имеется продукция А → ВС, то первый символ, порождаемый С, может быть первым символом, порождаемым А. Если С также порождает ε, то и FIRST(A), и FIRST(BC) содержат ε.

 

Использование ε-продукций

Продукциис ε в правой части требуют специальной трактовки. Анализатор методом рекурсивного спуска использует такую продукцию в качестве продукции по умолчанию,

когда не может быть использована никакая другая. Рассмотрим

stmt        begin opt_stmts end

opt_stmts         stmt_list | ε

Если при анализе opt_stmts сканируемый символ не принадлежит множеству FIRST(slmt_list), то используется ε-продукция. Такой выбор совершенно верен, когда сканируемый символ – end. Любой другой символ приведет к ошибке, обнаруживаемой в процессе анализа stmt.

Создание предиктивного анализатора

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

1.   Принимает решение, какая продукция будет использоваться, исходя из текущего сканируемого символа. Если сканируемый символ принадлежит множеству FIRST(α), применяется продукция с правой частью α. Продукция с ε в правой части используется в случае, когда текущий сканируемый символ не принадлежит множеству FIRST для любой другой правой части. В случае конфликта двух правых частей продукций для некоторого сканируемого символа этот метод анализа неприменим для рассматриваемой грамматики.

2.   Использует продукцию, имитируя ее правую часть. Нетерминал приводит к вызову процедуры, соответствующей этому нетерминалу, а токен, совпадающий с текущим сканируемым символом, ≈ к чтению следующего токена из входного потока. Если в какой-то момент токен продукции не совпадает со сканируемым, символом, вызывается процедура обработки ошибки. На рис. 2.17 представлен результат применения этих правил к грамматике (2.8).

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

1.   Построить предиктивный анализатор, игнорируя действия в продукциях.

2.   Скопировать действия из схемы трансляции в анализатор. Если действие в продукции р находится после символа грамматики Х, то оно копируется после кода, реализующего Х. В противном случае, если это действие располагается в начале продукции, оно копируется непосредственно перед кодом, реализующим продукцию.

Такой транслятор будет построен в следующем разделе.

Левая рекурсия

Анализатор, работающий методом рекурсивного спуска, может оказаться в состоянии зацикливания при работе с леворекурсивной продукцией типа

ехрr eхрr + term

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

Pис.2.18. Лeвo- и пpaвopeкуpcивныe cпocoбы гeнepaции сmpoки

 

Леворекурсивных продукций можно избежать, переписав продукции, доставляющие неприятности. Рассмотрим нетерминал А с двумя продукциями

А → Аα | β

где α и β представляют собой последовательности терминалов и нетерминалов, которые не начинаются с А. Например, в

ехрrехрr + term | term

A = expr, α = + term и β = term.

Нетерминал A левокурсивен, поскольку продукция ААα в качестве крайнего левого символа правой части содержит А. При повторном применении этой продукции создается последовательность α справа от А, как показано на рис.2.18а. Когда, наконец, А будет заменено на β получим β, за которой будет следовать нуль или несколько α.

Тот же результат можно получить, как показано на рис.2.18б, записав продукции для А следующим образом.

А → β R

R α R | ε                                  (2.11)

ЗдесьR – новый нетерминал. Продукция R αR представляет собой правую рекурсию, поскольку продукция для R в качестве крайнего справа символа правой части содержит R. Праворекурсивные продукции приводят к деревьям, которые растут вниз вправо, как показано на рис. 2.18б. Такие деревья затрудняют трансляцию выражений, содержащих левоассоциативные операторы, например, оператор вычитания. Однако в следующем разделе мы увидим, что корректной трансляции выражений в постфиксную запись можно добиться аккуратным построением схемы трансляции, основанной на праворекурсивной грамматике.

В главе 4, «Синтаксический анализ», мы рассмотрим более общие виды левой рекурсии и покажем, как устранить левую рекурсию из грамматики.

2.5. Транслятор для простых выражений

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

expr                 expr + term { print(‘+’) }

expr                  expr - term { print(‘-‘) }

expr                term

term          0    { print(‘0’) }

term          1    { print(‘1’) }

term          9    { print(‘9’) }

 

Рис. 2.19. Начальная спецификация транслятора инфиксной записи в постфиксную

Схема синтаксически управляемой трансляции часто может служить в качестве определения транслятора. В данном случае мы используем схему, приведенную нa рис. 2.19 (повторяющем рис. 2.13). Зачастую грамматика, лежащая в основе данной схемы, требует модификации перед тем, как сможет быть разобрана предиктивным анализатором. В частности, грамматика, лежащая в основе схемы, представленной на рис.2.19, леворекурсивна, но, как видно из предыдущего раздела, предиктивный, анализатор не может работать с леворекурсивной грамматикой. Устранив леворекурсивность, мы получим грамматику, пригодную для использования предиктивного анализатора, работающего методом рекурсивного спуска.

Абстрактный и конкретный синтаксис

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

Риc. 2.20 .Cинтакcичecкoe дepeвo для выpaжeния 9 - 5 + 2

 

Например, на рис.2.20 показано синтаксическое дерево для выражения 9-5+2. Поскольку + и - имеют один и тот же приоритет, а операторы с равным приоритетом выполняются слева направо, в дереве 9-5 сгруппировано в качестве подвыражения. Сравнивая рис. 2.20 с рис. 2.2, заметим, что синтаксическое дерево связывает оператор с внутренним узлом, а не представляет его в виде одного из дочерних узлов.

Желательно, чтобы схема трансляции базировалась на грамматике, деревья разбора которой были бы по возможности ближе к синтаксическим деревьям. Группирование подвыражений грамматикой (рис. 2.19) похоже на их группирование в синтаксических деревьях. К сожалению, грамматика на рис. 2.19 леворекурсивна, а следовательно, предиктивный анализ к ней неприменим. Итак, с одной стороны, нам нужна грамматика, упрощающая процесс разбора, с другой – для простоты трансляции требуется совершенно другая грамматика. Очевидное разрешение этого противоречия состоит в устранении леворекурсивности грамматики. Однако, как показано в следующем примере, это нужно делать предельно аккуратно и осторожно.

Пример 2.9

Приведенная ниже грамматика не подходит для трансляции выражений в постфиксный вид, хотя она порождает в точности тот же язык, что и грамматика на рис. 2.19, и может использоваться для анализа методом рекурсивного спуска.

eхрr                  term rest

rest                    + ехрr | - ехрr | ε

term                  0 | 1 | ... | 9

Проблема этой грамматики в том, что операнды операторов, порождаемых продукциями rest → + expr и rest → - ехрr, не очевидны из самих продукций. Ни один из приведенных ниже вариантов получения трансляции rest.t из трансляции expr.t не является приемлемым.

rest →       - expr {rest.t := '-' || expr.t}                 (2.12)

rest →       - expr {rest.t := expr.t || '-' }                (2.13)

(Здесь приведены продукции и семантические действия только для оператора "минус".) Трансляция 9-5 в постфиксную форму дает 95-, однако, если использовать действие из (2.12),'знак "–" появляется перед ехpr.t и 9-5 не изменяется после трансляции.

При использовании (2.13) и аналогичного правила для знака "+" операторы последовательно перемещаются к правому концу, и 9-5+2 транслируется в 952+- (в то время как корректной является трансляция 95-2+).

Адаптация схемы трансляции

Технология устранения леворекурсивности, схематически изображенная на рис. 2.18, может быть применена к продукциям, содержащим семантические действия. Воспользуемся преобразованиями из раздела 5.5 при работе с синтезируемыми атрибутами. Эта технология преобразовывает продукции А→Аa½Аb½gв

А→           gR

R           aR½bR½e

При работе с семантическими действиями мы переносим их в преобразованные продукции. В данном случае А = expr,a = + term { print(‘+’) }, b = -term { print(‘-’) } и g=term и описанное выше преобразование приводят к схеме трансляции (2.14). Продукции для expr (рис.2.19) преобразуются в продукции для expr и нового нетерминала rest (2.14). Продукции для term повторяют продукции для term из рис. 2.19. Обратите внимание, что лежащая в основе схемы грамматика отличается от описанной в примере 2.9, и эти отличия делают возможной требуемую трансляцию.

expr      term rest

rest        + term { print(‘+’) } rest ½ { print(‘-’) } rest ½ e

term      0{ print(‘0’) }

term      1{ print(‘1’) }

                  ………

term     9 { print(‘9’) }

На рис. 2.21 показано, каким образом описанная грамматика транслирует 9-5+2.

Рис. 2.21. Трансляция 9-5+2 в 95-2+

Процедуры для нетерминалов expr, term и rest

Теперь приступим к реализации транслятора на С с использованием синтаксически управляемой схемы трансляции (2.14). Квинтэссенция транслятора – код функций expr, term и rest на языке С (рис. 2.22). Эти функции реализуют соответствующие нетерминалы в (2.14).

expr()

{

term ();   rest ();

}

rest ()

{

if (lookahead) = =  ‘+’)  {

match ( ‘+’ ) ;  term( ) ;

putchar ( ‘+’ ) ;  rest ( ) ;

}

else  if  (lookahead  = =  ‘-‘ )  {

match ( ‘-’ ) ;  term ( ) ;

putchar ( ‘-’ ) ;  rest ( ) ;

}

else  ;

}

term ( )

{

if  (isdigit (lookahead) )  {

putchar (lookahead) ;

match (lookahead) ;

}

else error ( ) ;

}

Рис. 2.22. Функции для нетерминалов expr, rest и term

Функцияmatch, которая будет представлена позже, является С-эквивалентом части кода на рис. 2.17. Данная часть кода отвечает за проверку соответствия токена текущему сканируемому символу и перемещение по входному потоку. Поскольку в данном случае каждый токен представляет собой отдельный символ, функция match может быть реализована простым сравнением и считыванием  символов.

Для тех, кто незнаком с языкам программирования С, вкратце опишем основные различия между С и другими производными от Algol языками программирования, такими как Pascal. Программа на языка С состоит из последовательности определений функций; работа программы начинается с выполнения специальной функции main. Определения функций не могут быть вложенными. Аргументы функций указываются в круглых скобках (они необходимы даже в том случае, когда никакие аргументы функции не передаются, именно поэтому мы и пишем expr( ), term( ) и rest( )). Функции сообщаются друг с другом либо путем передачи параметров «по значению», либо с помощью глобальных данных, доступным всем функциям. Например, функции term( ) и rest( ) работают с текущим сканируемым символом с помощью глобальной переменной lookahead.

С и Pascal используют разные символы для присвоения и проверки равенства.

Операция

C

Pascal

Присвоение

=

: =

Проверка равенства

= =

=

Проверка неравенства

! =

< >

 

Рис. 2.23. Вид функции expr ( ) после оптимизации

Функции для нетерминалов имитируют правые части продукций. Например, продукция expr term rest реализуется путем вызовов term( ) и rest( ) в функции expr( ).

В качестве другого примера рассмотрим функцию rest( ), которая использует первую продукцию для rest из (2.14), если текущий сканируемый символ представляет собой знак «+», вторую продукцию – в случае знака «-» и продукцию rest ε по умолчанию. Первая продукция реализуется первой инструкцией if на рис. 2.22. Если сканируемый символ – «плюс», его соответствие токену и перемещение по входному потоку выполняется вызовом match(‘+’). После вызова term( ) стандартная библиотечная функция С putchar(‘+’) выполняет семантическое действие, путем вывода символа «плюс». Поскольку последняя продукция для rest представляет собой ε, последняя инструкция else в функции rest( ) не выполняет никаких действий.

Десять продукций term порождают десять цифр. На рис. 2.22 подпрограмма isdigit проверяет, является ли сканируемый символ цифрой. Если да, функция term( ) выводит этот символ и вызывает функцию match( ) для перемещения по входному потоку к следующему символу. Если же считанный символ – не цифра, значит, произошла ошибка. (Обратите внимание: поскольку вызов match( ) изменяет текущий сканируемый символ, печать цифры должна производиться до этого вызова.) Перед тем как создать полную программу, осуществим некоторые улучшения кода (рис. 2.22) в целях повышения его быстродействия.

Оптимизация транслятора

Некоторые рекурсивные вызовы можно заменить итерациями. Когда рекурсивный вызов текущей процедуры производится ее последней инструкцией, говорим об оконечной рекурсии (tail recursion). Например, вызовы rest( ) в пятой и девятой строках ее кода представляют собой оконечную рекурсию, поскольку после каждого такого вызова происходит выход из функции. Можно ускорить работу программы, заменив оконечную рекурсию итерацией. В случае вызова процедуры без передачи ей параметров оконечная рекурсия может быть просто заменена безусловным переходом к началу процедуры, и код при этом будет выглядеть следующим образом.

rest ( )

{

L:        if (lookahead = = ‘+’)  {

match (‘+’); term( );

putchar (‘+’); goto L;

}

else if (lookahead = = ‘-’)  {

match(‘-’); term( );

putchar (‘-’); goto L;

}

else;

}

 

До тех пор, пока сканируемый символ представляет собой знак «плюс» или «минус», функция rest( ) вызывает функцию match( ), передавая ей в качестве параметра символ, затем функцию term( ) для обработки цифры и повторяет процесс. Замети, поскольку функция match( ) переходит к следующему символу входного потока, описанный цикл будет выполняться только при чередующейся последовательности цифр и знаков. Если внести описанные изменения в исходный текст (рис. 2.22), то увидим, что единственный вызов функции rest( ) имеется в функции expr( ), в третьей строке кода. Таким образом, две функции можно объединить в одну, как показано на рис. 2.23. Кроме того, в С циклическое выполнение инструкции stmt обеспечивается записью

while(1) stmt

поскольку условие 1 всегда истинно. Выйти из цикла можно с помощью оператора break4. В результате, код функции rest( ) приобретает вид, приведенный на рис. 2.23.

expr( )

{

term( );

while(1)

if (lookahead = = ‘+’)  {

match(‘+’); term ( ); putchar(‘+’);

}

else if (lookahead = = ‘-’)  {

match(‘-’); term( ); putchar(‘-’);

}

else break;

}

Рис. 2.23. Вид функции expr( ) после оптимизации

____________________________________________

4 Все сказанное об инструкции while(1) справедливо и для инструкции for(;;). – Прим. ред.

Полная программа

Полностью код транслятора на языке С приведен на рис. 2.24. Первая строка, начинающаяся с #include, загружает <ctype.h> - файл, содержащий, помимо прочих стандартных подпрограмм С, код предиката isdigit.

Токены, состоящие из отдельных символов, поставляются стандартной библиотечной функцией getchar( ). Переменная lookahead описана как имеющая тип int, чтобы в дальнейшем, по мере развития программы, она могла хранить и другие токены. Поскольку переменная описана вне тела любой из функций, она является глобальной и может использоваться любой функцией, определенной после второй строки программы.

Функцияmatch ( ) проверяет соответствие текущего сканируемого символа токену и в случае соответствия считывает из входного потока следующий символ, а в ином случае вызывает функцию error  ( ). Последняя использует стандартную библиотечную функцию printf для вывода сообщения о синтаксической ошибке и прекращает работу программы вызовом другой стандартной библиотечной функции Сexit (1). 

#include <ctype.h> /* Файл с предикатом isdigit */

int lookahead;

main ( )

{

lookahead = getchar ( ) ;

expr ( ) ;

putchar ( ‘\ n’ ) ;  /* Символ перехода на новую строку */

}

expr ( )

{

term ( ) ;

while (1)

if  (lookahead = = ‘+’)  {

match ( ‘+’ ) ; term ( ) ; putchar ( ‘+’ );

}

else if (lookahead = = ‘-’ )  {

match (‘-’); term ( ); putchar (‘-’);

}

else break;

}

term ( )

{

if  (isdigit (lookahead) )  {

putchar (lookahead);

match (lookahead);

}

else error ( );

}

match (t)

int t;

{

if  (lookahead = = t)

lookahead = getchar ( );

else error ( );

}

error ( )

{

printf (“Syntax error\n”);  /* Сообщение об ошибке */

exit (1);  /* Прекращение выполнения программы */

}

Рис. 2.24. Программа на языке С для трансляции инфиксных выражений в постфиксные


2.6. Лексический анализ

Теперь к транслятору из предыдущего раздела добавим лексический анализатор, который считывает входную строку и превращает ее в поток токенов для последующего разбора анализатором. Вспомним из определения грамматики в разделе 2.2, что предложения языка состоят из строк токенов. Последовательность входных символов, входящих в состав единичного токена, называется лексемой. Лексический анализатор «ограждает» синтаксический анализатор от непосредственной работы с лексемами, представляющими токены. Рассмотрение лексического анализатора начнем с перечисления некоторых выполняемых им функций.

Удаление пробелов и комментариев

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

Если «пустые символы» будут удалены лексическим анализатором, синтаксический анализатор никогда не столкнется с ними. Альтернативный способ, состоящий из модификации грамматики для включения «пустых символов» в синтаксис, достаточно сложен для реализации.

Константы

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

Пустьnum токен, представляющий целое число. Когда во входном потоке встречается последовательность цифр, лексический анализатор передает синтаксическому анализатору токен num.Логически лексический анализатор передает синтаксическому анализатору как токен, так и его атрибут. Если записать токен и его атрибут как кортеж, заключенный в угловые скобки <>, то входная строка

31 + 28 + 59

трансформируется в последовательность кортежей

<num, 31> <+, > <num, 28> <+, > <num, 59>

Токен + атрибутов не имеет. Вторые компоненты кортежей, представляющие атрибуты токенов, не играют роли в процессе разбора, но требуются на этапе трансляции.

Распознавание идентификаторов и ключевых слов

Языки используют идентификаторы в качестве имен переменных, массивов, функций и т.п. Грамматика языка часто рассматривает идентификатор как токен. Синтаксический анализатор, основанный на такой грамматике, должен получать один и тот же токен (скажем, id) всякий раз, когда во входном потоке встречается идентификатор. Так, вход

count  = count  + increment;          (2.15)

должен конвертироваться лексическим анализатором в поток токенов

id = id + id                                    (2.16)

который будет разбираться синтаксическим анализатором.

Говоря о лексическом анализе строки типа (2.15), следует четко понимать различие между токеном id и лексемами count иincrement, связанными с экземплярами этого токена. Транслятор должен знать, что первые два токена id (2.16) образованы лексемой  count, а последний токен id – лексемой increment.

Когда лексема, образующая идентификатор, поступает на вход, требуется некоторый механизм определения того, не появлялась ли эта лексема ранее. Как упоминалось в главе 1, «Введение в компиляцию», в качестве такого механизма может использоваться таблица символов. Лексемы хранятся в таблице символов, а указатель на соответствующую запись таблицы становится атрибутом токена id.

Многие языки используют определенные заранее строки символов, такие как begin, end,if и т.п., в качестве символов пунктуации или для указания конкретных конструкций. Такие строки символов, именуемые ключевыми словами (keyword), обычно удовлетворяют правилам образования идентификаторов, а потому требуется дополнительный механизм, позволяющий отличать ключевые слова от прочих идентификаторов. Проблема упрощается, если ключевые слова зарезервированы, т.е. они не могут использоваться как идентификаторы. В таком случае строка символов формирует идентификатор, только если она является ключевым словом.

Проблема разделения токенов возникает и в том случае, когда одни и те же символы встречаются в лексемах нескольких токенов, как например, <, <= и <> Pascal. Технологии эффективного распознавания таких токенов обсуждаются в главе 3, «Лексический анализ».

Интерфейс к лексическому анализатору

Если лексический анализатор находится между синтаксическим анализатором и входящим потоком, он взаимодействует с ними, как показано на рис. 2.25. Анализатор считывает символы из входного потока, группирует их в лексемы и передает токены, образуемые этими лексемами, вместе с их атрибутами последующим стадиям компиляции. В некоторых ситуациях лексический анализатор считывает несколько следующих символов, прежде чем принять решение, такой токен должен быть передан синтаксическому анализатору. Например, лексический анализатор Pascal должен причитать символ, следующий после >. Если следующий символ – =, то формирующая токен лексема (>=) означает оператор «больше или равно». В противном случае лексема > соответствует оператору «больше». При этом лексический анализатор прочитал один лишний символ из входного потока. Этот символ следует вернуть во входной поток, поскольку он может оказаться началом следующей лексемы.

Рис. 2.25. Лексический анализатор между входным потоком и синтаксическим анализатором

Лексический и синтаксический анализаторы образуют пару производитель-потребитель (producer-customer). Лексический анализатор приводит токены,потребляемые синтаксическим анализатором. До использования токены могут храниться в буфере. Взаимодействие между двумя анализаторами ограничивается только размером буфера: лексический анализатор не может продолжить работу, когда буфер заполнен, а синтаксический анализатор – когда буфер пуст. Обычно в буфере хранится только один токен. В этом случае взаимодействие реализуется с помощью разработки лексического анализатора в виде процедуры, вызываемой синтаксическим анализатором для получения очередного токена.

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

Лексический анализатор

Теперь приступим к созданию простейшего лексического анализатора для транслятора выражений из раздела 2.5. Цель лексич5еского анализатора состоит в том, чтобы разрешить в выражениях использование пробелов и чисел. В следующем разделе мы продолжим работу над данным анализатором с тем, чтобы допустить в выражениях применение идентификаторов.

Рис. 2.26. Реализация взаимодействия, показанного на рис. 2.25

На рис. 2.26 показано, каким образом лексический анализатор, используемый в виде функции lexan( ) на языке С, реализует показанные на рис. 2.25 взаимодействия с входным потоком и синтаксическим анализатором. Работу с входным буфером обеспечивают функции getchar и ungetc из стандартного включаемого файла <stdio.h>. Функция lexan считывает символы и возвращает их во входной поток посредством вызовов функций getchar и ungetc. Если переменная c объявлена как символ (char), то пара инструкций

c = getchar ( ); undetc (c, stdin);

оставляет входной поток в исходном состоянии. Вызов getchar присваивает следующий входной символ переменной с, а вызов ungetc возвращает c в стандартный входной поток stdin.

Если язык реализации лексического анализатора не позволяет возврат из функции структур данных, то токены и их атрибуты должны передаваться раздельно. Функция lexan возвращает целое число, представляющее код токена. Токен символа может быть обычным целым числом, представляющим этот символ. Другие токены, такие как num, должны иметь значения, большие целого значения любого символа, например 256. Чтобы упростить изменение кодов токенов, для указания токена num воспользуемся символьной константой NUM. В Pascal связь NUM и кода осуществляется с помощью объявления const; в C – с использованием инструкции

#define NUM 256

Функция lexan возвращает NUM в том случае, если Вов входном потоке встречается последовательность цифр. Глобальная переменная tokenval устанавливается равной числовому значению последовательности цифр. Таким образом, если во входном потоке непосредственно за символом 7 следует символ 6, tokenval получит значение 76.

Для использования чисел в выражениях нужно внести соответствующие изменения в грамматику (рис. 2.19). Необходимо заменить отдельные цифры нетерминалом factor и добавить следующие продукции и семантические действия:

factor          (expr)

|        num {print (num.value)}

Соответствующий код на языке С (рис. 2.27) представляет собой непосредственную реализацию приведенных продукций. Когда lookahead равно NUM, значение атрибута num.value дается глобальной переменной tokenval. Выполнение семантического действия осуществляется стандартной библиотечной функцией printf. Первый аргумент printf – строка в двоичных кавычках, определяющая используемый при выводе остальных аргументов формат. Так, %d в строке обеспечивает десятичный вывод следующего аргумента, и в результате приведенный код выводит пробел, за которым следует десятичное значение числа и еще один пробел.

 

factor ( )

{

if ( lookhead = = ‘(‘ )        {

match ( ‘(‘ ); expr( ); match ( ‘)’ );

}

else if (lookhead = = NUM)          {

printf (“ %d ”, tokenval); match (NUM);

}

else error ( );

}

Рис. 2.27. Код на языке С для немерминала factor

Реализация функции lexan приведена на рис. 2.28. При каждом выполнении тела инструкции while (строки 8-28) в строке 9 присходит считывание нового символа в переменную t. Если этот символ – пробел или символ табуляции (обозначаемый в С как ‘\t’), производится повторное выполнение цикла. Если считывается символ перехода на новую строку, происходит увеличение глобальной переменной lineno на единицу для отслеживания номера текущей строки входного потока (это поможет отследить место возникновения ошибки), но токен не возвращается.

(1)                   #include <studio.h>

(2)                   #include <ctype.h>

(3)                   int lineno = 1;

(4)                   int tokenval = NONE;

(5)                   int lexan ( )

(6)                   {

(7)                                      int t;

(8)                                      while (1) {

(9)                                                  t = getchar ( );

(10)                                              if (t  = = ‘ ‘  | |  t  = = ‘\t’)

(11)                                                          ; /* Удаление пробелов и табуляции */

(12)                                              else if (t  = = ‘\n’)

(13)                                                          lineno ++;

(14)                                              else if (isdigit(t))        {

(15)                                                          tokenval = t – ‘0’;

(16)                                                          t = getchar( );

(17)                                                          while (isdigit (t)) {

(18)                                                                      tokenval = tokenval * 10 + t – ‘0’;

(19)                                                                      t = getchar ( );

(20)                                                          }

(21)                                                          ungetc (t, stdin);

(22)                                                          return NUM;

(23)                                              }

(24)                                              else  {

(25)                                                          tokenval = NONE;

(26)                                                          return t;

(27)                                              }

(28)                                  }

(29)                }

Рис. 2.28. Код на языке С лексического анализатора, удаляющего пробелы и собирающего числа в токены

Код, считывающий последовательность символов, приведен в строках 14-23. В строках 14 и 17 для определения, является ли считанный символ t цифрой, используется предикат isdigit(t) из стандартного включаемого файла <ctype.h>. Если этот символ – цифра, ее значение определяется выражением t-‘0’, что справедливо как при использовании ASCII, так и EBCDIC. При применении других наборов символов, возможно, потребуется более сложный способ вычисления значения. В разделе 2.9 мы интегрируем построенный лексический анализатор выражений.

2.7. Использование таблиц символов

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

Интерфейс таблицы символов

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

insert (s, t)        :           Возвращает индекс новой записи для строки и s токена t.

lookup(s)   :           Возвращает индекс записи для строки или s 0, если строка не найдена.

Лексический анализатор использует операцию lookup (просмотр) для определения, имеется ли в таблице символов запись, соответствующая дано лексеме. Если такой записи нет, для ее создания применяется операция insert (вставка). Рассмотрим реализацию, при которой и лексический, и синтаксический анализаторы имеют доступ к записям  таблицы символов (и соответственно, должны уметь работать с используемым форматом таблицы).

Обработка зарезервированных ключевых слов

Приведенные выше программы могут работать с любым набором зарезервированных ключевых слов. Например, рассмотрим токены div и mod соответственно. Таблицу символов можно инициализировать вызовами

insert (“div”, div);

insert (“mod”, mod);

Любой последующий вызов lookup(“div”) вернет токен div, а потому div не может быть использован в качестве идентификатора.

Таким образом, с помощью соответствующей инициализации таблицы символов можно работать с любым набором зарезервированных ключей слов.

Реализация таблицы символов

Образец структуры данных для реализации таблицы символов приведен на рис. 2.29. Для хранения лексем, образующих идентификаторы, не стоит отводить память фиксированного размера – этой паряти может оказаться недостаточно для очень длинного идентификатора и слишком много для коротких идентификаторов типа i, что влечет за собой нерациональное использование памяти. На рис. 2.29 строки символов, образующие лексемы, хранятся в специальном массиве lexemes. Строки завершаются символом конца строки (end-of-string), обозначенным как EOS, который не может встречаться в идентификаторе. Каждая запись в массиве таблицы символов symtable представляет собой запись, состоящую из двух полей – lexptr,указывающего на начало лексемы, и token. Для хранения атрибутов могут использоваться и дополнительные поля.

На рис. 2.29 нулевая запись пуста, поскольку для указания, что для данной строки в таблице символов не имеется записи, функция lookup возвращает 0. Первая и вторая записи используются для зарезервированных ключевых слов div и mod. В третьей и четвертой записях хранятся указатели еа идентификаторы count и i.

Рис. 2.29. Таблица символов и массив для хранения строк

Псевдокод лексического анализатора приведен на рис. 2.30, а его реализация на языке С представлена в разделе 2.9. Проблемы и целые константы обрабатываются этим лексическим анализатором так же, как и на рис. 2.28.

function lexan: integer;

var lexbuf: array [0..100] of char;

c:         char;

begin

loop begin

Прочесть символ в с

if c – пробел или табулятор then

ничего не делать

else if c – символ новой строки then

lineno := lineno + 1

else if c – цифра then begin

Установить tokenval равным значению этой и последующих цифр

return NUM

end

else if c – буква then begin

Поместить с и последующие символы и цифры в lexbuf

p := lookup (lexbuf);

if p = 0  then

p := insert (lexbuf, ID);

tokenval := p;

return Поле tokenval записи p таблицы

end

else begin  /*Токен – отдельный символ */

Установить tokenval равным NONE  /* Нет атрибутов */

return  Целое, представляющее код символа с

end

end

end

Рис. 2.30. Псевдокод лексического анализатора

При считывании буквы лексический анализатор начинает записывать буквы и цифры в буфер lexbuf. Затем сохраненная в буфере строка ищется в таблице символов с помощью операции lookup. Поскольку таблица символов изначально инициализирована записями для ключевых слов div иmod, как показано на рис. 2.29, их можно найти, если lexbuf содержит обе эти лексемы. Если в таблице символов их можно найти, если lexbuf содержит обе эти лексемы. Если в таблице символов нет записи, соответствующей строке в lexbuf (т.е. функция lookup вернет значение 0), значит, lexbuf содержит лексему нового идентификатора. Запись для нового идентификатора создается с помощью функции  insert. После вставки новой записи в таблицу символов переменная p содержит индекс записи в таблице для строки в lexbuf. Этот индекс передается синтаксическому анализатору путем присвоения переменной tokenval; функция при этом возвращает токен, хранящийся в поле token записи в таблице символов.

Действие по умолчанию состоит в возврате целого значения, являющегося кодом считанного символа, в качестве очередного токена. Поскольку токены, представляющие отдельные символы, не имеют атрибутов, переменной tokenval присваивается значение NONE.

2.8. Абстрактная стековая машина

Начальная стадия компилятора строит промежуточное представление исходной программы, из которого на заключительной стадии генерируется целевая программа. Один из популярных видов промежуточного представления – код для абстрактной стековой машины. Как упоминалось в разделе 1.5, разделение процесса компиляции на начальную и заключительную стадии упрощает адаптацию компилятора для работы на новой машине.

В этом разделе рассматривается абстрактная стековая машина и показано, как можно сгенерировать код для нее. Машина имеет раздельную память для инструкций и данных. Все арифметические выражения вычисляются над значениями в стеке. Инструкции такой машины существенно ограничены и разделяются на три класса: целой арифметики, работы со стеком и управления исполнением. Данная машина представлена на рис. 2.31. Указатель pc определяет инструкцию, которая должна выполняться в настоящий момент.

Рис. 2.31. Снимок стековой машины после выполнения первых четырех инструкций

Арифметические инструкции

Абстрактная стековая машина должна выполнять все операции промежуточного языка. Базовые операции, такие как сложение или вычитание, поддерживаются абстрактной машиной непосредственно. Более сложные операции могут быть реализованы как последовательность инструкций абстрактной стековой машины. Можно упростить описание машины, полагая, что для каждого арифметического оператора есть своя инструкция.

Код абстрактной машины для арифметических выражений имитирует вычисление постфиксного представления выражения с использованием стека. Вычисления производятся путем обработки постфиксного представления слева направо, при этом каждый встречающийся операнд помещается в стек. Если встречается k-арный оператор, его крайний слева аргумент находится на k-1 позицию ниже вершины стека, а его крайний справа аргумент – на вершине стека. При вычислении используются k верхних значений, которые при этом удаляются из стека, и результат помещается в стек. Например, при вычислении постфиксного выражения 1 3 + 5 * выполняются следующие действия.

1.                 В стек помещается 1.

2.                 В стек помещается 3.

3.                 Суммируются два верхних элемента стека (при этом они удаляются из стека), и в стек заносится результат сложения – 4.

4.                 В стек помещается 5.

5.                 Умножаются два верхних элемента стека (при этом они удаляются из стека), и в стек заносится результат умножения – 20.

По окончании вычислений значение на вершине стека (в данном случае равное 20) представляет собой результат вычисления всего выражения.

В данном промежуточном языке все значения являются целыми; false соответствует нулевое значение, а true – ненулевое целое. Логические операторы and и or требуют вычисления обоих своих аргументов.

l-значения и r-значения

Идентификаторы слева и справа в операторе присваивания имеют два разных смысла. В каждом из присваиваний

i := 5;

i := i+1;

правая сторона определяет целое значение, в то время как левая – адрес памяти, где это значение будет храниться. Точно так же и в случае с инструкцией (если p и q – указатели на символы)

p↑ := q↑;

ее правая части q↑ указывает символ, в то время как левая часть p↑ - место в памяти, куда следует поместить этот символ. Термины l-значение и r-значение (l-value и r-value)определяют значение, которые могут использоваться в левой и правой частях инструкции присвоения соответственно. Таким образом, r-значение – это то, что обычно подразумевается под словом «значение», в то время как l-значение – это адрес памяти.

Работа со стеком

Кроме очевидных инструкций для помещения целой константы в стек и удаления значения с вершины стека, имеются следующие инструкции для обращения к данным.

push v

Поместить v в стек.

rvalue l

Поместить в стек содержимое по адресу l.

lvalue l

Поместить в стек адрес ячейки памяти l.

pop

Удалить значение с вершины стека.

:=

r-значение на вершине стека размещается по адресу, представленному l-значением, следующим за ним в стеке; обе величины после этого удаляются из стека.

copy

Поместить копию значения на вершине стека в стек.

Трансляция выражений

Код для вычисления выражения в стековой машине тесно связан с постфиксной записью этого выражения. Постфиксная форма выражения E+F по определению представляет собой конкатенацию постфиксной записи E, постфиксной записи F и +. Точно так же код стековой машины для вычисления E+F является конкатенацией кода для вычисления E, кода для вычисления F и инструкции, суммирующей полученные значения. Следовательно, транслящию выражений в код стековой машины можно выполнить путем адаптации транслятора из разделов 2.6 и 2.7.

Сгенерируем теперь стековый код для выражений, в которых ячейки данных адресуются символически (выделение памяти для идентификаторов обсуждается в главе 7, «Среды времени исполнения»). Выражение a+b транслируется в

rvalue a

rvalue b

+

Другими словами, помещаем содержимое ячеек памяти a и b в стек, затем снимаем эти значения из стека, суммируем, и результат заносим в стек.

Трансляция присвоений в стековой машине выполняется следующий образом. l-значение идентификатора, которому будет присвоено значение, помещается в стек, затем вычисляется выражение, и его r-значение присваивается идентификатору. Например, присвоение

day := (1461*y)div 4 + (153*m + 2) div 5 + d                     (2.17)

транслируется в код, приведенный на рис. 2.32.

lvalue day

push 2

push 1461

+

rvalue y

push 5

*

div

push 4

+

div

rvalue d

push 153

+

rvalue m

:=

*

 

Рис. 2.32. Трансляция day :=(1461*y) div 4 + (153*m + 2) div 5 + d)

Все эти значения можно формализовать следующим образом. Каждый нетерминал имеет атрибут t, задающий его трансляцию. Атрибут lexeme токена id дает строку, представляющую индетификатор

stmtid:=expr{stmt.t:=’lvalue’||id.lexeme||expr.t||’:=’}

Управление выполнением

Стековая машина выполняет инструкции последовательно, если иное не предписано инструкциями условного или безусловного перехода. Для определения целевого адреса перехода имеется ряд опций.

1.                 Операнд инструкций дает целевой адрес.

2.                 Операнд инструкции определяет относительную дистанцию перехода (положительную или отрицательную).

3.                 Целевой адрес указывается символически (т.е. машина поддерживает метки).

При работе с первыми двумя опциями имеется дополнительная возможность получения операнда с вершины стека.

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

label l

Указание цели переходов к l; никаких других действий не выполняет.

goto l

Следующая выполняемая инструкция расположена по адресу l.

gofalse l

Снять значение с вершины стека и осуществить переход, если оно нулевое

gotrue l

Снять значение с вершины стека и осуществить переход, если оно ненулевое

halt

Прекратить выполнение.

Трансляция инструкции

На рис. 2.33 схематически показан код абстрактной машины для условного перехода и для инструкции while. Дальнейшее обсуждение вопроса посвящено созданию меток.

Рассмотрим код для инструкции if (рис. 2.33). При трансляции исходной программы может быть только одна инструкция label out, в противном случае возникает конфликт при выполнении инструкции goto out. Следовательно, требуется механизм, обеспечивающий согласованную замену out уникальной меткой при трансляции инструкции if.

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

stmt→if expr then stmt1          {out     :=         newlabel;

stmt.t  :=         expr.t||

‘gofalse’ out||

stmt1.t||

‘label’ out}

 

Рис. 2.33. Схема кода условного перехода и инструкции while

Вывод результатов трансляции

Трансляторы выражений из раздела 2.5 для инкрементальной генерации трансляции выражений использовали оператор печати. Схожие операторы могут применяться и при трансляции инструкций. Вместе операции печати используем процедуру emit для скрытия деталей вывода. Например, используя процедуру emit, вместо (2.18) можем записать

stmt  if

expr     { out := newlabel;emit(‘gofalse’,out); }

then

stmt1    { emit(‘label’,out); }

Когда в продукции встречаются семантические действия, элементы е правой части рассматриваются слева направо. В приведенной выше продукции вначале выполняются действия, соответствующие анализу expr; затем out присваивается значение, возвращаемое функцией newlabel; в код вносится инструкция gofalse; осуществляются действия, соответствующие анализу stmt1; и, наконец, в код вносится инструкция label. Поскольку в процессе анализа expr и stmt1 создается необходимый код для этих нетерминалов, описанные продукции реализуют код, приведенный на рис. 2.33.

procedure stmt;

var test, out: integer;              /* Для меток */

begin

if lookahead = id then begin

emit (‘lvakue’, tokenval); match (id); match (‘:=’); expr

end

else if lookahead = ‘if’ then begin

match (‘if’);

expr;

out := newlable;

emit (‘gofalse’, out);

match (‘then’);

stmt;

emit (‘label’, out);

end

/* Код для трансляции других инструкций */

else error

end

Рис. 2.34. Псевдокод для трансляции инструкций

Псевдокод для трансляции присвоений и условных инструкций показан на рис. 2.34. Поскольку переменная out локальна для процедуры stmt, ее значение не влияет на вызовы процедур expr и stmt. Генерация меток требует определенных усилий. Предположим, что при трансляции метки имеют вид L1, L2 и т.д. Псевдокод, работающий с такими метками, использует целое число, следующее за L. В результате переменная out объявлена как целое число, функция newlabel возвращает целую величину, которая становится значением переменной out, и emit выводит метку, заданную целым числом.

Макет кода для инструкции while (рис. 2.33) можно перевести в псевдокод подобным образом. Трансляция последовательности инструкций представляет собой простую конкатенацию инструкций этой последовательности и предлагается читателю в качестве небольшого упражнения.

Трансляция большинства конструкций с одним входом (single-entry) и выходом (single-exit) схожа с трансляцией инструкции while. Проиллюстрируем это на примере управления потоком выполнения в выражениях.

Пример 2.10

Лексический анализатор в разделе 2.7 содержит условный оператор типа

if t = blank or t = tab then...

Если t является пробелом, то совершенно очевидно, что не нужно проверять, является ли t символом табуляции, поскольку с учетом первого равенства все выражения в целом истинно. Выражение

expr1 or expr2

может быть реализовано как

if expr1 then true else expr2

Читатель может убедиться, что следующий код реализует оператор or:

Код для expr1

copy                /* Копирования значения expr1 */

gotrue out

pop                  /* Снятие со стека значения expr1 */

Код для expr2

label out

Вспомним, инструкции gotrue и gofalse удаляют значения с вершины стека, чтобы упростить генерацию кода для инструкции if и while. Копируя значение expr1, можно гарантировать, что значение на вершине стека остается равным true при переходе посредством инструкции gotrue.

2.9. Сборка транслятора

В этой главе было рассмотрено множество синтаксически управляемых технологий для построения начальной стадии компилятора. В данном разделе мы объединим все рассмотренные технологии в программе на языке С, которая служит транслятором инфиксной записи в постфиксную для языка, состоящего из последовательности выражений, разделенных точками с запятой. Выражения состоят из чисел, идентификаторов и операторов +, -, *,/, div иmod. Выход транслятора расширением программ, разработанных в разделах 2.5-2.7. Полный листинг программы приведен в конце раздела.

Описание транслятора

Транслятор создан с использованием схемы синтаксически управляемой трансляции, представленной на рис. 2.35. Токен id представляет непустую последовательность букв и цифр, начинающуюся с буквы, num – последовательность цифр, а eof – символ конца файла. Токены разделяются последовательностями пробелов, символов табуляций и новой строки. Атрибут lexeme токена id указывает строку, образующую токен. Атрибут value токена num содержит целое число, представляющее num.

Код транслятора разделен на семь модулей, каждый из которых хранится в отдельном файле. Выполнение начинается с модуля main.c, в котором последовательно вызываются функции init( ) – для инициализации, и parse( ) – для трансляции. Остальные шесть модулей показаны на рис. 2.36. Имеется также глобальный заголовочный файл global.h, содержащий определения, которые встречаются в нескольких модулях. Первая структура каждого модуля

#include global.h

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

start             listeof

list            expr; list

|          ε

expr             expr + term                  {print(‘+’)}

|          expr + term                 {print(‘-’)}

|          term

term             term*factor                  {print(‘*’)}

|          term/factor                  {print(‘/’)}

|          term div factor             {print(‘div’)}

|          term mod factor           {print(‘mod’)}

|          factor

factor              (expr)

|          id                                {print(‘id.lexeme’)}

|          num                            {print(‘num.value’)}

Рис. 2.35. Спецификация транслятора из инфиксной формы записи в постфиксную

Рис. 2.36 Модули транслятора из инфиксной формы в постфиксную

Модуль лексического анализа lexer.c

Лексический анализатор представляет собой функцию lexan( ), вызываемую синтаксическим анализатором для получения токена. Построенная на основе псевдокода из рис. 2.30, функция считывает по одному символу из входного потока и возвращает синтаксическому анализатору найденный токен. Значение атрибута, связанного с токеном, присваивается глобальной переменной tokenval.

Синтаксический анализатор воспринимает следующие токены.

+  - *  /  DIV  MOD  ( )  ID  NUM  DONE

Здесь ID соответствует идентификатору, NUM – числу, а DONE – концу файла. Пробелы удаляются лексическим анализатором автоматически. На рис. 2.37 показаны токены и атрибуты, производимые лексическим анализатором для различных лексем.

Лексема

Токен

Значение атрибута

Пробел

 

 

Последовательность цифр

NUM

Числовые значения последовательности

div

DIV

 

mod

MOD

 

Прочие последовательности символов, начинающиеся с буквы и состоящие из букв и цифр

ID

Индекс в таблице символов

Символ конца файла

DONE

 

Прочие символы

Этот символы

 

Рис. 2.37. Описание токенов

Лексический анализатор использует для работы с таблицей символов функцию lookup, которая определяет, имеется ли в таблице символов данная лексема, и insert, сохраняющую новую лексему в таблице символов. Кроме того, лексический анализатор увеличивает глобальную переменную linelo всякий раз, когда во входящем потоке встречается символ новой строки.

Модуль синтаксического анализатора parser.c

start            list eof

list            expr; list

|          ε

expr             term moreterms

moreterms            + term {print(‘+’)} moreterms

|          - term {print(‘-’)} moreterms

|          ε

term             factor morefactors

morefactors            * factor {print(‘*’)} morefactors

|          / factor {print(‘/’)} morefactors

|          div factor {print(‘DIV’)} morefactors

|          mod factor {print(‘MOD’)} morefactors

|          ε

factor              (expr)

|          id {print(‘id.lexeme’)}

|          num {print(‘num.value’)}

Рис.2.38. Схема синтаксически управляемой трансляции после устранения левой рекурсии

Синтаксический анализатор строится с использованием технологий, описанных в разделе 2.5. Вначале из схемы трансляции (рис. 2.35) устраняем левую рекурсию, чтобы иметь возможность проанализировать грамматику с помощью метода рекурсивного спуска. Преобразованная схема показана на рис. 2.38.

Затем создаем функции для нетерминалов expr,term и factor, как показано на рис. 2.24. Функция parse ( ) реализует стартовый символ грамматики. Чтобы получить новый токен, эта функция вызывает функцию lexan (). Для генерации выхода синтаксический анализатор использует функцию emit, а для вывода сообщения об ошибке – функцию error.

Модуль вывода emitter.c

Модуль вывода состоит из единственной функции emit(t, tval), которая генерирует выход для токена t со значением атрибута tval.

Модули работы с таблицей символов symbol.c и init.c

Модуль работы с таблицей символов symbol.c реализует структуру данных, показанную на рис. 2.29 в разделе 2.7. Записи в массиве symtable представляют собой пары, состоящие из указателя на массив lexemes и целой величины, описывающей хранимый токен. Операция insert(s, t) возвращает индекс в таблице symatable для лексемы s, образующей токен t. Функция lookup(s) возвращает индекс записи в таблице symtable для лексемы s (или 0, если такой записи нет).

Модуль init.c используется для первоначального занесения в таблицу символов зарезервированных ключевых слов. Лексемы и токены, представляющие зарезервированные ключевые слова, хранятся в массиве keywords, который имеет тот же тип, что и массив symtable. Функция init( ) проходит последовательность по всем элементам массива keywords и использует функцию insert для помещения ключевых слов в таблицу символов. Такая технология позволяет легко и просто изменить набор ключевых слов и представление их токенов.

Модуль обработки ошибок error.c

Этот модуль используется при выводе сообщения об ошибке. При возникновении ошибки транслятор просто выводит сообщение о ней и прекращает работу. Однако было бы разумнее применить метод, при котором возникшая ошибка приводила бы к пропуску оставшейся части строки до символа « и продолжению анализа. Читатель может самостоятельно внести в исходные тексты необходимые изменения. Ряд интеллектуальных технологий восстановления после ошибок представлен в главе 4, «Синтаксический анализ».

Создание компилятора

Код модулей расположен в семи файлах: lexer.c, parser.c, emmiter.s, symbol.c, init.c, error.c и main.c. Файл main.c содержит функцию main( ), которая вызывает функции init( ), parsel( ), а при успешном завершении программы – exit(0).

В операционной системе UNIX компилятор может быть создан с помощью команды

cc lexer.c parser.c emmiter.s symbol.c init.c error.c main.c

либо отдельной компиляцией файлов

cc ~c filename.c

и компоновкой полученных файлов filename.o

cc lexer.o parser.o emmiter.o symbol.o init.o error.o main.o

Команда cc создает файл a.out, содержащий транслятор. Транслятор может быть запущен вводом в командной строке a.out5, а затем – транслируемых выражений

2 + 3 * 5

12 div 5 mod 2

или любых других.

_________________________________________________

5 Обычно для запуска используется ввод./a.out Прим. ред.

Листинг

Далее приводится листинг программы на языке С, реализующий транслятор. Вначале приведен общий заголовочный файл global.h, за которым следует семь исходных файлов.

/****               global.h            **************************/

#include <stdio.h>                   /*         Загрузка программ ввода-вывода   */

#include <ctype.h>                  /*         Загрузка программ проверки символов     */

 

#define            BSIZE             128      /*         Размер буфера           */

#define            NONE            -1

#define             EOS               ‘\0’

 

#define             NUM             256

#define             DIV                257

#define             MOD             258

#define             ID                   259

#define             DONE            260

 

extern int                      tokenval;          /* Значение атрибута токена */

extern int                      lineno;

 

struct entry {                                      /*Запись в таблице символов */

char *lexptr;

int  token;

};

 

extern struct entry symtable [];             /*Таблица символов          */

 

/****               lexer               *************************/

 

#include “global.h”

char lexbuf [BSIZE];

int lineno          =1;

int tokenval      = NONE;

 

int lexan( )                                          /*         Лексический анализатор     */

{

int t;

while (1)  {

t = getchar( );

if (t  = = ‘\t’)

;                                        /* Отбрасываем разделители-пробелы */

else if (t  = =  ‘\n’)

lineno;

else if (isdigit(t))  {                   /* t – цифра */

ungetc(t, stdin);

scanf(“%d”, &tokenval);

return NUM;

}

else if (isalpha(t))  {                 /* t – цифра */

int p, b = 0;

while (isalnum(t))  {           /* t – буква или цифра */

lexbuf[b++] = t;

t = getchar( );

if (b >= BSIZE)

error (“compiler error”);

}

lexbuf[b] = EOS;

if (t != EOF)

ungetc(t, stdin);

p = lookup (lexbuf);

if (p = = 0)

p = insert(lexbuf, ID);

tokenval = p;

return symtable[p].token;

}

else if (t = = EOF)

return DONE;

else {

tokenval = NONE;

return t;

}

}

}

 

/****   parser.c          **************************/

 

#include “global.h”

 

int lookahead;

 

parse( )                        /* Разбор и трансляция списка выражений */

{

lookahead = lexan( );

while (lookahead != DONE)  {

expr( ); match (‘;’);

}

}

 

expr( )

{

int t;

term( );

while (1)

switch (lookahead)  {

case ‘+’: case ‘-’:

t = lookahead;

match (lookahead); term( ); emit(t, NONE);

continue;

default:

return;

}

}

 

factor( )

{

switch (lookahead)  {

case ‘(’:

match ( ‘(‘ ); expr( ); match ( ‘)’ ); break;

case NUM:

emit (Num, tokenval); match(NUM); break;

case ID:

emit (ID, tokenval); match (ID); break;

default:

error(“syntax error”);

}

}

 

match (int t)

{

if (lookahead = = t)

lookahead = lexan( );

else error(“syntax error”);

}

 

/****   emitter.c          **********************************/

 

#include “global.h”

 

emit(int t, int tval)         /* Генерация вывода           */

{

switch (t)  {

case ‘+’: case ‘-’: case ‘*’: case ‘/’:

printf (“%c\n”, t); break;

case DIV:

printf (“DIV\n”); break;

case MOD:

printf (“MOD\n”); break;

case NUM:

printf (“%d\n”, tval); break;

case ID;

printf (“%s\n”, symtable[tval].lexptr); break;

default:

printf (“token %d, tokenval %d\n”, t, tval);

}

}

 

/****   symbol.c         ***************************/

 

#include “global.h”

 

#define             STRMAX        999      /* Размер массива лексем */

#define             SYMMAX      100      /* Размер таблицы символов */

 

char lexemes[STRMAX];

int lastchar = -1;                                 /* Последняя использованная позиция в lexemes */

 

struct entry symtable[SYMMAX];

int lasttentry = 0;                                 /* Последняя использованная позиция в таблице символов */

 

 

int lookup (char s[])                             /* Возвращает положение в таблице символов для s */

{

int p;

for (p = lastentry; p > 0; p- - )

if (strcmp (symtable[p] . lexptr, s) = = 0)

return p;

return 0;

}

 

int insert (char s[], int tok)                   /*Возвращает положение в таблице символов для s */

 

{

int len;

len = strlen(s);        /* strlen вычисляет длину строки */

if (lastentry + 1 >= SYMMAX)

error (“symbol table full”);

if (lastchar + len + 1 >= STRMAX)

error (“lexemes array full”);

lastentry + +;

symptable [lastentry] . token = tok;

symptable [lastentry] . lexptr = &lexemes [lastchar + 1];

lastchar += len + 1;

strcpy (symptable[lastenentry] . lexptr, s);

return lastentry;

}

 

/****               init.c                 ********************************/

 

#include “global.h”

 

struct enrty keywords[] = {

“div”, DIV,

mod”, MOD,

0,               0

};

 

init( )                            /* Загрузка ключевых слов в таблицу символов */

{

struct entry *p;

for (p = keywords; p->token; p+ +)

insert (p->lexptr, p->token);

}

 

/****               main.c              ***************/

 

#include “global.h”

 

main( )

{

init( );

parse( );

exit(0);                   /* Успешное завершение работы программы */

}

 

/********************************************************/

 

Упражнения

2.1.Рассмотрим контекстно-свободную грамматику

S SS + |SS*|a

а) покажите, что этой грамматикой может быть сгенерирована строка аа+а*;

b) постройте дерево разбора для этой строки;

с) какой язык генерируется грамматикой? Обоснуйте ответ.

2.2.      Какой язык генерируется следующей грамматикой? (В каждом случае обоснуйте ответ.)

а) S → 0 S1 | 01

b) S → +SS | - SS | a

c) S → S (S) S | ε

d) S → a S b S | b S a S | ε

e) S a | S + S |SS| S * | (S)

2.3.      Какая из грамматик в упр.2.2. неоднозначна?

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

а) арифметическое выражение в постфиксной записи;

b) левоассоциативные списки  идентификаторов, разделенных запятыми;

c) правоассоциативные списки идентификаторов, разделенных запятыми;

d) арифметические выражения с целыми и идентификаторами с четырьмя бенарными операциями +, -, *, /;

е) добавьте к арифметическим операторам из п.d унарные плюс и минус.

*2.5.       Покажите, что все двоичные строки, порождаемые следующей грамматикой, имеют значение, кратное 3. (Указание. Используйте индукцию по количеству узлов в дереве разбора.)

num → 11 |1001| num 0 | num num

2.6.      Постройте контекстно-свободную грамматику для римских чисел.

2.7.      Постройте схему синтаксически управляемой трансляции, которая преобразует арифметические выражения из инфиксной записи в префиксную (оператор записывается перед своими операндами). Например, -xy представляет собой префиксную запись выражения x-y. Постройте аннотированные деревья разбора для входных строк 9-5+2 и 9-5*2.

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

2.9.      Постройте схему синтаксически управляемой трансляции для преобразования римских чисел в целые.

2.10.    Постройте схему синтаксически управляемой трансляции для преобразования римских чисел в целые.

2.11.    Постройте для грамматик a, b и c из упр.2.2 синтаксические анализаторы, работающие по методу рекурсивного спуска.

2.12.    Постройте синтаксически управляемый транслятор, который проверяет сбалансированность скобок во входной строке.

2.13.    Следующие правила определяют перевод английских слов на «поросячью латынь»6:

а) если слово начинается с непустой строки согласных, переместите начальную строкe согласных в конец слова и добавьте суффикс AY (pig становится igpay);

b) если слово начинается с гласной, добавьте суффикс YAY (owl становится owlyay);

c) U, следующее за Q, считается согласной;

d) Y в начале слова считается гласной, если за ней не следует гласная;

e) слово из одной буквы не изменяется.

Постройте схему синтаксически управляемой трансляции для «поросячьей латыни».

2.14.       В языке программирования С инструкция for имеет следующий вид;

for(expr1; expr2; expr3)stmt

Первое выражение выполняется до цикла; обычно оно используется для инициализации индекса цикла. Второе выражение представляет собой тест, выполняемый перед каждой итерацией цикла. Когда это выражение принимает значение 0, происходит выход из цикла (цикл состоит из инструкции {stmt expr3;}). Третье выражение выполняется в конце каждой и обычно используется для увеличения индекса цикла. Инструкция for подобна

expr1; while (expr2) {stmt expr3;}

Постройте схему синтаксически управляемой трансляции для преобразования инструкции for языка С в код стековой машины.

*2.15.     Рассмотрим следующую инструкцию for.

for i := 1 step 10–j until 10*j od j := j+1

Эта инструкция может иметь три определения семантики. Во-первых, вычисление предела 10*j и инкремента 10-j может осуществляться однократно, до работы цикла, как в PL/I. Например, если до выполнения цикла j=5, цикл будет выполнен десять раз. Во-первых, значение предела и инкремент могут вычисляться при каждом прохождении цикла. В этом случае, если перед входом в цикл j=5, цикл станет бесконечным. В-третьих, возможен смысл, как в языке Algol, когда при отрицательном инкременте проверка условия выхода из цикла становится i<10*j, а не i>10*j. Для каждой из трех семантических определений постройте свою схему синтаксически управляемой трансляции для преобразования приведенного цикла в код стековой машины.

2.16.    Рассмотрим следующий фрагмент грамматики для инструкций if-then и if-then-else:

stmt          if expr then stmt

|        if expr then stmt else stmt

|        other

где other соответствует прочим инструкциям языка.

Выполните следующее:

а) покажите, что эта грамматика неоднозначна;

b) постройте эквивалентную однозначную грамматику, в которой каждый else связан с тем ближайшим предшествующим then, с которым еще не связан записанный выше другой else;

с) постройте основанную на этой грамматике схему синтаксически управляемой трансляции для преобразования условных инструкций в код стековой машины.

*2.17.     Постройте схему синтаксически управляемой трансляции, которая переводит арифметические выражения в инфиксном виде в инфиксную запись без излишних скобок. Приведите аннотированное дерево разбора для входной строки (((1+2)*(3+4))+5).

__________________________________________

6 Из англо-русского словаря: pig Latin детск. жарг. «поросячья латынь» (манера коверкать слова, переставляя первый звук в конец слова и добавляя слог ау, например Oodgay orningmay = Good morning). – Прим. перев.

Программные упражнения

Р2.1.    На основе схемы синтаксически управляемой трансляции из упр.2.9 реализуйте транслятор для перевода целых чисел в римские.

Р2.2.    Модифицируйте транслятор из раздела 2.9 для получения кода абстрактной стековой машины из раздела 2.8.

Р2.3.    Модифицируйте модуль обработки ошибок из раздела 2.9, чтобы при ошибке он пропускал неверное выражение и переходил к следующему.

Р2.4.    Расширьте транслятор из раздела 2.9 на обработку всех выражений языка Pascal.

Р2.5.    Дополните компилятор из раздела 2.9 для трансляции в код стековой машины инструкций, порождаемых следующей грамматикой:

stmt             id := expr

|          if expr then stmt

|          while expr do stmt

|          begin opt_stmts end

opt_stmts              stmt_list | ε

stmt_list             stmt_list ; stmt | stmt

 

*P2.6     Создайте набор тестовых выражений для компилятор из раздела 2.9, таких, чтобы каждая продукция использовалась в наборе по крайней мере один раз. Создайте тестовую программу, используемую в качестве тестирующего инструмента, и воспользуйтесь ею для запуска компилятора с этими выражениями.

Р2.7.    Создайте набор тестовых инструкций для компилятора из упр.Р2.5, таких, чтобы каждая продукция использовалась, по меньшей мере один раз, для генерации некоторой тестовой инструкции. Для запуска компилятора с этими тестовыми выражениями воспользуйтесь программой, разработанной в упр.Р2.6.