formal_languages_translation_theory (852748), страница 14
Текст из файла (страница 14)
Кроме синтаксического анализа, процедуры данного класса осуществляют действия по семантическому контролю и переводу программы во внутреннее представление. Объяснение этих дополнительных действий и вспомогательных объектов будетдано в следующих разделах.67Элементы теории трансляции / Синтаксический анализclass Parser{Lexcurr_lex; // текущая лексемаtype_of_lex c_type;intc_val;Scannerscan;Stack < int, 100 > st_int;Stack < type_of_lex, 100 > st_lex;voidvoidvoidvoidvoidvoidvoidvoidvoidP(); // процедуры РС-методаD1();D();B();S();E();E1();T();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:Polizprog;// внутреннее представление программыParser ( const char *program) : scan (program), prog (1000) {}voidanalyze(); // анализатор с действиями};void Parser::analyze (){gl ();P ();prog.print();cout << endl << "Yes!!!" << endl;}void Parser::P (){if ( c_type == LEX_PROGRAM )gl ();68Элементы теории трансляции / Синтаксический анализelsethrow curr_lex;D1 ();if ( c_type == LEX_SEMICOLON )gl ();elsethrow curr_lex;B ();if ( c_type != LEX_FIN )throw curr_lex;}void Parser::D1 (){if ( c_type == LEX_VAR ){gl ();D ();while ( c_type == LEX_COMMA ){gl();D();}}elsethrow curr_lex;}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();}else69Элементы теории трансляции / Синтаксический анализif ( c_type == LEX_BOOL ){dec ( LEX_BOOL );gl();}elsethrow curr_lex;}}}void Parser::B (){if ( c_type == LEX_BEGIN ){gl();S();while ( c_type == LEX_SEMICOLON ){gl();S();}if ( c_type == LEX_END )gl();elsethrow curr_lex;}elsethrow curr_lex;}void Parser::S (){int pl0, pl1, pl2, pl3;if ( c_type == LEX_IF ){gl();E();eq_bool();pl2 = prog.get_free ();prog.blank();prog.put_lex (Lex(POLIZ_FGO));if ( c_type == LEX_THEN ){gl();S();pl3 = prog.get_free();prog.blank();prog.put_lex (Lex(POLIZ_GO));prog.put_lex (Lex(POLIZ_LABEL, prog.get_free()),pl2);if (c_type == LEX_ELSE){gl();S();70Элементы теории трансляции / Синтаксический анализprog.put_lex(Lex(POLIZ_LABEL,prog.get_free()),pl3);}elsethrow curr_lex;}elsethrow curr_lex;} //end ifelseif ( c_type == LEX_WHILE ){pl0 = prog.get_free();gl();E();eq_bool();pl1 = prog.get_free();prog.blank();prog.put_lex (Lex(POLIZ_FGO));if ( c_type == LEX_DO ){gl();S();prog.put_lex (Lex (POLIZ_LABEL, pl0));prog.put_lex (Lex ( POLIZ_GO));prog.put_lex (Lex(POLIZ_LABEL, prog.get_free()),pl1);}elsethrow curr_lex;} //end whileelseif ( c_type == LEX_READ ){gl();if ( c_type == LEX_LPAREN ){gl();if ( c_type == LEX_ID ){check_id_in_read();prog.put_lex (Lex ( POLIZ_ADDRESS, c_val) );gl();}elsethrow curr_lex;if ( c_type == LEX_RPAREN ){gl();prog.put_lex (Lex (LEX_READ));}elsethrow curr_lex;}elsethrow curr_lex;} //end readelse71Элементы теории трансляции / Синтаксический анализif ( c_type == LEX_WRITE ){gl();if ( c_type == LEX_LPAREN ){gl();E();if ( c_type == LEX_RPAREN ){gl();prog.put_lex (Lex(LEX_WRITE));}elsethrow curr_lex;}elsethrow curr_lex;} //end writeelseif ( c_type == LEX_ID ){check_id ();prog.put_lex (Lex(POLIZ_ADDRESS,c_val));gl();if ( c_type == LEX_ASSIGN ){gl();E(); eq_type();prog.put_lex (Lex (LEX_ASSIGN) );}elsethrow curr_lex;} //assign-endelse B();}void Parser::E (){E1();if ( c_type == LEX_EQ || c_type == LEX_LSS || c_type == LEX_GTR ||c_type == LEX_LEQ || c_type == LEX_GEQ || c_type == LEX_NEQ ){st_lex.push (c_type);gl();E1();check_op();}}void Parser::E1 (){T();while ( c_type==LEX_PLUS || c_type==LEX_MINUS || c_type==LEX_OR ){st_lex.push (c_type);gl();72Элементы теории трансляции / Синтаксический анализT();check_op();}}void Parser::T (){F();while ( c_type==LEX_TIMES || c_type==LEX_SLASH || c_type==LEX_AND ){st_lex.push (c_type);gl();F();check_op();}}void Parser::F (){if ( c_type == LEX_ID ){check_id();prog.put_lex (Lex (LEX_ID, c_val));gl();}elseif ( c_type == LEX_NUM ){st_lex.push ( LEX_INT );prog.put_lex ( curr_lex );gl();}elseif ( c_type == LEX_TRUE ){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_TRUE, 1) );gl();}elseif ( c_type == LEX_FALSE ){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_FALSE, 0) );gl();}elseif ( c_type == LEX_NOT ){gl();F();check_not();}elseif ( c_type == LEX_LPAREN ){73Элементы теории трансляции / Синтаксический анализgl();E();if ( c_type == LEX_RPAREN)gl();elsethrow curr_lex;}elsethrow curr_lex;}Семантический анализатор для М-языкаКонтекстные условия, выполнение которых нам надо контролировать в программахна М-языке, таковы:1.
Любое имя, используемое в программе, должно быть описано и только один раз.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) надо запоминать (мы будем их запоминать в стеке целых чисел Stackint,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)Именно это свойство грамматики позволит провести синтаксически-управляемыйконтроль контекстных условий.Упражнение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
