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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Кроме того, нужно проверять, нет ли повторных описанийидентификаторов. Эта информация становится известной в тот момент,когдасинтаксическийанализаторобрабатываетописания.Следовательно, в синтаксические правила для описаний нужно вставитьдействия, с помощью которых будем запоминать типы переменных иконтролировать единственность их описания.Лексический анализатор запомнил в таблице идентификаторов TID всеидентификаторы-лексемы, которые были им обнаружены в текстеисходной программы. Информацию о типе переменных и о наличии ихописания естественно заносить в ту же таблицу.Пусть каждая строка в TID имеет видstruct record {char *name; /* идентификатор */int declare; /* описан ? 1-"да", 0-"нет" */char *type; /* тип переменной */...};Тогда таблица идентификаторов TID - это массив структур#define MAXSIZE_TID 1000struct record TID [MAXSIZE_TID];причем i-ая строка соответствует идентификатору-лексеме вида (4,i).Лексический анализатор заполнил поле name; значения полей declare иtype будем заполнять на этапе семантического анализа.Для этого нам потребуется следующая функция:void decid (int i, char *t) - в i-той строке таблицы TID контролирует изаполняет поле declare и, если лексема (4,i) впервые встретилась вразделе описаний, заполняет поле type:void decid (int i, char *t){if (TID [i].declare) ERROR(); /*повторное описание */else {TID [i].declare = 1; /* описан ! */strcpy (TID [i].type, t);} /* тип t ! */}Раздел описаний имеет видD → I {,I}: [int | bool],т.е.

имени типа (int или bool) предшествует список идентификаторов.Эти идентификаторы (вернее, номера соответствующих им строктаблицы TID) надо запоминать (например, в стеке), а когда будетпроанализировано имя типа, заполнить поля declare и type в этихстроках.Для этого будем использовать функции работы со стеком целых чисел:void ipush (int i); /* значение i - в стек */int ipop (void); /* из стека - целое */Будем считать, что (-1) - "дно" стека; тогда функцияvoid dec (char *t){int i;while ((i = ipop()) != -1)decid(i,t);}считывает из стека номера строк TID и заносит в них информацию оналичии описания и о типе t.С учетом этих функций правило вывода с действиями для обработкиописаний будет таким:D → <ipush (-1)> I <ipush (curr_lex.value)>{,I <ipush (curr_lex.value)>}:[ int <dec ("int")> | bool < dec ("bool")> ]Контроль контекстных условий в выраженииПусть есть функцияchar *gettype (char *op, char *t1, char *t2),которая проверяет допустимость сочетания операндов типа t1 (первыйоперанд) и типа t2 (второй операнд) в операции op; если типысовместимы, то выдает тип результата этой операции; иначе - строку"no".Типы операндов и обозначение операции будем хранить в стеке; дляэтого нам нужны функции для работы со стеком строк:void spush (char *s); /* значение s - в стек */char *spop (void); /* из стека - строку */Если в выражении встречается лексема-целое_число или логическиеконстанты true или false,то соответствующий тип сразу заносим в стек спомощью spush("int") или spush("bool").Если операнд - лексема-переменная, то необходимо проверить, описанали она; если описана, то ее тип надо занести в стек.

Эти действия можновыполнить с помощью функции checkid:void checkid (void){int i;i = curr_lex.value;if (TID [i].declare) /* описан? */spush (TID [i].type); /* тип - в стек */else ERROR(); /* описание отсутствует */}Тогда для контроля контекстных условий каждой тройки - "операнд-операция-операнд" будемиспользовать функцию checkop:void checkop (void){char *op;char *t1;char *t2;char *res;t2 = spop(); /* из стека - тип второго операнда */op = spop(); /* из стека - обозначение операции */t1 = spop(); /* из стека - тип первого операнда */res = gettype (op,t1,t2); /* допустимо ? */if (strcmp (res, "no")) spush (res); /* да! */else ERROR(); /* нет! */}Для контроля за типом операнда одноместной операции not будем использовать функциюchecknot:void checknot (void){if (strcmp (spop (), "bool")) ERROR();else spush ("bool");}Теперь главный вопрос: когда вызывать эти функции?В грамматике модельного языка задано старшинство операций:наивысший приоритет имеет операция отрицания, затем в порядкеубывания приоритета - группа операций умножения (*, /, and), группаопераций сложения (+,-,or), операции отношения.E → E1 | E1 [ = | < | > ] E1E1 → T {[ + | - | or ] T}T → F {[ * | / | and ] F}F → I | N | [ true | false ] | not F | (E)Именно это свойство грамматики позволит провести синтаксическиуправляемый контроль контекстных условий.Замечание: сравните грамматики, описывающие выражения, состоящиеиз символов +, *, (, ), i:G1: E → E+E | E*E | (E) | i G4: E → T | E+TG2:E → E+T | E*T | TT → i | (E)G3:F → i | (E)E → T+E | T*E | TT → i |(E)T → F | T*FG5:E → T | T+ET → F | F*TF → i | (E),оцените, насколько они удобны для трансляции выражений.Правила вывода выражений модельного языка с действиями дляконтроля контекстных условий:E → E1 | E1 [ = | < | > ] <spush(TD[curr_lex.value])>E1 <checkop()>E1 → T {[ + | - | or ] <spush(TD[curr_lex.value])>T <checkop()>}T → F {[ * | / | and ] <spush(TD[curr_lex.value])>F<checkop()>}F → I <checkid()> | N <spush("int")> |[ true | false ] <spush ("bool") |not F <checknot()> | (E)Замечание: TD - это таблица ограничителей, к которым относятся изнаки операций; будем считать, что это массив#define MAXSIZE_TD 50char * TD[MAXSIZE_TD];именно из этой таблицы по номеру лексемы в классе выбираемобозначение операции в виде строки.Контроль контекстных условий в операторахSI := 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()>1. Условный оператор и оператор цикла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 50char * 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⊥E → () | (E {, E}) | AA→a|bb)S → P := E | if E then S | if E then S else SP → I | I (e)E → T {+T}T → F {*F}F → P | (E)I→a|bc)S → type I = T {; I = T} ⊥T → int | record I: T {; I: T} endI→a|b|cd)S → P = E | while E do SP → I | I (E {, E})E→E+T|TT→T*F|FF → P | (E)50. Написать для заданной грамматики процедуры анализа методомрекурсивного спуска, предварительно преобразовав ее.a) S → E⊥ b) S → E⊥E → E+T | E-T | TT → T*P | PP → (E) | II→a|b|cE → E+T | E-T | TT → T*F | T/F | FF → I | I^N | (E)I→a|b|c|dN→2|3|4F → function I(I) S; I:=E endc)S → ; I:=E S | εE → E*I | E+I | Id)S → P := E | while E do SP → I | I (E {, E})E→E+T|TT→T*F|FF → P | (E)51.ВосстановитьКС-грамматикупофункциям,синтаксический анализ методом рекурсивного спуска.реализующим#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.!");}Какой язык она порождает?52.Предложитьалгоритм,использующийвведенныеранеепреобразования (см.

Характеристики

Список файлов книги