Главная » Просмотр файлов » И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции

И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 14

Файл №1114891 И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции) 14 страницаИ.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891) страница 142019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Любое имя, используемое в программе, должно быть описано и только один раз.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) надо запоминать (мы будем их запоминать в стеке целых чисел 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";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)Именно это свойство грамматики позволит провести синтаксически-управляемыйконтроль контекстных условий.Упражнение.

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

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

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

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6367
Авторов
на СтудИзбе
310
Средний доход
с одного платного файла
Обучение Подробнее