И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 14
Текст из файла (страница 14)
Любое имя, используемое в программе, должно быть описано и только один раз.2. В операторе присваивания типы переменной и выражения должны совпадать.3. В условном операторе и в операторе цикла в качестве условия возможно толькологическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выражении определяются пообычным правилам (как в Паскале).Проверку контекстных условий совместим с синтаксическим анализом.
Для этого всинтаксические правила вставим вызовы процедур, осуществляющих необходимый контроль, а затем перенесем их в процедуры рекурсивного спуска.Для реализации семантического анализа будем использовать следующий шаблонныйкласс Stack:template <class T, int max_size > class Stack{T s[max_size];int top;public:Stack(){top = 0;}void reset() { top = 0; }void push(T i);T pop();bool is_empty(){ return top == 0; }bool is_full() { return top == max_size; }};template <class T, int max_size >void Stack <T, max_size >::push(T i){if ( !is_full() ){s[top] = i;++top;}74Элементы теории трансляции / Синтаксический анализelsethrow "Stack_is_full";}template <class T, int max_size >T Stack <T, max_size >::pop(){if ( !is_empty() ){--top;return s[top];}elsethrow "Stack_is_empty";}Обработка описанийДля контроля согласованности типов в выражениях и типов выражений в операторах,необходимо знать типы переменных, входящих в эти выражения.
Кроме того, нужно проверять, нет ли повторных описаний идентификаторов. Эта информация становится известной втот момент, когда синтаксический анализатор обрабатывает описания. Следовательно, в синтаксические правила для описаний нужно вставить действия, с помощью которых будем запоминать типы переменных и контролировать единственность их описания.Лексический анализатор запомнил в таблице идентификаторов TID все идентификаторы-лексемы, которые были им обнаружены в тексте исходной программы. Информация отипе переменных и о наличии их описания заносится в ту же таблицу.i-ая строка таблицы TID соответствует идентификатору-лексеме вида 〈LEX_ID, i 〉.Лексический анализатор заполнил поле name; значения полей declare и type будем заполнять на этапе семантического анализа.Раздел описаний имеет видD → I {, I}: [int | bool],т. е. имени типа (int или bool) предшествует список идентификаторов.
Эти идентификаторы(вернее, номера соответствующих им строк таблицы TID) надо запоминать (мы будем их запоминать в стеке целых чисел Stack<int,100> st_int), а когда будет проанализировано имя типа, надо заполнить поля declare и type в этих строках.Функция void Parser::dec (type_of_lex type) считывает из стека номера строк таблицыTID, заносит в них информацию о типе соответствующих переменных, о наличии их описаний и контролирует повторное описание переменных.void Parser::dec ( type_of_lex type ){int i;while ( !st_int.is_empty()){i = st_int.pop();if ( TID[i].get_declare() )throw "twice";75Элементы теории трансляции / Синтаксический анализelse{TID[i].put_declare();TID[i].put_type(type);}}}С учетом имеющихся функций правило вывода с действиями для обработки описанийбудет таким:D → 〈 st_int.reset( ) 〉 I 〈 st_int.push ( c_val ) 〉{, I 〈 st_int.push (c_val) 〉 }:[ int 〈 dec ( LEX_INT ) 〉 | bool 〈 dec ( LEX_BOOL ) 〉 ]Контроль контекстных условий в выраженииТипы операндов и обозначение операций мы будем хранить в стеке Stack 〈type_of_lex,100〉 st_lex.Если в выражении встречается лексема целое_число или логические константы trueили false, то соответствующий тип сразу заносится в стек.Если операнд — лексема-переменная, то необходимо проверить, описана ли она; еслиописана, то ее тип надо занести в стек.
Эти действия можно выполнить с помощью функцииcheck_id( ):void parser::check_id(){if ( TID[c_val].get_declare() )st_lex.push(TID[c_val].get_type());elsethrow "not declared";}Тогда для контроля контекстных условий каждой тройки — 〈операнд – операция –операнд〉 (для проверки соответствия типов операндов данной двуместной операции) будемиспользовать функцию check_op( ):void Parser::check_op (){type_of_lex t1, t2, op, t = LEX_INT, r = LEX_BOOL;t2 = st_lex.pop();op = st_lex.pop();t1 = st_lex.pop();if ( op==LEX_PLUS || op==LEX_MINUS || op==LEX_TIMES || op==LEX_SLASH )r = LEX_INT;if ( op == LEX_OR || op == LEX_AND )t = LEX_BOOL;if ( t1 == t2 && t1 == t )st_lex.push(r);elsethrow "wrong types are in operation";}76Элементы теории трансляции / Синтаксический анализДля контроля за типом операнда одноместной операции not будем использоватьфункцию check_not( ):void Parser::check_not (){if (st_lex.pop() != LEX_BOOL)throw "wrong type is in not";else{st_lex.push (LEX_BOOL);}}Теперь главный вопрос: когда вызывать эти функции?В грамматике модельного языка задано старшинство операций: наивысший приоритетимеет операция отрицания, затем в порядке убывания приоритета — группа операций умножения (∗, /, and), группа операций сложения (+, −, or), операции отношения.E → E1 | E1 [ = | < | > ] E1E1 → T { [+ | − | or ] T }T → F { [ ∗ | / | and ] F}F → I | N | [ true | false ] | not F | (E)Именно это свойство грамматики позволит провести синтаксически-управляемыйконтроль контекстных условий.Упражнение.
Сравните грамматики, описывающие выражения, состоящие из символов +, ∗, (, ), i:G4 :G1:E → E + E | E ∗ E | (E) | IE → T|E+TT → F|T∗FG2:F → i | (E)E → E+T|E∗T|TT → i | (E)G3:G5 :E → T|T+ET → F|F∗TF → i | (E)Оцените, насколько они удобны для трансляции выражений методом рекурсивногоспуска (G1 — неоднозначная, леворекурсивная; G1, G2, G3 — не учитывается приоритет операций; G4, G5 — учитывается приоритет операций, G2, G4 — леворекурсивные, операциигруппируются слева направо, как принято в математике, G3, G5 — операции группируютсясправа налево).ET→ T+E|T∗E|T→ i | (E)77Элементы теории трансляции / Синтаксический анализПравила вывода выражений модельного языка с действиями для контроля контекстных условий:EE1TF→→→→E1 | E1 [ = | < | > ] 〈st_lex.push(c_type) 〉 E1 〈check_op( ) 〉T { [ + | −| or ] 〈st_lex.push (c_type ) 〉 T 〈check_op( ) 〉}F { [ ∗ | / | and ] 〈st_lex.push (c_type ) 〉 F 〈check_op( ) 〉}I 〈 check_id( ) 〉 | N 〈st_lex (LEX_INT) 〉 | [ true | false ]〈st_lex.push (LEX_BOOL) 〉 | not F 〈 check_not( ) 〉 | (E)Контроль контекстных условий в операторахS → I := E | if E then S else S | while E do S | B | read (I) | write (E)1.
Оператор присваиванияI := EКонтекстное условие: в операторе присваивания типы переменной I и выражения Eдолжны совпадать.В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней операции); если при анализе идентификатора Iпроверить, описан ли он, и занести его тип в тот же стек (для этого можно использоватьфункцию check_id( ) ), то достаточно будет в нужный момент считать из стека два элемента исравнить их:void Parser::eq_type (){if ( st_lex.pop() != st_lex.pop() ) throw "wrong types are in :=";}Следовательно, правило для оператора присваивания:I 〈 check_id( ) 〉 := E 〈 eq_type( ) 〉2.
Условный оператор и оператор циклаif E then S else S | while E do SКонтекстные условия: в условном операторе и в операторе цикла в качестве условиявозможны только логические выражения.В результате контроля контекстных условий выражения E в стеке останется тип этоговыражения (как тип результата последней операции); следовательно, достаточно извлечь егоиз стека и проверить:void Parser::eq_bool (){if ( st_lex.pop() != LEX_BOOL )throw "expression is not boolean";}78Элементы теории трансляции / Синтаксический анализТогда правила для условного оператора и оператора цикла будут такими:if E 〈eq_bool( )〉 then S else S | while E 〈eq_bool( )〉 do S3.
Для поверки операнда оператора ввода read(I) можно использовать следующуюфункцию:void Parser::check_id_in_read (){if ( !TID [c_val].get_declare() )throw "not declared";}Правило для оператора ввода будет таким:read ( I 〈 check_id_in_read( ) 〉 ) .В итоге получаем процедуры для синтаксического анализа методом рекурсивногоспуска с синтаксически-управляемым контролем контекстных условий, которые легко написать по правилам грамматики с действиями.Класс Parser с дополнительными полями и методами для семантического анализа выглядит так:class Parser{Lexcurr_lex;type_of_lex c_type;intc_val;Scannerscan;Stack < int, 100 > st_int;Stack < type_of_lex, 100 > st_lex;void P(); void D1(); void D(); void B(); void S();void E(); void E1(); void T(); void F();voidvoidvoidvoidvoidvoidvoiddec ( type_of_lex type);check_id ();check_op ();check_not ();eq_type ();eq_bool ();check_id_in_read ();void gl (){curr_lex = scan.get_lex();c_type = curr_lex.get_type();c_val = curr_lex.get_value();}public:Parser ( const char *program) : scan (program) {}voidanalyze();79Элементы теории трансляции / Синтаксический анализ};void Parser::analyze (){gl ();P ();cout << endl << "Yes!!!" << endl;}В качестве примера реализации приведем функцию с семантическими действиями длянетерминала D (раздел описаний):void Parser::D (){st_int.reset();if (c_type != LEX_ID)throw curr_lex;else{st_int.push ( c_val );gl();while (c_type == LEX_COMMA){gl();if (c_type != LEX_ID)throw curr_lex;else{st_int.push ( c_val );gl();}}if (c_type != LEX_COLON)throw curr_lex;else{gl();if (c_type == LEX_INT){dec ( LEX_INT );gl();}elseif (c_type == LEX_BOOL){dec ( LEX_BOOL );gl();}else throw curr_lex;}}}80Элементы теории трансляции / Генерация внутреннего представления программГенерация внутреннего представления программРезультатом работы синтаксического анализатора должно быть некоторое внутреннеепредставление исходной цепочки лексем, которое отражает ее синтаксическую структуру.Программа в таком виде в дальнейшем может либо транслироваться в объектный код, либоинтерпретироваться.Язык внутреннего представления программыОсновные свойства языка внутреннего представления программ:а) он позволяет фиксировать синтаксическую структуру исходной программы;б) текст на нем можно автоматически генерировать во время синтаксического анализа;в) его конструкции должны относительно просто транслироваться в объектный кодлибо достаточно эффективно интерпретироваться.Некоторые общепринятые способы внутреннего представления программ:а) постфиксная запись;б) префиксная запись;в) многоадресный код с явно именуемыми результатами;г) многоадресный код с неявно именуемыми результатами;д) связные списочные структуры, представляющие синтаксическое дерево.В основе каждого из этих способов лежит некоторый метод представления синтаксического дерева.ЗамечаниеЧаще всего синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A → B, где A, B ∈ N.Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее также называют ПОЛИЗ — польская инверсная запись).ПОЛИЗ идеален для внутреннего представления интерпретируемых языков программированя, которые, как правило, удобно переводятся в ПОЛИЗ и легко интерпретируются.В ПОЛИЗе операнды выписаны слева направо в порядке их следования в исходномтексте.
Знаки операций стоят таким образом, что знаку операции непосредственно предшествуют ее операнды.Простым будем называть выражение, состоящее из одной константы или имени переменной. Такие выражения в ПОЛИЗе остаются без изменений. При переводе в ПОЛИЗсложных выражений важно правильно определять границы подвыражений, являющихся левыми и правыми операндами бинарных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
