Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
| 2Государственный комитет Российской Федерации 2по высшему образованию 2Рыбинская государственная авиационная 2технологическая академия 2В.Н. ПИНАЕВ 2ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ЯЗЫКОВ 2ПРОГРАММИРОВАНИЯ И ПОСТРОЕНИЕ ТРАНСЛЯТОРОВ конспект лекций Рекомендовано Учебно-методи- ческим объединением высших учеб- ных заведений Российской Федера- ции по образованию в области ави- ации, ракетостроения и космоса в качестве учебного пособия для студентов высших технических за- ведений, обучающихся по специаль- ности 22О4ОО и направлению 5528ОО 2Рыбинск 21995 . ББК 32.973 П-32 УДК 681.3.О6 Пинаев В.Н. Формальные методы описания языков программи- рования и построение трансляторов: Конспект лекций/ РГАТА. - Рыбинск, 1995. - 84 с. Рассматриваются формальные методы описания синтаксиса языков программирования, а также принципы построения трансля- торов. Описывается аппарат формальных грамматик, приводится их классификация по Хомскому. Обсуждаемые алгоритмы отдельных фаз трансляции приводятся в виде фрагментов программ или процедур на языке Паскаль. Пособие предназначено для студентов, обучающихся по спе- циальности "220400 - Программное обеспечение вычислительной техники и автоматизированных систем" или по направлению "552800 - Информатика и вычислительная техника". Ил. 17 Табл. 7 Библиогр. 16 Рецензенты: кафедра информатики и вычислительной техники Ярославского государственного педагогического университета; доктор физ.-мат. наук, профессор И.Л.Братчиков ISBN 5-88435-О22-8 C Пинаев В.Н., 1995 С Рыбинская государственная авиационная технологическая академия, 1995 . - 3 - 2ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 5 1. ТРАНСЛЯТОРЫ, КОМПИЛЯТОРЫ, ИНТЕРПРЕТАТОРЫ 8 1.1. Основные определения 8 1.2. Программно-моделируемые вычислительные машины 9 1.3. Выбор языка реализации 12 1.4. Краткий обзор процесса компиляции 14 1.5. Понятие о проходах 17 2. ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ЯЗЫКОВ 18 2.1. Определения и общие свойства порождающих грамматик 18 2.2. Классификация грамматик 22 3. ВЫВОД ЦЕПОЧЕК 24 3.1. Задача разбора 24 3.2. Дерево разбора 25 3.3. Классификация методов разбора 28 4. ЛЕКСИЧЕСКИЙ АНАЛИЗ 29 4.1. Регулярные выражения 29 4.2. Конечные автоматы 30 4.3. Лексический анализатор 32 4.4. Пример сканера для языка PL/0 34 4.5. Выход из лексического анализатора 38 5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ И КС-ГРАММАТИКИ 39 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ. МЕТОД РЕКУРСИВНОГО СПУСКА 41 38 . - 4 - 7. LL - ГРАММАТИКИ 44 7.1. Безвозвратный анализ по первому символу 44 7.2. Грамматики и синтаксические диаграммы 47 7.3. Определение LL-грамматик 48 7.4. Таблично-управляемый анализатор для LL(1)-грамматик 49 8. ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА 53 8.1. LR - грамматики 53 8.2. LR-таблицы разбора 53 8.3. Грамматики простого предшествования 55 8.4. Анализатор предшествования 57 9. ГЛОБАЛЬНЫЙ АНАЛИЗАТОР 60 10. ОБРАБОТКА ОШИБОК 63 10.1. Синтаксические ошибки 63 10.2. Контекстные ошибки 65 11. ГЕНЕРАЦИЯ КОДА 66 11.1. Интерпретатор Р-кода 67 11.2. Описание команд Р-кода 71 ЗАКЛЮЧЕНИЕ 75 ЛИТЕРАТУРА 76 ПРИЛОЖЕНИЕ 1. Программа LR-анализатора 77 ПРИЛОЖЕНИЕ 2. Синтаксические диаграммы языка PL/0 82 . - 5 - 2ВВЕДЕНИЕ В настоящее время в мире насчитывается свыше тысячи язы- ков программирования. Однако язык останется мертворожденным, если он не будет реализован на ЭВМ. Исключение могут состав- лять языки, предназначенные для проведения каких-либо формаль- ных исследований. Реализация языка означает разработку и использование спе- циальной программы,"понимающей" тексты на этом языке. Такая программа называется 2транслятором 0. Для начинающего програм- миста написание транслятора - большая и сложная работа. А так как в практических приложениях часто возникает потребность в своем, возможно, не очень сложном, но чрезвычайно удобном для вас языке, то понятно, как важно уметь ориентироваться в воп- росах разработки и реализации трансляторов. Примерами таких языков могут служить системы запросов, генераторы отчетов, языки управления некими объектами, различные препроцессоры. Даже выбранная форма и структура входных данных для какой-либо вашей программы по существу является неким языком. Одновременно возникает актуальная до настоящего времени задача представления (то есть - описания) языка программирова- ния. Такое описание необходимо и для тех, кто желает узнать и понять новый язык, и для тех, кто разрабатывает транслятор этого языка. Особенно важны формальные методы описания языков, так как только аккуратное формальное описание языка программи- рования позволит избежать различных трактовок его конструкций, а, следовательно, и их смысла. Значимость описания полезна еще и по другой причине. Лю- бой формализм позволяет перейти на более высокий уровень абстракции, охватывающий уже гораздо больше конкретных вариан- тов, один из которых и служит толчком к этой абстракции. Вот что сказал Эдсгер В. Дейкстра 14 августа 1972 года в речи при вручении ему премии Тьюринга: "... наиболее важным видом дея- тельности компетентного программиста можно считать эффективную - 6 - эксплуатацию его способности к абстрагированию. ... Какие последствия может иметь знание и сознательное использование этих приемов абстрагирования, открылось мне, когда я понял, что если бы это было известно 15 лет тому назад, то, например, шаг от БНФ к синтаксически ориентированным компиляторам занял бы несколько минут вместо нескольких лет". Различное понимание читателями одного и того же текста типично для естественных языков. Да и сам по себе используемый язык может быть многозначным. Вот один из примеров: "Он встре- тил ее на поляне с цветами". Здесь возможны сразу три интерп- ретации. Чтобы преодолеть подобные трудности, автор текста вы- нужден специальным образом оговаривать использование тех или иных слов или словосочетаний, дублировать основную мысль ка- ким-либо способом. Последнее приводит к разрастанию текста в целом и, следовательно, к затруднению его восприятия. Примером такого разрастания может служить и настоящий абзац. ( Впрочем, не исключено, что это разрастание и естественная многознач- ность русского языка могли привести к тому, что читатель не смог понять излагаемой здесь автором идеи.) Итак, наличие формального описания языка программирования снижает вероятность его неверного толкования и позволяет авто- матизировать (до некоторой степени) разработку соответствующе- го транслятора. Традиционно описание языка состоит из описания его лекси- ческих, синтаксических и семантических свойств. Для первых двух составляющих разработаны соответствующие формализмы. Су- ществуют методы и для описания семантики, но их формальное применение при разработке транслятора представляется достаточ- но затруднительным. Для тех, кто впервые знакомится с предметом обсуждения, рекомендуется освоить главу 5 "Структура языков и транслято- ров" в книге Никлауса Вирта "Алгоритмы + структуры данных = программы" [3]. Кстати, обратите внимание, выпущено два изда- ния этой книги. Первое основано на языке ПАСКАЛЬ, а второе использует язык МОДУЛА-2. Во втором издании нет упомянутой главы, и поэтому нам интересно именно первое издание. Тем, кто глубже заинтересуется теорией формальных языков и методами разработки трансляторов, мы рекомендуем познакомиться с лите- ратурой [1,2,4,6-11]. Автор считает необходимым отметить, что - 7 - при подготовке данного текста существенно использовались пере- численные издания. Основная цель подготовки данного пособия заключалась в том, чтобы собрать вместе теоретический материал и примеры практических реализаций так, чтобы начинающий программист мог использовать их в своей работе. Хотя по теории трансляции и существует хорошая литература, но, во-первых, она недоступна большинству студентов в силу малого количества экземпляров в библиотеках, и, во-вторых, нет краткого варианта курса, соче- тающего и теоретические, и практические аспекты обсуждаемых вопросов. Поэтому автор, не претендуя на оригинальность текста, надеется, что его труд окажется полезным. Пособие предназначено для студентов, обучающихся по спе- циальности "220400 - Программное обеспечение вычислительной техники и автоматизированных систем" или по направлению "552800 - Информатика и вычислительная техника". Излагаемый материал может использоваться в курсах "Построение транслято- ров", "Теоретические основы систем программирования", "Основы теории вычислительных процессов и структур", "Трансляция язы- ков программирования". От читателя требуются знания по курсам "Дискретная математика" и "Конструирование программ и языки программирования", так как отдельные алгоритмы иллюстрируются на языке ПАСКАЛЬ. Автор благодарен своему научному руководителю и рецензен- ту Братчикову Игорю Леонидовичу, заведующему лабораторией ка- федры МПОЭВС Ефимову Евгению Владимировичу, а также всем чле- нам кафедры за полезные советы по устранению многих шерохова- тостей и изъянов в изложении материала. . - 8 - 21. ТРАНСЛЯТОРЫ, КОМПИЛЯТОРЫ, ИНТЕРПРЕТАТОРЫ 21.1. Основные определения Мы начнем изложение материала с уточнения некоторых поня- тий [7]. Под вычислительной машиной в самом общем виде понима- ется устройство для хранения алгоритмов и структур данных и способное исполнять программы. В зависимости от того, как представлено это устройство, можно говорить либо о реальной физической конструкции, либо о некой гипотетической или вирту- альной машине. Последняя может не иметь ни микросхем, ни кабе- лей, ни других деталей. Тогда предполагается, что такая машина представлена в программно-моделируемом виде. Любая вычислительная машина содержит в себе устройство для исполнения команд. Это устройство должно определить оче- редную команду, выполнить соответствующие ей действия и подго- товиться к приему следующей команды. Результат работы програм- мы определяется конечным состоянием машины. Из сказанного следует важный вывод: машинный язык - это необязательно язык низкого уровня. Теоретически любой язык высокого уровня может быть реализован аппаратно. Но по сущест- ву это будет 1программно-аппаратная вычислительная машина 0, вы- полняемая на специальной 1микропрограммируемой вычислительной 1машине. 0В конечном итоге все определяется потребностями и эко- номическими возможностями. Реализация языка программирования на конкретной машине заключается в создании некоторого способа преобразования про- извольного текста на этом языке в программу для данной машины. С этой целью разрабатываются трансляторы. Под 2транслятором 0понимается специальная программа, кото- рая переводит 1исходную программу 0 в эквивалентную ей 1объектную 1программу 0. Процесс такого преобразования называется 1трансляци 0- 1ей 0. Язык, на котором написана обрабатываемая программа, назы- вается исходным, а язык, на котором записывается результирую- щая программа, называется объектным. В качестве исходного и объектного языков могут выступать как языки низкого, так и языки высокого уровня. Транслятор, преобразующий текст на языке высокого уровня в объектную программу на языке низкого уровня (близкого к ма- - 9 - шинному) или языке ассемблера, называется 2компилятором 0. После компиляции полученная объектная программа обычно не может быть исполнена непосредственно. Дальнейшая ее обработка связана с применением программ, которые могут быть отнесены к специаль- ного типа трансляторам: 1) под 1программой 0 2ассемблер 0понимается транслятор, преоб- разующий программу на 1языке ассемблера 0 (автокод) в программу на машинном языке в некоторой форме (абсолютный или перемещае- мый формат); 2) под 2загрузчиком 0понимается транслятор, преобразующий программу на языке, близком к машинному, но не содержащую пол- ностью всей информации об используемых абсолютных значениях адресов; результатом работы загрузчика является программа го- товая к выполнению на вычислительной машине. Таким образом, полный цикл трансляции программы может включать в себя несколько этапов. Например, трансляция прог- раммы на язык ассемблера, получение перемещаемого кода (ас- семблирование), формирование последовательности машинных ко- манд. И только после этого программу можно выполнить на компь- ютере. Впрочем, сама компиляция может допускать несколько эта- пов преобразования исходной программы. 21.2. Программно-моделируемые вычислительные машины Конечная цель - выполнение исходной программы - может быть достигнута и без формирования машинного кода. Этот иной вариант заключается в разработке специальной программно-моде- лируемой машины, набор команд которой приближен к операторам входного языка. Как обычно на вход машины подается обрабатыва- емая программа. Далее осуществляется возможное преобразование программы в промежуточную форму, которая может быть обработана и выполнена на нашей виртуальной машине. Описанный подход по- лучил название 1интерпретации 0, а виртуальная машина называется 1интерпретатором 0 входного языка. Разработка транслятора представляется достаточно сложной задачей, кроме тех редких случаев, когда входной язык близок к машинному. Поэтому принципиальная возможность отказаться от обязательной компиляции в машинные коды и вместо этого разра- - 10 - ботать соответствующий интерпретатор, в некоторых случаях яв- ляется чуть ли не панацеей от всех бед. Выбор схемы трансляции определяется не только сложностью задачи перевода, а и во многом зависит от свойств реализуемого языка. Представим себе ситуацию, когда язык программирования разрешает модифицировать программу в процессе ее выполнения. Примерами таких языков могут служить языки Бейсик и Пролог. Понятно, что ни один компилятор будет не в состоянии породить машинный код заранее неизвестной конструкции. Следующий пример |
Добавить документ в свой блог или на сайт
Похожие:
 | Конспект лекций Владимира Климентьева по истории философии, отредактированный... Рекомендовано Министерством общего и профессионального образования Российской федерации в качестве учебника для студентов высших... | | Курс лекций 2-е издание, стереотипное Минск 2005 удк 008(076. 6) Рекомендовано к изданию Комиссией по приемке и аттестации электронных версий учебных и учебно-методических материалов Академии управления... |
