Язык внутреннего представления программы

Глава 5. Генерация внутреннего представления программ

Задачи

1. Написать на языке Си анализатор, действующий методом рекурсивного спуска, для грамматики:

a) S ® E^

E ® () | (E {, E}) | A

A ® a | b

b) S ® P := E | if E then S | if E then S else S

P ® I | I (e)

E ® T {+T}

T ® F {*F}

F ® P | (E)

I ® a | b

c) S ® type I = T {; I = T} ^

T ® int | record I: T {; I: T} end

I ® a | b | c

d) S ® P = E | while E do S

P ® I | I (E {, E})

E ® E + T | T

T ® T * F | F

F ® P | (E)

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

a) S ® E^ b) S ® E^

E ® E+T | E-T | T E ® E+T | E-T | T

T ® T*P | P T ® T*F | T/F | F

P ® (E) | I F ® I | I^N | (E)

I ® a | b | c I ® a | b | c | d

N ® 2 | 3 | 4

c) F ® function I(I) S; I:=E end d) S ® P := E | while E do S

S ® ; I:=E S | e P ® I | I (E {, E})

E ® E*I | E+I | I E ® E + T | T

T ® T * F | F

F ® P | (E)

3. Восстановить КС-грамматику по функциям, реализующим синтаксический анализ методом рекурсивного спуска. Какой язык она порождает?

#include <stdio.h>

int c; FILE *fp;

void A();

void ERROR();

void S (void)

{if (c == 'a')

{c = fgetc(fp); S();

if (c == 'b') c = fgetc(fp);

else ERROR();

else A();

}

void A (void)

{if (c == 'b') c = fgetc(fp);

else ERROR();

while (c == 'b')

c = fgetc(fp);

}

void main()

{fp = fopen("data", "r");

c = fgetc(fp);

S();

printf("O.K.!");

}

4. Какой язык порождает заданная грамматика? Провести анализ цепочки (a,(b,a),(a,(b)),b)^.

S ® <k = 0> E ^

E ® A | (<k=k+1; if (k == 3) ERROR();> E {,E}) <k = k-1>

A ® a | b

5. Есть грамматика, описывающая цепочки в алфавите {0, 1, 2, ^}:

S ® A^

A ® 0A | 1A | 2A | e

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

6. Дана грамматика, описывающая цепочки в алфавите {a, b, c, ^}:

S ® A^

A ® aA | bA | cA | e

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

- в цепочку должно входить не менее трех букв с;

- если встречаются подряд две буквы а, то за ними обязательно должна идти буква b.

7. Есть грамматика, описывающая цепочки в алфавите {0, 1}:

S ® 0S | 1S | e

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

8. Написать КС-грамматику с действиями для порождения
L = {a^m bⁿ c^k | m+k = n либо m-k = n}.

9. Написать КС-грамматику с действиями для порождения
L = {1ⁿ 0^m 1^p | n+p > m, m ³ 0}.

10. Дана грамматика с семантическими действиями:

S ® < A = 0; B = 0 > L {L} < if (A > 5) ERROR() > ^

L ® a < A = A+1 >| b < B = B+1; if (B > 2) ERROR() >|

c < if (B == 1) ERROR() >

Какой язык описывает эта грамматика ?

11. Дана грамматика:

S ® E^

E ® () | (E {, E}) | A

A ® a | b

Вставить в заданную грамматику действия, контролирующие соблюдение следующих условий:

- уровень вложенности скобок не больше четырех;

- на каждом уровне вложенности происходит чередование скобочных и бесскобочных элементов.

12. Пусть в языке L есть переменные и константы целого, вещественного и логического типов, а также есть оператор цикла

S ® for I = E step E to E do S

Включить в это правило вывода действия, проверяющие выполнение следующих ограничений:

- тип I и всех вхождений Е должен быть одинаковым;

- переменная логического типа недопустима в качестве параметра цикла.

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

13. Дана грамматика

P ® program D; begin S {; S} end

D ® var D' {; D'}

D'® I {, I}: record I: R {; I: R} end | I {, I} : R

R ® int | bool

S ® I := E | I.I := E

E ® T {+T}

T ® F {*F}

F ® I | (E) | I.I | N | L ,

где I - идентификатор, N - целая константа, L - логическая константа.

Вставить в заданную грамматику действия, контролирующие соблюдение следующих условий:

- все переменные, используемые в выражениях и операторах присваивания, должны быть описаны и только один раз;

- тип левой части оператора присваивания должен совпадать с типом его правой части.

Замечания:

- все записи считаются переменными различных типов (даже если они имеют одинаковую структуру);

- допускается присваивание записей.

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

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

Основные свойства языка внутреннего представления программ:

- он позволяет фиксировать синтаксическую структуру исходной программы;

- текст на нем можно автоматически генерировать во время синтаксического анализа;

- его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться.

Некоторые общепринятые способы внутреннего представления программ:

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

- префиксная запись;

- многоадресный код с явно именуемыми результатами;

- многоадресный код с неявно именуемыми результатами;

- связные списочные структуры, представляющие синтаксическое дерево.

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

Обычно синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A ® B, где A, B Î VN.

Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее часто называют ПОЛИЗ - польская инверсная запись).

В ПОЛИЗе операнды выписаны слева направо в порядке их использования. Знаки операций стоят таким образом, что знаку операции непосредственно предшествуют ее операнды.

Например, обычной (инфиксной) записи выражения a*(b+c)-(d-e)/f

соответствует такая постфиксная запись: abc+*de-f/-.

Обратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфиксной записи, учтено старшинство операций, а скобки исчезли.

Более формально постфиксную запись выражений можно определить таким образом:

1) если Е является единственным операндом, то ПОЛИЗ выражения Е - это этот операнд;

2) ПОЛИЗом выражения Е₁ q Е₂, где q - знак бинарной операции,
Е₁ и Е₂ операнды для q, является запись E₁’ E₂’ q , где E₁’ и E₂’ - ПОЛИЗ выражений Е₁ и Е₂ соответственно;

3) ПОЛИЗом выражения q E, где q- знак унарной операции, а Е - операнд q, является запись E’ q, где E’ - ПОЛИЗ выражения Е;

4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.

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

(1) если очередной элемент ПОЛИЗа - это операнд, то его значение заносится в стек;

(2) если очередной элемент ПОЛИЗа - это операция, то на "верхушке" стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;

(3) когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент - это значение всего выражения.

Следует отметить, что для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация об операндах, хранящаяся в таблицах.

Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак "-" в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции "-" возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами:

1) заменить унарную операцию бинарной, то есть считать, что "-а" означает "0-а";

2) либо ввести специальный знак для обозначения унарной операции; например, "-а" заменить на "&a" (это изменение касается только внутреннего представления программы и не требует изменения входного языка).

Теперь необходимо разработать ПОЛИЗ для операторов входного языка.

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