И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции, страница 8

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

В качестве примера приведем функцию для нетерминала D (раздел описаний):

#include <string.h>

#define MAXSIZE_TID 1000

#define MAXSIZE_TD 50

char * TD[MAXSIZE_TD];

struct record

{char *name;

int declare;

char *type;

/* ... */

};

struct record TID [MAXSIZE_TID];

/* описание функций ERROR(), getlex(), id(), eq(char *),

типа struct lex и переменной curr_lex - в алгоритме

рекурсивного спуска для М-языка */

void ERROR(void);

struct lex {int class; int value;};

struct lex curr_lex;

struct lex getlex (void);

int id (void);

int eq (char *s);

void ipush (int i);

int ipop (void);

void decid (int i, char *t)

{if (TID [i].declare) ERROR();

else {TID [i].declare = 1; strcpy (TID [i].type, t);}

}

void dec (char *t)

{int i;

while ((i = ipop()) != -1) decid (i,t);}

void D (void)

{ipush (-1);

if (!id()) ERROR();

else {ipush (curr_lex.value);

curr_lex = getlex ();

while (eq (","))

{curr_lex = getlex ();

if (!id ()) ERROR ();

else {ipush (curr_lex.value);

curr_lex = getlex();}

}

if (!eq (":")) ERROR();

else {curr_lex = getlex ();

if (eq ("int")) {curr_lex = getlex ();

dec ("int");}

else if (eq ("bool"))

{curr_lex = getlex();

dec ("bool");}

else ERROR();

}

}

}

Задачи.

49. Написать для данной грамматики (предварительно преобразовав ее, если это требуется) анализатор, действующий методом рекурсивного спуска.

a) S  E b) S  P := E | if E then S | if E then S else S

E  () | (E {, E}) | A P  I | I (E)

A  a | b E  T {+T}

T  F {*F}

F  P | (E)

I  a | b

c) S  type I = T {; I = T}  d) S  P = E | while E do S

T  int | record I: T {; I: T} end P  I | I (E {, E})

I  a | b | c E  E + T | T

T  T * F | F

F  P | (E)

I  a | b | c

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

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  SaAb | Sb | bABa

S  ; I:=E S |  A  acAb | cA | 

E  E*I | E+I | I B  bB | 

*e) S  Ac | dBea *f) S  fASd | 

A  Aa | Ab | daBc A  Aa | Ab | dB | f

B  cB |  B  bcB | 

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

a) #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.!");

}

*b) #include <stdio.h>

int c; FILE *fp;

void A();

void ERROR();

void S (void)

{ A(); if ( c != '') ERROR();

}

void A (void)

{ B(); while ( c == 'a' ) {c = fgetc(fp); B();}; B();

}

void B (void)

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

}

void main()

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

c = fgetc(fp);

S();

printf("O.K.!");

}

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

53. Какой язык порождает заданная грамматика? Провести анализ цепочки (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

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

S  A

A  0A | 1A | 2A | 

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

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

S  A

A  aA | bA | cA | 

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

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

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

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

S  0S | 1S | 

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

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

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

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

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() >

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

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

S  E

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

A  a | b

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

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

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

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

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

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

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

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

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

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

*b) Дан фрагмент грамматики

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

D  ... | label L{,L} |...

S  L { , L } : S` | S`

S`  ...| goto L |...

L  I

где I -идентификатор

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

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

2. не должно быть одинаковых меток у различных операторов;

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

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

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

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 - логическая константа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. префиксная запись

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

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

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

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

Замечание: чаще всего синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A  B, где A, B  VN.

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

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

Например, обычной (инфиксной) записи выражения

a*(b+c)-(d-e)/f

соответствует такая постфиксная запись:

abc+*de-f/-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I := E

в ПОЛИЗе будет записан как

I E :=

где ":=" - это двухместная операция, а I и Е - ее операнды; I означает, что операндом операции ":=" является адрес переменной I, а не ее значение.