Description:

Министерство образования Российской Федерации Пензенский государственный университет И.Г. Кревский, М.Н. Селиверстов, К.В. Григорьева ФОРМАЛЬНЫЕ ЯЗЫКИ, ГРАММАТИКИ И ОСНОВЫ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ Учебное пособие (под ред. д.т.н., профессора А.М. Бершадского) Пенза 2003 УДК 681.3 Рецензенты: Кафедра "Системы автоматизированного проектирования" Воронежского государственного технического университета Доктор технических наук, профессор К.Б. Скобельцын Санкт-Петербургский государственный технический университет И.Г. Кревский, М.Н. Селиверстов, К.В. Григорьева Формальные языки, грамматики и основы построения трансляторов: Учебное пособие Под ред. А.М. Бершадского - Пенза: Изд-во Пенз. гос. ун-та, 2002. - 124 с.: 15 ил., 6 табл., библиогр. 12 назв. Представлен материал для изучения разделов, посвященных формальным языкам, грамматикам и разработке трансляторов в курсах "Лингвистическое программное обеспечение САПР" и "Теория вычислительных процессов и структур". Подробно рассмотрены основные вопросы теории грамматик и автоматов, лексический анализ, нисходящий и восходящий синтаксический анализ, построение программы синтаксического анализа для заданного синтаксиса, применение синтаксических диаграмм для построения анализаторов, таблично-управляемые и программно-управляемые анализаторы, формирование постфиксной записи арифметических выражений и операторов языка, генерация объектного кода программы. Приведены методические указания к лабораторным работам с вариантами заданий, а также требования к курсовому проекту по построению компиляторов. Учебное пособие разработано на кафедре "Системы автоматизированного проектирования" и предназначено для студентов специальностей 22.03.00 "Системы автоматизированного проектирования" и 35.15.00 "Математическое обеспечение и администрирование информационных систем", также может быть использовано для подготовки дипломированных специалистов по другим специальностям направления 654600 "Информатика и вычислительная техника", бакалавров по направлению 552800 "Информатика и вычислительная техника". СОДЕРЖАНИЕ: ВВЕДЕНИЕ. 4 1. СТРУКТУРА КОМПИЛЯТОРА. ТИПЫ ТРАНСЛИРУЮЩИХ ПРОГРАММ. 7 2. ОПРЕДЕЛЕНИЕ ЯЗЫКА. СИНТАКСИС И СЕМАНТИКА. 15 3. КЛАССИФИКАЦИЯ ГРАММАТИК. ИЕРАРХИЯ ХОМСКОГО.. 20 4. ПРОБЛЕМА РАЗБОРА. 26 5. ЛЕКСИЧЕСКИЙ АНАЛИЗ. 31 6. КОНЕЧНЫЕ АВТОМАТЫ. 35 7. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ. 40 8. LL(1) ГРАММАТИКИ. 45 9. ПРЕОБРАЗОВАНИЕ ГРАММАТИК В LL(1) ФОРМУ. 50 10. ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО ГРАФА. 56 11. ПОСТРОЕНИЕ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА ДЛЯ ЗАДАННОГО СИНТАКСИСА. 61 12. ПОСТРОЕНИЕ ТАБЛИЧНО-УПРАВЛЯЕМОЙ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА. 66 13. ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ. 71 14. РАБОТА С ТАБЛИЦЕЙ СИМВОЛОВ. 84 15. ВОССТАНОВЛЕНИЕ ПРИ СИНТАКСИЧЕСКИХ ОШИБКАХ. 88 16. ПОСТФИКСНАЯ ЗАПИСЬ. 91 17. ВНУТРЕННИЕ ФОРМЫ. 103 18. МЕТОДЫ ГЕНЕРИРОВАНИЯ КОДА. 105 19. ЛИТЕРАТУРА. 107 20. ЛАБОРАТОРНЫЕ РАБОТЫ. 108 ЛАБОРАТОНАЯ РАБОТА №1. РАЗРАБОТКА ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА. 109 ЛАБОРАТОНАЛЬНАЯ РАБОТА №2. РАЗРАБОТКА СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА. 110 ЛАБОРАТОНАЛЬНАЯ РАБОТА №3. ФОРМИРОВАНИЕ ПОСТФИКСНОЙ ЗАПИСИ. 112 ЛАБОРАТОНАЛЬНАЯ РАБОТА №4. РАЗРАБОТКА ГЕНЕРАТОРА КОДА.. 113 ПРИЛОЖЕНИЕ А. ВАРИАНТЫ ЗАДАНИЙ К ЛАБОРАТОРНЫМ РАБОТАМ. 117 ПРИЛОЖЕНИЕ Б. ТРЕБОВАНИЯ К КУРСОВОМУ ПРОЕКТУ. 123 ВВЕДЕНИЕ Большую часть программы курса "Лингвистическое и программное обеспечение САПР" занимают вопросы, связанные с изучением формальных языков, грамматик и основ построения трансляторов. По опыту преподавания этой дисциплины студентам специальности 22.03.00 "Системы автоматизированного проектирования" освоение данного материала требует от них, наряду с владением навыками программирования, серьезного изучения теоретических основ построения трансляторов. Именно поэтому значительная часть лабораторного практикума и курсового проектирования по дисциплине "Лингвистическое и программное обеспечение САПР" посвящены созданию транслятора. За рамками данного пособия сознательно оставлены вопросы, касающиеся общих вопросов организации программного обеспечения САПР, технологий структурного и объектно-ориентированного программирования, тем более что большая часть этого материала в ПГУ вынесена в отдельные дисциплины регионального компонента. Также не рассмотрены языки проектирования САПР, поскольку их рассмотрению посвящено отдельное пособие, находящееся сейчас в стадии написания. Можно сказать, что изучение теоретических основ и приобретение практических навыков написания транслятора имеют большое воспитательное значение. Не секрет, что многие студенты информационных специальностей, а часто и выпускники вузов, прекрасно умея разрабатывать программный код, абсолютно не умеют правильно поставить задачу, искренне не понимают, что любая программа будет эффективно и корректно работать лишь в том случае, когда она предварительно правильно спроектирована. Разработка транслятора это прекрасный способ понять на собственном опыте, что, не выполнив предварительных этапов (например, не разработав правильного формального описания языка и допускающей детерминированный анализ грамматики), невозможно сделать хорошо работающую программу. Ключевые слова: операнд, объявление переменный, дерево, рассмотренный, признак, инфиксный запись, синтаксический анализ, постфиксный форма, равный следующий, блок сканирование, обратный порядок, построение транслятор, описание, элемент, регулярный выражение, разбор, стек, подвыражение, машинный язык, граф, анализ, программа, строка состоящий, соответствующий, исполнитель цель, синтаксический анализатор, дерево разбор, выходной строка, должный, регулярный, активный префикс, данный, процедура, операция, курсовой проект, отправной точка, бинарный операция, уны, математическое обеспечение, мир ахо, начальный символ, язык состоящий, проблема разбор, транслятор, синтаксический ошибка, объявление, контрольный, безусловный переход, множество, последний, команда переход, бинарный оператор, отчет, синтаксический, переменный, конечный автомат, определение, генератор код, нетерминать, инфиксный выражение, стечь, очередной символ, вершина стек, следующий, автомат, процесс, входной поток, пустой строка, неоднозначный грамматик, исполнитель, операция расположенный, порождать править, преобразование, предварительный анализ, постфиксный строка, нетерминал, интерпретатор, пособие, компилятор, двухуровневый грамматик, начальный, прикладной реализация, начальный состояние, порождающий, направляющий символ, идентификатор, вывод, цель, генератор, альтернативный правый, символ, тип компьютер, следовательно, внешний символ, функция, нетерминальный символ, полный соответствие, недостаток, команда расположенный, входной, слово, возможный, присваивание присваивание, форма, входной буфер, унарный операция, идента, постфиксный, выражение, синтаксис, лексический анализатор, вариант программа, вариант, идента буква, вопрос, вычисление, вид, свёртка, переход, результат, применение, присваивание, система граф, число, синтаксический дерево, предложение, символ следующий, приоритет, проектирование, код, множество символ, запись, грамматика, работа, грамматик, блок, грамматический разбор, стартовый символ, регулярный грамматик, правый, содержащий скобка, контрольный вопрос, знак операция, строка, последовательность, основа, построение, вычислительный техник, постфиксный запись, терминальный символ, материал, грамматик тип, порядок, скобка, однопроходный компилятор, синтаксический граф, язык тип, случай, исходный, разработка транслятор, таблица, согласование скобка, файл, лексический анализ, порождающий править, класс, конфликт переноссвертка, образ, передаваться управление, инфиксный форма, конечный, помощь, левый, иерархия хомский, генерировать, реализуемый язык, точка, команда, цифра, вариант задание, часть, разработка, иденты, лабораторный, детерминированный, метод, пример, уна, анализатор, инфиксный выражениее, естественный язык, следующий символ, программирование, оператор, бин, состояние, оп, селиверстов, возврат, правый часть, курсовой проектирование, порождающий правило, язык программирование, адрес, вершина, реализация, выполнение, ошибка, литература, грамматический, продукция, конструкция, тип, терминал, лексический, правосентенциальная форма, рис, текст, реальный язык, порождать, действие, лабораторный работа, буква, правило, закрывающий скобка, подвыражение подвыражение, логический операция, структура, язык, выражение выражение, править, лексема, объект проектирование