Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Контроль контекстных условий в операторах
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. Написать КС-грамматику с действиями для порождения
58. Написать КС-грамматику с действиями для порождения
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) допускается присваивание записей.
|
||||||
Последнее изменение этой страницы: 2016-12-30; просмотров: 308; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.212.145 (0.02 с.) |