сист пр об ч 3 (Лекции по СПО)

6.1.2. ЗАДАЧА № 2—РАСПОЗНАВАНИЕ СИНТАКСИЧЕСКИХ ЕДИНИЦ И ИНТЕРПРЕТАЦИЯ ИХ ЗНАЧЕНИЙ

После того как программа была разбита на лексические еди­ницы или стандартные символы, компилятор должен:

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

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

Базовые синтаксические Лексические единицы
конструкции

wcm : procedure ( RATE , START ,

Оператор процедуры

FINISH ) ;

DECLARE ( COST , RATE , START , FINISH ) FIXED

BINARY ( 31 ) STATIC ;

BINARY ( 31 ) STATIC ;

Оператор декларации

COST = RATE * ( START - FINISH ) + 2 * RATE *

( START - FINISH - 100 ) ;

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

RETURN ( COST ) ;

Оператор возврата

END ;

Оператор END

Рис. 8.4. Синтаксический анализ — разбиение программы на синтаксические

единицы.

ций в исходной программе. Этот процесс известен как синтакси­ческий анализ. В нашем примере в качестве фраз мы произволь­но взяли операторы языка. Вся программа просматривается и разделяется на фразы, как показано на рис. 8.4.

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

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

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

‘ ARIFMETICSTM’».

8.1.3. ПРОМЕЖУТОЧНАЯ ФОРМА

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

1. Облегчает оптимизацию объектного кода.

2. Позволяет логически отделить машинно-независимые фазы (лексический анализ, синтаксический анализ и интерпре­тацию) от машинно-зависимых фаз (генерация кода и сборка).

При использовании промежуточной формы возникают два вопроса: (1) какова должна быть эта форма и (2) каковы пра­вила преобразования исходной программы в эту форму? Форма зависит от синтаксических конструкций: например, может быть различной для арифметических, неарифметических или неиспол-няемых операторов.

8.1.3.1. Арифметические операторы

Промежуточной формой арифметического оператора являет­ся дерево грамматического разбора. С помощью формальных методов, рассмотренных в предыдущей главе (например, общее синтаксическое дерево в упражнении 1 гл. 7), можно получить дерево грамматического разбора, изображенное на рис. 8.5. Пра­вила преобразования арифметического оператора в дерево грам­матического разбора следующие:

1. Любая переменная является терминальным узлом дерева.

1. Операции порождают (в порядке, определяемом правила­ми алгебры) двоичное дерево, в котором левая ветвь соответ­ствует первому операнду, а правая — второму операнду,

Дерево арифметического оператора нашей программы пред­ставлено на рис. 8.5.

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

В качестве промежуточной формы компилятор использует линейное представление дерева грамматического разбора в виде

матрицы. В матрице операции располагаются в порядке их ис­полнения. Каждая строка матрицы содержит операцию и два операнда.

COST = RATE * ( START - FINISH ) + 2 * RATE *

( START - FINISH - 100 ) ;

=

COST +

*

RATE -

START *

FINISH * -

2 RATE

-

START FINISH

Рис. 8.5. Дерево — промежуточная форма арифметического оператора нашей

программы.

Операнды представляются стандартными символами, обозна­-
чающими переменные, литералы или другие строки матрицы Mi
(i — номер строки матрицы). Матрица, которая генерируется для арифметического оператора, показана на рис. 8.6. (Для облегчения чтения в матрице пишутся сами символы, а не их стандартное представление.)

Номер строки матрицы	Операция	Операнд 1	Операнд 2
1	-	START	FINISH
2	*	RATE	M1
3	*	2	RATE
4	-	START	FINISH
5	-	M4	100
6	*	M3	M5
7	+	M2	M6
8	=	COST	M7

Рис 8.6. Матрица для арифметического оператора.

Дерево (рис. 8.5) и матрица (рис. 8.6) являются эквивалент­ными представлениями оператора присваивания. Читатель мо­жет построить дерево такого оператора, используя правила эле­ментарной алгебры. Процесс построения дерева или матрицы арифметического оператора рассматривается во многих книгах по компиляторам. Мы оставляем это как упражнение для чита­теля (см. упражнение 1 в гл. 7).

8.1.3.2. Неарифметические операторы

Задачаn создания промежуточной формы для неарифметиче­ских исполняемых операторов аналогична той же задаче для арифметических операторов. Операторы DO, IF, GO TO и т. д.

Исходная программа	Матрица
	Операция	Операнд 1	Операнд 2
R ETURN (COST) ;	RETURN	COST
E ND;	END

Рис. 8.7. Часть матрицы для операторов RETURN и END

.

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

8.1.3.3. Неисполняемые операторы

Неисполняемые операторы, подобные DECLARE, дают компилятору информацию о пере­менных и связанной с ними памяти. Для них не существует промежуточной формы. Информация, содержащаяся в неисполняемых операторах, переносится в таблицы для использования другими блоками компилятора. Например, с помощью оператора DECLARE нашей программы интерпретирующая фаза опреде­лит тип данных, точность и тип памяти (FIXED BINARY, 31 бит, SТАТIС) в таблице идентификаторов для каждой из перемен­ных СОSТ, RАТЕ, SТАRТ и FINISH (как показано на рис. 8.8).

В языках высокого уровня, подобных ПЛ/1, в некоторых слу­чаях распределение памяти и определение переменных откладываются до времени выполнения программы, поэтому часть таб­лиц используется также объектной программой. Так что некото­рая описательная информация передается и объектной про­грамме.

До сих пор мы рассматривали лексический анализ, синтак­сический анализ и интерпретацию (семантику). Теперь рассмотрим последние две задачи, связанные с реализацией примера программы на языке ПЛ/1.