| С. П. Филин Концепции современного естествознания: конспект лекций Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования РФ и... | | Учебно-методический комплекс Специальность: 080801. 65 (351400) Прикладная... С 56 Современная информационная культура: Учебно-методический комплекс / авт сост. С. Б. Голубцов – спб.: Ивэсэп, 2010. – 42 с |
| Конспект лекций раскрывает содержание и структуру учебной дисциплины... Налоговое право : конспект лекций / сост доцент Р. В. Бобринев; Кузбасский институт экономики и права. – Кемерово, 2011 – 144 с | | Тема Содержание Нормативно-правовые документы и учебно-методическое обеспечение к началу учебного года |
| Конспект лекций Анализ рынка Форекс Учебно-тематический план дисциплины «Учет и операционная деятельность в банках» 7 | | Учебно-методический комплекс по дисциплине «Философия права» Учебно-методический комплекс включает учебную программу курса, учебно-тематический план, конспект лекций, планы проведения семинарских... |
 | И. В. Кузьмин «29» августа 2013 года ... | | Организация производства курс лекций Рекомендовано к печати методической комиссией экономического факультета ггау, протокол №1 от 22. 09. 2004 г |
| Конспект лекций по философии Часть 1 Античная философия Новосибирск... Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с | | Информационный бюллетень новых поступлений книг за сентябрь 2011 года Амангельдиева Ж. А. Финансы: учебно-методи-ческий комплекс. Астана: Казату, 2010. 146с. 1 Сбо., 2 н а., 2 ч з., 1 оф., 59 уч а |
| Конспект лекций по курсу хозяйственного права тема Понятие хозяйственного права Кафедра Истории, социологии и права Назаров Андрей Александрович конспект лекций по курсу хозяйственного права | | Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в федеральный компонент профессионального цикла дисциплин специальности и является обязательной для изучения. Данный... |
| Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в цикл общих математических и естественнонаучных дисциплин специальности и является дисциплиной по выбору студента.... | | Конспект лекций по высшей математике. В 2 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
