Материалы (6) (1115033), страница 2
Текст из файла (страница 2)
| αnБудет получена грамматика, эквивалентная исходной.3) Если в грамматике есть нетерминал, у которого 126несколько правил вывода, и среди них есть правила,начинающиеся нетерминальными символами, т.е.имеют видA → B1α1 | ... | Bnαn | a1β1 | ... | amβmB1 → γ11 | ... | γ1k...Bn → γn1 | ... | γnp, гдеγij ∈ ( T ∪ N )*,Bi ∈ N;aj ∈ T;αi,βj,то можно заменить вхождения нетерминалов Bi ихправыми частями из правил вывода:A → γ11α1 | ... | γ1kα1 | ... | γn1αn | ... | γnpαn | a1β1 | ...
| amβmБудет получена грамматика, эквивалентная исходной.1274) Если в грамматике есть правилаA → α1A | ... | αnA | β1 | ... | βm| εB → αAβи FIRST(A) ∩ FOLLOW(A) ≠ ∅ (из-за вхождения А вправило вывода для В), то можно преобразовать их втакие:B → αA’A’ → α1A’ | ...
| αnA’ | β1β | ... |βmβ| βПолученная грамматика будет эквивалентна исходной.Задача разбора (синтаксический анализ) длянеоднозначных грамматик128две постановки задачи:(1) Даны КС-грамматика G и цепочка x. Требуетсяпроверить: x ∈ L(G)? Если да, то построить все деревья выводадля x (или все левые выводы для x, или все правые выводы для x)Для решения этой задачи можно обобщить метод рекурсивногоспуска, чтобы он работал с возвратами, пробуя различныеподходящие альтернативы.(2) ДаныКС-грамматика G и цепочка x. Требуетсяпроверить: x ∈ L(G)? Если да, то построить одно дерево выводадля x (возможно, «наиболее подходящее» в некотором смысле).129Рассмотрим пример. Грамматика неоднозначна. РСметод неприменим.G = ({if, then, else, a, b}, {S}, P, S, S’),где P = {S → if b then S S’ | a;S’ → else S | ε }.В этой грамматике для цепочки if b then if b then a else aможно построить два различных дерева вывода:Одно из них соответствует семантике Паскаля: elseотносится к ближайшему if.
Такое дерево можно получить,написав РС-процедуры, где S’ по возможности отдаетпредпочтение непустой альтернативе.130SifbthenS’SSelseif(не соответствует)bthenSaSifbthenifSbthen(соотв. семантике Паскаля)S’aεS’εSaS’elseSaСинтаксический анализатор для М-языка131Будем считать, что синтаксический и лексический анализаторывзаимодействуют следующим образом: анализ исходной программы идет подуправлением синтаксического анализатора; если для продолжения анализа емунужна очередная лексема, то он запрашивает ее у лексического анализатора;тот выдает одну лексему и "замирает" до тех пор, пока синтаксическийанализатор не запросит следующую лексему.Соглашения:• лексический анализатор — это функция-член классаScanner — get_lex (), которая в качестве результатавыдает лексемы типа (class) Lex;• в переменной Lex curr_lex будем хранить текущуюлексему, выданную лексическим анализатором, (а впеременной c_val – ее значение, в с_type – ее тип, этопригодится на этапе семантического анализа.)132Грамматика модельного языкаPD1DBSEE1TFLIN→ program D1; B⊥→ var D {,D}→ I {,I}: [ int | bool ]→ begin S {;S} end→ I := E | if E then S else S | while E do S | B | read (I) | write (E)→ E1 [ = | < | > | <= | >= | != ] E1 | E1→ T {[ + | - | or ] T}→ F {[ * | / | and ] F}→ I | N | L | not F | (E)→ true | false→a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9→0 | 1 |...| 9 | N0 | N1 |...| N9133class 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 gl (){curr_lex = scan.get_lex();c_type = curr_lex.get_type();// c_val = curr_lex.get_value();}public:// Poliz prog;Parser (const char *program):scan(program)//,prog (1000){}void analyze();};134void Parser::analyze () {gl();P();// prog.print();cout << endl << "OK" << endl;}void Parser::Pif (c_typeelse throwD1();if (c_typeelse throwB();if (c_type}() {== LEX_PROGRAM) gl();curr_lex;== LEX_SEMICOLON) gl();curr_lex;!= LEX_FIN) throw curr_lex;135void Parser::D1 () {if (c_type == LEX_VAR){gl();D();while (c_type == LEX_COMMA){ gl(); D();}}else throw curr_lex;}…Семантический анализКонтекстно-свободные грамматики, с помощью которыхописывают синтаксис языков программирования, не позволяютзадавать контекстные условия, имеющиеся в любом языке.Примеры наиболее часто встречающихся контекстных условий:(а)каждый используемый в программе идентификатор долженбыть описан, но не более одного раза в одной зоне описания;(б) при вызове функции число фактических параметров и их типыдолжны соответствовать числу и типам формальных параметров;(в) обычно в языке накладываются ограничения на типыоперандов любой операции, определенной в этом языке, на типылевой и правой частей в операторе присваивания, на тип параметрацикла, на тип условия в операторах цикла и условном операторе ит.п.136137Семантический анализатор для М-языкаКонтекстные условия, выполнение которых надо контролировать впрограммах на М-языке:1.
Любое имя, используемое в программе, должно быть описано и толькоодин раз.2. В операторе присваивания типы переменной и выражения должнысовпадать.3. В условном операторе и в операторе цикла в качестве условиявозможно только логическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выраженииопределяются по обычным правилам (как в Паскале).Проверку контекстных условий совместим с синтаксическим анализом.
Дляэтого в синтаксические правила вставим вызовы процедур, осуществляющихнеобходимый контроль, а затем перенесем их в процедуры рекурсивного спуска.Обработка описаний138Лексический анализатор запомнил в таблице идентификаторов 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, заносит в них информацию о типе соответствующихпеременных, о наличии их описаний и контролирует повторное описаниепеременных.139void 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) > ]Контроль контекстных условий в выражении140Типы операндов и обозначение операций будем хранить в стеке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:141void 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) );}142Для контроля за типом операнда одноместной операции 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));}}В грамматике модельного языка задано старшинство операций:наивысший приоритет имеет операция отрицания, затем в порядке убыванияприоритета — группа операций умножения (*, /, and), группа операцийсложения (+,-,or), операции отношения.E → E1 | E1 [ = | < | > ] E1E1 → T {[ + | - | or ] T}T → F {[ * | / | and ] F}F → I | N | [ true | false ] | not F | (E)143Именно это свойство грамматики позволит провести синтаксическиуправляемый контроль контекстных условий.Правила вывода выражений модельного языка с действиями для контроляконтекстных условий:E→E1|E1 [ = | < | > ] <st_lex.push(c_type)>E1<check_op()>E1→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.push (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)1441) Оператор присваивания 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()>1452) Условный оператор и оператор цикла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";}Правила для условного оператора и оператора цикла будут такими:if E <eq_bool()> then S else S | while E <eq_bool()> do S1463) Для поверки операнда оператора ввода read (I) можно использоватьследующую функцию:void Parser::check_id_in_read () {if ( !TID [c_val].get_declare() ) throw "notdeclared";}Правило для оператора ввода будет таким:read (I < check_id_in_read()>).В итоге получаем процедуры для синтаксического анализа методомрекурсивного спуска с синтаксически управляемым контролем контекстныхусловий, которые легко написать по правилам грамматики с действиями.В качестве примера приведем функцию для нетерминала D (разделописаний):147void 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;}}}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
