formal_languages_translation_theory (852748), страница 15

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

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

Сравните грамматики, описывающие выражения, состоящие из символов , , (, ), i:G1:G4 :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.Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее также называют ПОЛИЗ — польская инверсная запись).ПОЛИЗ идеален для внутреннего представления интерпретируемых языков программированя, которые, как правило, удобно переводятся в ПОЛИЗ и легко интерпретируются.В ПОЛИЗе операнды выписаны слева направо в порядке их следования в исходномтексте.

Знаки операций стоят таким образом, что знаку операции непосредственно предшествуют ее операнды.Простым будем называть выражение, состоящее из одной константы или имени переменной. Такие выражения в ПОЛИЗе остаются без изменений. При переводе в ПОЛИЗсложных выражений важно правильно определять границы подвыражений, являющихся левыми и правыми операндами бинарных операций. Проблем не возникает, если сложные подвыражения явно ограничены скобками. Например, в выражении (a  b)  с левым операндомоперации  является подвыражение a  b, а правым — простое выражение с.

Когда скобкиявно не расставлены, как в случаях a  b  с и a  b  c, важно учитывать приоритет операций, а также ассоциативность операций одинакового приоритета. Умножение имеет больший приоритет, чем сложение, поэтому в выражении a  b  c операнд b относится к опера-81Элементы теории трансляции / Генерация внутреннего представления программции умножения и эквивалентное выражение со скобками будет таким: a  (b  c).

В выражении a  b  c операнд b относится к левой операции, т. е. к «минусу», а не к «плюсу» (в силулевой ассоциативности операций  и , имеющих одинаковый приоритет), и это выражениеэквивалентно выражению (a  b)  c. Лево-ассоциативные операции группируются с помощью скобок слева направо: a  b  c  d эквивалентно (( a  b )  c)  d .Теперь можем формально определить постфиксную запись выражений таким образом:1) если Е является простым выражением, то ПОЛИЗ выражения Е — это само выражение Е;2) ПОЛИЗом выражения Е1  Е2, где  — знак бинарной операции, Е1 и Е2 операндыдля , является запись E1′ E2′ , где E1′ и E2′ — ПОЛИЗ выражений Е1 и Е2 соответственно;3) ПОЛИЗом выражения  E, где  — знак унарной операции, а Е — операнд , является запись E′ , где E′ — ПОЛИЗ выражения Е;4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.Пример.

ПОЛИЗом выражения a  b  c является a b  c , но не a b c  . Последняязапись является ПОЛИЗом для выражения a  (b  c).Алгоритм Дейкстры перевода в ПОЛИЗ выраженийБудем считать, что ПОЛИЗ выражения будет формироваться в массиве, содержащемлексемы — элементы ПОЛИЗа, и при переводе в ПОЛИЗ будет использоваться вспомогательный стек, также содержащий элементы ПОЛИЗа (операции, имена функций) и круглыескобки.1. Выражение просматривается один раз слева направо.2. Пока есть непрочитанные лексемы входного выражения, выполняем действия:а)б)в)г)Читаем очередную лексему.Если лексема является числом или переменной, добавляем ее в ПОЛИЗ-массив.Если лексема является символом функции, помещаем ее в стек.Если лексема является разделителем аргументов функции (например, запятая),то до тех пор, пока верхним элементом стека не станет открывающаяся скобка,выталкиваем элементы из стека в ПОЛИЗ-массив.

Если открывающаяся скобкане встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.д) Если лексема является операцией , тогда: пока приоритет  меньше либо равен приоритету операции, находящейся навершине стека (для лево-ассоциативных операций), или приоритет  строгоменьше приоритета операции, находящейся на вершине стека (для правоассоциативных операций), выталкиваем верхние элементы стека в ПОЛИЗмассив; помещаем операцию  в стек.е) Если лексема является открывающей скобкой, помещаем ее в стек.82Элементы теории трансляции / Генерация внутреннего представления программж) Если лексема является закрывающей скобкой, выталкиваем элементы из стекав ПОЛИЗ-массив до тех пор, пока на вершине стека не окажется открывающаяскобка.

При этом открывающая скобка удаляется из стека, но в ПОЛИЗ-массивне добавляется. Если после этого шага на вершине стека оказывается символфункции, выталкиваем его в ПОЛИЗ-массив. Если в процессе выталкиванияоткрывающей скобки не нашлось и стек пуст, это означает, что в выражении несогласованы скобки.3. Когда просмотр входного выражения завершен, выталкиваем все оставшиеся в стеке символы в ПОЛИЗ-массив.

(В стеке должны были оставаться только символы операций;если это не так, значит в выражении не согласованы скобки.)Например, обычной (инфиксной) записи выраженияa  ( b  c)  (d  e) / fсоответствует такая постфиксная запись:abcdef/ЗамечаниеОбратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфиксной записи, учтено старшинство операций, а скобки исчезли.Запись выражения в такой форме очень удобна для последующей интерпретации (т.

е.вычисления значения этого выражения) с помощью стека.Алгоритм вычисления выражений, записанных в ПОЛИЗе1) Выражение просматривается один раз слева направо и для каждого элемента выполняются шаги (2) или (3);2) Если очередной элемент ПОЛИЗа — операнд, то его значение заносится в стек;3) Если очередной элемент ПОЛИЗа — операция, то на верхушке стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;4) Когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент — это значение всего выражения, т.

е. результат вычисления.Замечание1. Для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация обоперандах, хранящаяся в таблицах.2. Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак «» в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака.

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

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