Контроль контекстных условий в операторах

S ® I:= E | if E then S else E | while E do S | B | read (I) | write (E)

 

1) Оператор присваивания I:= E

Контекстное условие: в операторе присваивания типы переменной I и выражения E должны совпадать.

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

 

void eqtype (void)

{ if (strcmp (spop (), spop ())) ERROR();}

 

Следовательно, правило для оператора присваивания:

I < checkid() >:= E < eqtype() >

 

2) Условный оператор и оператор цикла

if E then S else S | while E do S

Контекстные условия: в условном операторе и в операторе цикла в качестве условия возможны только логические выражения.

В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней операции); следовательно, достаточно извлечь его из стека и проверить:

 

void eqbool (void)

{if (strcmp (spop(), "bool")) ERROR();}

 

Тогда правила для условного оператора и оператора цикла будут такими:

if E < eqbool() > then S else S | while E < eqbool() > do S

 

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

В качестве примера приведем функцию для нетерминала 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 | e A ® acAb | cA | e

E ® E*I | E+I | I B ® bB | e

 

*e) S ® Ac | dBea *f) S ® fASd | e

A ® Aa | Ab | daBc A ® Aa | Ab | dB | f

B ® cB | e B ® bcB | e

 

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 | e

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

 

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

S ® A^

A ® aA | bA | cA | e

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

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

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

 

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

S ® 0S | 1S | e

Дополнить эту грамматику действиями, исключающими из языка любые цепочки, содержащие подцепочку 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) допускается присваивание записей.