Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
do {x x (a b (c/2 1)) a; y y 2;} while (y 10); Если не является, объясните почему, и предложите свой вариант ПОЛИЗа для этого фраг- мента программы. 7. Является ли запись ПОЛИЗ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 i 1 = ; i n < 36 !F a a b + 1 - x y 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 y 2 + / - * 5 + = ; i i 2 + = ; 5 ! правильной записью в ПОЛИЗе следующего фрагмента программы на Си: for ( i 1; i n; i i 2 ) a (a b 1) (x y /(y 2)) 5; Если не является, объясните почему и предложите свой вариант ПОЛИЗа для этого фраг- мента программы. 8. а) перевести в ПОЛИЗ фрагмент программы на Си: i 10; s 0; while ( i 0 && s 40 ) { p + f(i+s) ? i : s++ ; }; b) выражение в ПОЛИЗе записать в инфиксной форме (на Си). x y z a x 5 y / z 6 8 9. а) перевести в ПОЛИЗ фрагмент программы на Си: if (z x y 5) a x y? (z x 6): (z=a y); else z + y ; b) выражение в ПОЛИЗе записать в инфиксной форме (на Си). x a x z y / z 6 a Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ 112 10. Предложить ПОЛИЗ для следующих операторов: a) if( E ) S 1 ; S 2 ; S 3 Семантика этого оператора такова: вычисляется значение выражения Е; если его значение меньше 0, то выполняется оператор S 1 ; если равно 0 — оператор S 2 , иначе — оператор S 3 b) choice ( S 1 ; S 2 ; S 3 ), E Семантика: вычисляется значение выражения Е; если его значение равно i, то выполняется оператор S i для i 1, 2, 3; иначе оператор choice эквивалентен пустому оператору. c) cycle ( E 1 ; E 2 ; E 3 ), S Семантика этого оператора отличается от семантики оператора for в языке Си только тем, что оператор S выполняется, по крайней мере, один раз (т.е. после вычисления выражения Е 1 сразу выполняется оператор S, затем вычисляется значение Е 3 , потом — значение Е 2 , ко- торое используется для контроля за количеством повторений цикла также, как и в цикле for). 11. Построить грамматику для выражений, содержащих переменные, знаки операций , , , / и скобки ( ). Грамматика должна отражать одинаковый приоритет и лево-ассоциативность всех четырех операций. Определить действия по переводу таких выражений в ПОЛИЗ. 12. Изменить приоритет операций отношения в М-языке — сделать его наивысшим. По- строить соответствующую грамматику, отражающую этот приоритет. Написать синтаксиче- ский анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ. 13. Построить КС-грамматику, аналогичную данной, E T { T} T F { F} F (E) | i с той лишь разницей, что в новом языке перед идентификатором будет допускаться унар- ный минус, имеющий наивысший приоритет (например, a b c допускается и означает a ( b) ( c). В созданную грамматику вставить действия по переводу такого выражения в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си 14. Дана грамматика, описывающая выражения: E TE E TE | T FT T FT | F PF F ^ PF | P (E) | i Включить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си 113 Литература [1]. Д. Грис. Конструирование компиляторов для цифровых вычислительных машин. — М.: Мир, 1975. [2]. Ф. Льюис, Д. Розенкранц, Р. Стирнз. Теоретические основы проектирования компиля- торов. — М.: Мир, 1979. [3]. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. — Т. 1,2. — М.: Мир, 1979. [4]. Ф. Вайнгартен. Трансляция языков программирования. — М.: Мир, 1977. [5]. И. Л. Братчиков. Синтаксис языков программирования. — М.: Наука, 1975. [6]. С. Гинзбург. Математическая теория контекстно-свободных языков. — М.: Мир, 1970. [7]. Дж. Фостер. Автоматический синтаксический анализ. — М.: Мир, 1975. [8]. В. Н. Лебедев. Введение в системы программирования. — М.: Статистика, 1975. [9]. Б. Ф. Мельников. Подклассы класса контекстно-свободных языков. — М.: МГУ, 1995. [10]. В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В. Горячая. Машины Тьюринга и алгоритмы Маркова. Решение задач. — М.:МГУ, 2006. [11]. А. Ахо., Р. Сети, Дж. Ульман. Компиляторы: принципы, технологии, инструменты. — М.: «Вильямс», 2001. [12]. А. Ахо, М. Лам, Р.Сети, Дж. Ульман. Компиляторы: принципы, технологии и инстру- ментарий. — М.: «Вильямс», 2008. 114 Содержание МГУ им. М. В. Ломоносова ...................................................................................... 2 Рецензенты: .............................................................................................................. 2 Элементы теории формальных языков и грамматик ............................................. 3 Введение .................................................................................................................................... 3 Основные понятия и определения ......................................................................................... 3 Классификация грамматик и языков по Хомскому ................................................................. 7 Грамматики с ограничениями на вид правил вывода .......................................................... 7 Иерархия Хомского ............................................................................................................... 9 Примеры грамматик и языков ................................................................................................ 11 Регулярные .......................................................................................................................... 12 Контекстно-свободные ........................................................................................................ 12 Неукорачивающие и контекстно-зависимые ..................................................................... 13 Без ограничений на вид правил (тип 0) .............................................................................. 13 Замечание о связи между языком и грамматикой .............................................................. 14 Разбор цепочек ........................................................................................................................ 15 Преобразования грамматик .................................................................................................... 19 Алгоритм удаления недостижимых символов ................................................................... 19 Алгоритм удаления бесплодных символов ........................................................................ 19 Алгоритм приведения грамматики ..................................................................................... 20 Алгоритм устранения правил с пустой правой частью ..................................................... 20 Элементы теории трансляции ............................................................................... 21 Введение .................................................................................................................................. 21 Разбор по регулярным грамматикам ...................................................................................... 22 Алгоритм разбора по диаграмме состояний....................................................................... 24 Пример разбора цепочки ..................................................................................................... 27 О недетерминированном разборе ....................................................................................... 28 Регулярные выражения ....................................................................................................... 34 Задачи лексического анализа .................................................................................................. 35 Лексический анализатор для М-языка................................................................................ 37 Синтаксический анализ........................................................................................................... 47 Метод рекурсивного спуска ................................................................................................ 48 Нисходящий анализ с прогнозируемым выбором альтернатив ........................................ 52 О применимости метода рекурсивного спуска .................................................................. 53 Задача разбора для неоднозначных грамматик .................................................................. 65 О других методах распознавания КС-языков.................................................................... 66 Синтаксический анализатор для М-языка .......................................................................... 67 Семантический анализатор для М-языка ........................................................................... 74 Генерация внутреннего представления программ ................................................................. 81 Язык внутреннего представления программы ................................................................... 81 Синтаксически управляемый перевод ................................................................................ 85 115 Генератор внутреннего представления программы на М-языке ....................................... 87 Интерпретатор ПОЛИЗа для модельного языка ................................................................ 89 Задачи ..................................................................................................................... 93 I. Грамматики и языки. Классификация по Хомскому .......................................................... 93 II. Регулярные грамматики, конечные автоматы, разбор по ДС ........................................... 99 III. Метод рекурсивного спуска. КС-грамматики с действиями ......................................... 103 IV. Синтаксически управляемый перевод ............................................................................ 108 V. ПОЛИЗ, перевод в ПОЛИЗ .............................................................................................. 109 Литература ............................................................................................................ 113 |