Лекции (2) (Презентации лекций (PDF))

Семантический анализКC-грамматики, с помощью которых описывают синтаксис языковпрограммирования, не позволяют задавать контекстные условия (КУ),имеющиеся в любом языке. Проверку КУ называют семантическиманализом.Наиболее часто встречающиеся контекстные условия: каждый используемый в программе идентификатор должен бытьописан, но не более одного раза в одной зоне описания; при вызове функции число и тип фактических параметров должнысоответствовать числу и типам формальных параметров; обычно в языке накладываются ограничения на- типы операндов любой операции, определенной в этом языке;- типы левой и правой частей в операторе присваивания;- тип параметра цикла;- тип условия в операторах цикла и условном операторе и т.п.Проверка КУ будет проводиться, как только синтаксический анализаторраспознает конструкцию, на компоненты которой наложены некоторыеограничения, т.е.

на этапе синтаксического анализа должны выполнятьсянекоторые дополнительные действия, осуществляющие семантическийконтроль.Вставка действий в КС-грамматикуЕсли для синтаксического анализа используется метод рекурсивногоспуска, то для контроля КУ в тела процедур РС-метода необходимо вставитьвызовы дополнительных "семантических" процедур (семантические действия).Сначала семантические действия вставляются в синтаксические правила, апотом по этим расширенным правилам строятся процедуры РС-метода.Чтобы отличать вызовы семантических процедур от других символовграмматики, они заключаются в угловые скобки.Фактически при этом расширяется понятие КС-грамматики.Пусть в грамматике есть правилоA → a < D1 > B < D1; D2 > | b C < D3 > ,гдеA, B, C  N; a,b  T; < Di > - есть вызов процедуры Di, i = 1, 2, 3.По такому правилу грамматики процедуру для РС-метода будет следующей:void A ( ) {if (c == 'a‘) { gc( ); D1( ); B( ); D1( ); D2( ); }elseif (c == 'b') { gc( ); C( ); D3( ); }else throw c;}ПримерНаписать грамматику, которая порождает языкL = {  (0,1)+ |  содержит равное количество 0 и 1}.Решить эту задачу можно- чисто синтаксическими средствами - описать цепочки,обладающие нужным свойством;- с помощью синтаксических правил описатьпроизвольные цепочки из 0 и 1, а потом вставитьдействия для отбора цепочек с равным количеством 0 и 1.S → < k0 = k1 = 0; > A A → 0 < k0++; > B | 1 < k1++;> BB → A | ε < if (k0 != k1) throw "ERROR !!!"; >Семантический анализатор для М-языкаКонтекстные условия, выполнение которых надоконтролировать в программах на М-языке, таковы: Любое имя, используемое в программе, должно бытьописано и только один раз. В операторе присваивания типы переменной и выражениядолжны совпадать. В условном операторе и в операторе цикла в качествеусловия возможно только логическое выражение. Операнды операции отношения должны бытьцелочисленными. Тип выражения и совместимость типов операндов ввыражении определяются по обычным правилам(как в Паскале).Для проверки КУ М-языка в синтаксические правилаграмматики вставим вызовы процедур, осуществляющихнеобходимый контроль, а затем перенесем их в процедурырекурсивного спуска.Обработка описанийВ синтаксические правила для описаний нужно вставить действия, спомощью которых можно запомнить типы переменных иконтролировать единственность их описания.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";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 ( ) );else throw "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 );else throw "wrong types are in operation";prog.put_lex (Lex (op) );}Для контроля за типом операнда одноместной операции 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);prog.put_lex (Lex (LEX_NOT));}}Сравним грамматики, описывающие выражения, состоящиеиз символов + , * , ( , ) , i:G1:E → E+E | E*E | (E) | iG2:E → E+T | E*T | TT → i | (E)G3:E → T+E | T*E | TT → i |(E)G4:E → T | E+TT → F | T*FF → i | (E)G5:E → T | T+ET → F | F*TF → i | (E)Правила вывода выражений модельногоязыка с действиями для контроляконтекстных условийE  E1 | E1 [= |< |>] <st_char.push(TD[c_val])> E1<check_op()>E1  T { [ + | - | or ] <st_char.push (TD[c_val] )> T <check_op()>}T  F { [ * | / | and ] <st_char.push (TD[c_val] )>F<check_op()>}F  I < check_id() > | N <st_char.push ("int")> |[ true | false ] <st_char.push ("bool")> | not F < check_not() > | (E)Контроль контекстных условий в операторахS  I := E | if E then S else S | while E do S | B | read (I) | write (E)Оператор присваивания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 ( ) >Условный оператор, оператор цикла, оператор вводаif E then S else S | while E do S | read (I)Контекстные условия:- в условном операторе и в операторе цикла в качестве условия возможны толькологические выражения.- операнд оператора ввода должен быть описан.Для контроля КУ в условном операторе и операторе цикла функция eq_bool ():void Parser::eq_bool () {if ( st_lex.pop() != LEX_BOOL )throw "expression is not boolean";}Для поверки операнда оператора ввода read (I) используется следующую функцию:void Parser::check_id_in_read () {if ( !TID [c_val].get_declare( ) ) throw "not declared";}Правила вывода для условного оператора и операторов цикла и ввода:if E < eq_bool () > then S else S | while E < eq_bool ( ) > do S | read (I < check_id_in_read ( )>)Грамматика с действиями для раздела описаний М-языка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;}}}.