Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
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"; Элементы теории трансляции / Синтаксический анализ 76 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"; } Элементы теории трансляции / Синтаксический анализ 77 Для контроля за типом операнда одноместной операции 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 → E 1 | E 1 [ | | ] E 1 E 1 → T { [ | | or ] T } T → F { [ | / | and ] F} F → I | N | [ true | false ] | not F | (E) Именно это свойство грамматики позволит провести синтаксически-управляемый контроль контекстных условий. Упражнение. Сравните грамматики, описывающие выражения, состоящие из симво- лов , , (, ), i: G 1 : E → E E | E E | (E) | I G 2 : E → E T | E T | T T → i | (E) G 4 : E → T | E T T → F | T F F → i | (E) G 3 : E → T E | T E | T T → i | (E) G 5 : E → T | T E T → F | F T F → i | (E) Оцените, насколько они удобны для трансляции выражений методом рекурсивного спуска (G 1 — неоднозначная, леворекурсивная; G 1 , G 2 , G 3 — не учитывается приоритет опе- раций; G 4 , G 5 — учитывается приоритет операций, G 2 , G 4 — леворекурсивные, операции группируются слева направо, как принято в математике, G 3 , G 5 — операции группируются справа налево). Элементы теории трансляции / Синтаксический анализ 78 Правила вывода выражений модельного языка с действиями для контроля кон- текстных условий: E → E 1 | E 1 [ | | ] st_lex.push(c_type) E 1 check_op( ) E 1 → T { [ | | or ] st_lex.push (c_type ) T check_op( ) } T → F { [ | / | and ] st_lex.push (c_type ) F check_op( ) } F → 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"; } Элементы теории трансляции / Синтаксический анализ 79 Тогда правила для условного оператора и оператора цикла будут такими: if E eq_bool( ) then S else S | while E eq_bool( ) do S 3. Для поверки операнда оператора ввода 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 { Lex curr_lex; type_of_lex c_type; int c_val; Scanner scan; 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(); void dec ( type_of_lex type); void check_id (); void check_op (); void check_not (); void eq_type (); void eq_bool (); void 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) {} void analyze(); Элементы теории трансляции / Синтаксический анализ 80 }; 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(); } else if (c_type == LEX_BOOL) { dec ( LEX_BOOL ); gl(); } else throw curr_lex; } } } Элементы теории трансляции / Генерация внутреннего представления программ 81 Генерация внутреннего представления программ Результатом работы синтаксического анализатора должно быть некоторое внутреннее представление исходной цепочки лексем, которое отражает ее синтаксическую структуру. Программа в таком виде в дальнейшем может либо транслироваться в объектный код, либо интерпретироваться. Язык внутреннего представления программы Основные свойства языка внутреннего представления программ: а) он позволяет фиксировать синтаксическую структуру исходной программы; б) текст на нем можно автоматически генерировать во время синтаксического анали- за; в) его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться. Некоторые общепринятые способы внутреннего представления программ: а) постфиксная запись; б) префиксная запись; в) многоадресный код с явно именуемыми результатами; г) многоадресный код с неявно именуемыми результатами; д) связные списочные структуры, представляющие синтаксическое дерево. В основе каждого из этих способов лежит некоторый метод представления синтакси- ческого дерева. Замечание Чаще всего синтаксическим деревом называют дерево вывода исходной цепочки, в котором уда- лены вершины, соответствующие цепным правилам вида A → B, где A, B N. Выберем в качестве языка для представления промежуточной программы постфикс- ную запись(ее также называют ПОЛИЗ — польская инверсная запись). ПОЛИЗ идеален для внутреннего представления интерпретируемых языков програм- мированя, которые, как правило, удобно переводятся в ПОЛИЗ и легко интерпретируются. В ПОЛИЗе операнды выписаны слева направо в порядке их следования в исходном тексте. Знаки операций стоят таким образом, что знаку операции непосредственно предше- ствуют ее операнды. Простым будем называть выражение, состоящее из одной константы или имени пе- ременной. Такие выражения в ПОЛИЗе остаются без изменений. При переводе в ПОЛИЗ сложных выражений важно правильно определять границы подвыражений, являющихся ле- выми и правыми операндами бинарных операций. Проблем не возникает, если сложные под- выражения явно ограничены скобками. Например, в выражении (a b) с левым операндом операции является подвыражение a b, а правым — простое выражение с. Когда скобки явно не расставлены, как в случаях a b с и a b c, важно учитывать приоритет опера- ций, а также ассоциативность операций одинакового приоритета. Умножение имеет боль- ший приоритет, чем сложение, поэтому в выражении a b c операнд b относится к опера- Элементы теории трансляции / Генерация внутреннего представления программ 82 ции умножения и эквивалентное выражение со скобками будет таким: a (b c). В выраже- нии a b c операнд b относится к левой операции, т. е. к «минусу», а не к «плюсу» (в силу левой ассоциативности операций и ,имеющих одинаковый приоритет), и это выражение эквивалентно выражению (a b) c. Лево-ассоциативные операции группируются с помо- щью скобок слева направо: a b c d эквивалентно (( a b ) c) d . Теперь можем формально определить постфиксную запись выражений таким обра- зом: 1) если Е является простым выражением, то ПОЛИЗ выражения Е — это само вы- ражение Е; 2) ПОЛИЗом выражения Е 1 Е 2 , где — знак бинарной операции, Е 1 и Е 2 операнды для , является запись E 1 ′ E 2 ′ , где E 1 ′ и E 2 ′ — ПОЛИЗ выражений Е 1 и Е 2 соот- ветственно; 3) ПОЛИЗом выражения E, где — знак унарной операции, а Е — операнд , яв- ляется запись E′ , где E′ — ПОЛИЗ выражения Е; 4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е. Пример. ПОЛИЗом выражения a b c является a b c , но не a b c . Последняя запись является ПОЛИЗом для выражения a (b c). Алгоритм Дейкстры перевода в ПОЛИЗ выражений Будем считать, что ПОЛИЗ выражения будет формироваться в массиве, содержащем лексемы — элементы ПОЛИЗа, и при переводе в ПОЛИЗ будет использоваться вспомога- тельный стек, также содержащий элементы ПОЛИЗа (операции, имена функций) и круглые скобки. 1. Выражение просматривается один раз слева направо. 2. Пока есть непрочитанные лексемы входного выражения, выполняем действия: а) Читаем очередную лексему. б) Если лексема является числом или переменной, добавляем ее в ПОЛИЗ-массив. в) Если лексема является символом функции, помещаем ее в стек. г) Если лексема является разделителем аргументов функции (например, запятая), то до тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в ПОЛИЗ-массив. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разде- литель, либо не согласованы скобки. д) Если лексема является операцией , тогда: пока приоритет меньше либо равен приоритету операции, находящейся на вершине стека (для лево-ассоциативных операций), или приоритет строго меньше приоритета операции, находящейся на вершине стека (для право- ассоциативных операций), выталкиваем верхние элементы стека в ПОЛИЗ- массив; помещаем операцию в стек. е) Если лексема является открывающей скобкой, помещаем ее в стек. Элементы теории трансляции / Генерация внутреннего представления программ 83 ж) Если лексема является закрывающей скобкой, выталкиваем элементы из стека в ПОЛИЗ-массив до тех пор, пока на вершине стека не окажется открывающая скобка. При этом открывающая скобка удаляется из стека, но в ПОЛИЗ-массив не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в ПОЛИЗ-массив. Если в процессе выталкивания открывающей скобки не нашлось и стек пуст, это означает, что в выражении не согласованы скобки. 3. Когда просмотр входного выражения завершен, выталкиваем все оставшиеся в сте- ке символы в ПОЛИЗ-массив. (В стеке должны были оставаться только символы операций; если это не так, значит в выражении не согласованы скобки.) Например, обычной (инфиксной) записи выражения a ( b c) (d e) / f соответствует такая постфиксная запись: a b c d e f / Замечание Обратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфикс- ной записи, учтено старшинство операций, а скобки исчезли. Запись выражения в такой форме очень удобна для последующей интерпретации (т. е. вычисления значения этого выражения) с помощью стека. Алгоритм вычисления выражений, записанных в ПОЛИЗе 1) Выражение просматривается один раз слева направо и для каждого элемента вы- полняются шаги (2) или (3); 2) Если очередной элемент ПОЛИЗа — операнд, то его значение заносится в стек; 3) Если очередной элемент ПОЛИЗа — операция, то на верхушке стека сейчас нахо- дятся ее операнды (это следует из определения ПОЛИЗа и предшествующих дей- ствий алгоритма); они извлекаются из стека, над ними выполняется операция, ре- зультат снова заносится в стек; 4) Когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один эле- мент — это значение всего выражения, т. е. результат вычисления. |