Обзор источников
Работа над проектом требует тщательного изучения наработок, которые
существуют в данной области. В данный разделе будут рассмотрены основные
источники информации по данной тематике (книги, лекции, Web ресурсы).
Все эти источники использовались в данном проекте.
Альфред Ахо, Рави Сети, Джеффри Ульман
Компиляторы. Принципы, технологии, инструменты.
Альфред Ахо, Рави Сети, Джеффри Ульман
Компиляторы. Принципы, технологии, инструменты.
Издательский дом "Вильямс" 2001г.
Эта книга является, пожалуй, самым важным источником информации по построению
компиляторов. Она является продолжением книги А. Ахо Д. Ульмана
"Принципы разработки компиляторов", написанной в 1970-х годах. Вы могли
слышать о ней, как о книге дракона. Ахо и Ульман
известны как авторы многих книг по алгоритмам и программированию,
они являются признанными классиками, наравне с Кнутом и Виртом.
Книга рассматривает все вопросы связанные с построением компиляторов, от
лексического анализа до оптимизации кода. Также в этой книге можно найти
много полезной информации, которая пригодится не только при построении
компилятора. Например, здесь можно найти описания конечных автоматов,
регулярных выражений, некоторые секреты известных компиляторов и пр.
Эта книга является довольно полным описанием всех фаз компиляции.
Ее можно использовать как учебник. Она написана простым и понятным
языком, содержит много примеров и упражнений для самоконтроля.
В книге вводятся практически все понятия, и определения
которые встречаются при создании компилятора.
Глава посвященная лексическому анализу вводит понятия
токена, лексемы, шаблона. Определяются роль и задачи лексического
анализа как фазы работы компилятора. В качестве лексического
анализатора- сканера рассматривается конечный автомат, который строится
на основе регулярных выражений. Здесь можно найти алгоритмы построения
недетерминированного конечного автомата по регулярным выражениям
и преобразования его в детерминированный. Рассматриваются вопросы
эффективности подобных алгоритмов, способы уменьшения расходов памяти
при построении конечных автоматов. В качестве инструмента для построения
сканеров описывается известная утилита LEX.
Синтаксический анализ также представлен целой главой
книги. В ней прежде всего рассказывается о роли синтаксического
анализа. Вводится определение контекстно-свободной формальной
грамматики. Уделено внимание однозначности формальных грамматик,
их разработке (приведены некоторые алгоритмы преобразования грамматик).
Далее в главе описываются нисходящие и
восходящие способы разбора.
В качестве нисходящих анализаторов приведены ЛЛ1 анализатор и метод
рекурсивного спуска. Для ЛЛ1 анализатора здесь можно найти достаточно
подробный алгоритм построения управляющих таблиц, а также найти
рекомендации по восстановлению после ошибок.
Восходящий анализ представлен алгоритмом перенос-свертка. Дано
неформальное описание этого алгоритма, рассмотрены проблемы, связанные
с этим алгоритмом (конфликты перенос-свертка, свертка-свертка).
Достаточно подробно можно прочитать о LR-анализаторах
и LR-грамматиках. Приводится алгоритм построения
таблиц для SLR-анализа, LR-анализа и самого широко применяемого-
LALR-анализа. В процессе построения этих таблиц возможно
неэффективное расходование памяти, решение этой проблемы можно найти
в этой главе.
Грамматики предшествования практически не рассмотрены, лишь немного
внимания уделено грамматике операторного предшествования (здесь она
называется грамматики приоритета операторов).
Также здесь можно найти способы "борьбы" в неоднозначными грамматиками.
Например, с помощью использования приоритетов и ассоциативности для
разрешения конфликтов. Решена задача "кочующего else" для LR-грамматик.
Краткое описание одного из самых распространенных построителей
компиляторов- YACC дополняет эту главу.
Вопросы семантического анализа начинаются с рассмотрения синтаксически
управляемой трансляции. Она изложена в достаточно большом объеме.
Рассказывается об атрибутах, синтаксических деревьях. Материал
содержит описание работы процессоров для восходящего выполнения
S-атрибутных и нисходящего выполнения L-атрибутных определений,
уделено внимание рекурсивным вычислителям атрибутов.
Следующий важный этап контекстного анализа- проверка типов. Этой
проблеме уделена целая глава, в которую вошли такие вопросы
как статическая и динамическая проверка типов, проверка типов выражений,
инструкция, функций, эквивалентность выражений типа, преобразование
типов, полиморфные функции, алгоритм унификации.
Книга содержит полезные советы по непосредственному программированию
компилятора. В ней есть описание структур данных, стратегии выделения
памяти, а также здесь можно найти рекомендации по автоматической
сборке мусора. Небольшой раздел посвящен распределению памяти в Fortran,
на основе которого можно создать свой менеджер памяти.
Огромная часть книги описывает процесс генерации кода. Этот этап
предполагает выбор целевой машины, создание стратегии распределения
памяти и регистров, построение графов потоков. В решении этих а также
многих других вопросов помогает сориентироваться глава "Генерация кода".
Генерация кода и оптимизация тесно связаны. В книге содержатся основные
приемы оптимизации- общие подвыражения, распространение копий, удаление
бесполезного кода, оптимизация циклов, перемещение кода... Материал
содержит введение в глобальный анализ потоков данных, рассматриваются
средства для анализа потоков данных. Приведены даже рекомендации для
построения отладчиков оптимизированного кода.
В главе "Создание компилятора" авторы делятся реальным опытом. Приведены
советы как спланировать компилятор, подходы к разработке компилятора.
Довольно подробно рассматривается такой подход как "раскрутка", при котором
разрабатываемый язык программирования используется как средство для
создания компилятора для самого себя. Таким образом, начиная с простого
варианта, язык, словно снежный ком увеличивается в объеме.
Авторы приводят очень интересный обзор компиляторов, рассказывая о
многих компиляторах "изнутри", глазами создателей. Например глазами
Вирта на Pascal. Также освещены некоторые "тонкие" черты отдельных
компиляторов.
С точки зрения практического применения интересно рассмотреть приложения
книги, в одном из которых приведены реальные грамматики языков С++
и C#. Здесь приводятся спецификации для пакета YACC.
В.Н. Касьянов, И.В. Поттосин
Методы построения трансляторов.
В.Н. Касьянов, И.В. Поттосин
Методы построения трансляторов.
Новосибирск изд. Наука 1986 г.
Эта книга разбита на три большие части. Первая часть дает общее
представление о задачах трансляции. Здесь вводятся термины (синтаксис
языка, лексема, семантика языка, атрибуты, автомат), приводится
классификация Хомского для грамматик, рассматриваются различные виды
трансляторов (конверторы, конкретизаторы, интерпретаторы).
Вторая часть посвящена детальному рассмотрению различных фаз работы
компилятора. Лексическому анализу посвящено недостаточно внимания,
однако все-таки здесь можно прочитать о том, что такое распознаватель,
как он строится, какие функции реализует сканер.
Гораздо больше материала о синтаксическом анализе. В качестве основы
для построения синтаксического анализатора рассматривается автомат с
магазинной памятью. Для нисходящего анализа описан алгоритм разбора
ЛЛ-грамматик. Восходящий анализ представлен анализатором для грамматик
предшествования.
Очень интересный вид разбора- горизонтальный, описан авторами этой
книги. Также приводится алгоритм анализа, для LR-грамматик.
Некоторое внимание авторы уделили вопросу восстановления после ошибок
(режим переполоха, исключение символов, вставка символов, правила для
ошибок).
Следующий большой вопрос, рассмотренный в этой части- контекстный анализ
или семантический. Здесь рассматривается два процесса- идентификации и
атрибутной индукции, что соответствует процессам вычисления L-атрибутов и
S-атрибутов. Такое различие в терминологии часто встречается в этой
книге, как впрочем и во многих других.
Весь остальной материал второй части посвящен вопросам генерации кода,
оптимизации, рассмотрена организация транслятора и приведен пример
транслятора с Минала (мини алгол).
Третья часть рассказывает об автоматизации процесса построения
компилятора. В краткой форме рассмотрены вопросы автоматического
построения синтаксических анализаторов для LL и LR грамматик.
Описываются несколько систем построения трансляторов (СПТ).
Эта книга во многом носит обзорный характер. В ней нет проработанных
алгоритмов, нет четкого описания того или иного метода. Многое опущено,
повсюду встречаются ссылки на более подробное описание того или иного
вопроса. Однако, это дало возможность авторам коснуться многих тем,
которые не часто затрагиваются в других книгах (LL(2) грамматики,
горизонтальный разбор...).
Ф. Льюис, Д. Розенкранц, Р. Стирнз
Теоретические основы проектирования компиляторов.
Ф. Льюис, Д. Розенкранц, Р. Стирнз
Теоретические основы проектирования компиляторов.
М 1979
Авторы этой книги известны первоклассными работами по теории
формальных языков. Их книга построена как учебник для студентов,
обладающих скромными математическими навыками. Весь материал книги
излагается строго, но неформально. Большое внимание в книге уделено
"переводу", а не просто "разбору".
Материал данной книги содержит достаточно полную информацию, необходимую
для построения лексического и синтаксического блоков компилятора.
Применение атрибутной трансляции позволило авторам включить в построение
синтаксического блока значительную часть того, что часто называют
"генерацией кода" или "семантикой". В книга также есть дополнительный
материал по генерации кода и краткий обзор по оптимизации кода.
Книга была написана в 70-х годах, поэтому успела завоевать известность.
В книге достаточно много удачных примеров, которые помогают разобраться
с излагаемым материалом. Достаточно много внимания уделено автоматам и
преобразователям. В книге имеется много "оригинального" материала,
который не рассматривается в других книгах, например S и Q грамматики,
бессуффиксные ПО-грамматики.
Для многих будет интересно подробное рассмотрение метода рекурсивного
спуска (в книге приводится даже описание работы с атрибутами для этого
метода).
Для нашей работы было очень интересно приложение книги, в котором
приводятся много полезных алгоритмов преобразования грамматик.
Эта книга является очень удачной работой в данной области. Она хорошо
и подробно
описывает многие важные понятия и механизмы теории компиляторов
достаточно простым, основанным на примерах языком. Это выделяет
ее из подобных книг, основанных на формализмах. Материал
книги очень хорошо подобран, нет практически ничего лишнего и в тоже
время есть все необходимое.
Дж. Фридл
Регулярные выражения.
Дж. Фридл
Регулярные выражения.
изд-во Питер 2001г.
Очень необходимая книга для любого программиста и даже для простых
пользователей компьютеров. В ней рассказывается о различных применениях
регулярных выражений, которые могут пригодится в повседневной работе
любому человеку, работающему на компьютере.
Регулярные выражения- это очень простой и мощный механизм обработки
текста. Он позволяет производить с ним операции поиска, замены,
проверки на соответствие определенному формату. Являясь очень простым
языком, язык регулярных выражений настолько же мощен и эффективен.
Книга описывает этот язык, причем в различных его реализациях
(в том числе стандарт POSIX). Здесь
можно найти множество примеров их использования и объяснений их
работы. Таким образом человек, прочитавший эту книгу и попробовавший
в действии регулярные выражения точно научится ими пользоваться.
Однако, самая большая ценность книги состоит в описании алгоритмов
обработки регулярных выражений. Эта часть будет интересна программистам.
Здесь можно найти несколько алгоритмов- алгоритм построение и
моделирования ДКА
(детерминированного конечного автомата) и алгоритм построения и
моделирования НКА (недетерминированного конечного автомата).
Для программистов будет представлять интерес даже моделирование работы
НКА, т.к. подобная задача часто встречается и совсем нетривиальна.
Также интересен алгоритм преобразования НКА в ДКА, т.к. подобная задача
также часто встает перед программистами.
Книга содержит много аналитической информации. Приводится сравнение
различных алгоритмов анализа регулярных выражений, различных библиотек и
утилит для работы с ними, в том числе и отличия в их реализациях.
Большое внимание уделено регулярным выражениям в языке Perl. Этот
язык является самым популярным языком для обработки текста на основе
РВ.
Книга окажется полезной для создания лексического анализатора, так как
содержит в себе практически всю информацию для этого. Написание сканера
оказывается лишь "делом техники" после прочтения этой книги.
Грис Д.
Конструирование компиляторов для цифровых вычислительных машин.
Грис Д.
Конструирование компиляторов для цифровых вычислительных машин.
М.: Мир, 1975.
Э.А. Опалева В.П. Самойленко
Проектирование трансляторов компилирующего типа
Э.А. Опалева В.П. Самойленко
Проектирование трансляторов компилирующего типа
Ленинград ЛЭТИ 1981г.
В этом учебном пособии рассказывается об основных методах
синтаксического анализа и синтаксически управляемого перевода.
Оно рассказывает об основных типах формальных грамматик и
синтаксических анализаторах для каждого типа (ЛЛ1 анализатор,
анализаторы типа перенос-свертка для LR0, SLR1 грамматик и
грамматик предшествования).
Целый раздел отведен самым простым синтаксическим анализаторам-
ЛЛ1 анализаторам. ЛЛ1 грамматики могут быть построены для многих
синтаксических конструкций, хотя и существует целый ряд сложностей в
описании языков с помощью ЛЛ1 грамматик. Однако реализация
ЛЛ1 анализатора очень проста и эффективна, что позволяет
ей конкурировать с другими анализаторами в случаях несложных
языков. В пособии этому типа анализатора уделено достаточное
внимания еще и потому, что в учебных целях этот тип анализатора
незаменим- на его основе можно продемонстрировать основные принципы
работы компилятора.
В дополнение к ЛЛ1 анализатору рассматривается L-атрибутный ДМП
процессор, осуществляющий синтаксически управляемый перевод для
ЛЛ1 грамматик.
Вообще, атрибутные транслирующие грамматики занимают важную часть
пособия. Здесь дано определение атрибутной транслирующей грамматики,
рассмотрены два типа таких грамматик- L-атрибутны и S-атрибутные.
ЛЛ1 анализатор представляет собой реализацию нисходящего подхода при
синтаксическом анализе. Восходящий анализ представлен в пособии двумя
основными алгоритмами- алгоритм разбор для LR грамматик и для грамматик
предшествования.
Являясь по сути алгоритмами перенос-свертка, тем не менее, они имеют
достаточно различий. В брошюре приведены оба этих алгоритма с
различными модификациями (для грамматик LR0, SLR1, простого,
слабого и операторного предшествования). Представлены алгоритмы
построения управляющих таблиц для этих анализаторов.
Рассмотрен S-атрибутный ДМП-процессор (детерминированный с магазинной
памятью) для алгоритмов перенос-свертка.
Данное издание будет очень полезно для быстрого изучения основ
проектирования компиляторов. В нем собраны практически все основные
сведения по данному вопросу. Исключение составляет LALR грамматики,
которые очень широко применяются для создания реальных компиляторов.
Однако LALR грамматики очень близки к LR0 и SLR1 грамматикам, поэтому
алгоритм разбора для LALR грамматик принципиально не отличается от
алгоритма разбора для LR0 и SLR1 грамматик. Большим достоинством данного
учебного пособия является краткость и в то же время полнота изложения
материала, в нем есть практически все, что может понадобится для создания
синтаксического анализатора.
Э.А. Опалева В.П. Самойленко
Формальные грамматики и распознающие автоматы
Э.А. Опалева В.П. Самойленко
Формальные грамматики и распознающие автоматы
Ленинград ЛЭТИ 1991г.
Это небольшое учебное пособие содержит основные сведения о формальных
грамматиках. Приводится математическое определение формальной грамматики,
языка, конечного автомата, преобразователя,
описываются классы ФГ,
строго описываются алгоритмы преобразования ФГ. Рассматриваются вопросы
однозначности ФГ.
Пособие адресовано людям имеющим небольшое представление о предметной
области и
может быть использовано как небольшой справочник по основным понятиям
теории компиляторов. Ценность пособия заключается в краткости и
математической точности описания.
В нем достаточно много внимания уделяется алгоритмам преобразования
грамматик (приведены достаточно подробные описания
всех основных алгоритмов), преобразователям и автоматам с
магазинной памятью (которые используются при построении компиляторов),
рассмотрены вопросы связанные с детерминированностью конечных
автоматов и преобразованием недетерминированных автоматов в
детерминированные.
В.А.Серебряков
Лекции по конструированию компиляторов
В.А.Серебряков
Лекции по конструированию компиляторов
Москва 1993
Книга основана на курсе лекций,
прочитанных на факультете вычислительной математики и
кибернетики Московского государственного университета в 1991-
1993 гг.
Содержание книги представляет собой "классические" разделы
предмета: лексический и синтаксический анализ, организация
памяти, генерация кода. Сделана попытка на протяжении всего
изложения провести единую "атрибутную" точку зрения на процесс
разработки компилятора.
Эту книгу очень часто можно встретить в интернете, благодаря своей
популярности, доступности и полноте изложения. В ней рассмотрены
основные этапы разработки компиляторов в краткой и понятной форме.
Книга достаточно современна, что придает ей еще больше ценности.
Лексический анализ представлен в книге с точки зрения регулярных
выражений. Приведен алгоритм разбора регулярных выражений (с помощью
построения конечного автомата), также описывается утилита Lex-
построитель сканеров (лексических анализаторов).
Глава посвященная синтаксическому анализу содержит описания алгоритмов
разбора для LL(1) грамматик и LR(k) грамматик. Изложен материал,
касающийся восстановлению после ошибок. Приведены алгоритмы устранения
левой рекурсии для приведения грамматики к классу LL(1).
Очень ценным является материал о промежуточном представлении программы.
Рассмотрены несколько способов представления- в виде ориентированного
графа, трехадресного кода, лениаризованные представления.
Волкова И.А., Руденко Т.В.
Формальные грамматики и языки. Элементы теории трансляции.
Волкова И.А., Руденко Т.В.
Формальные грамматики и языки. Элементы теории трансляции.
Издательство механико-математического факультета МГУ им. М.В.Ломоносова, 1996
Это учебное пособие интересно тем, что представляет собой практическое
руководство для построения простейшего компилятора. Здесь достаточно
материала по теории формальных языков и грамматик: даны основные понятия
и определения, описаны некоторые алгоритмы преобразования грамматик,
приведена классификация грамматик и языков по Хомскому.
Рассмотрены элементы теории трансляции на примере модельного языка
являющегося подмножеством языка Pascal. Почти все основные алгоритмы
приведенные в качестве примеров написаны на С.
Первым шагом на пути построения компилятора является лексический анализ
представленный в пособии конечным автоматом. Подробно описаны шаги и
способы его построения, а также приведена
короткая программа моделирования его
работы. Некоторое внимание уделено недетерминированным автоматам.
Для анализа синтаксиса приведен алгоритм рекурсивного спуска с
возможностью проверки семантики. Приведена программа для этого метода,
а также дано описание генерации представления программы.
Несмотря на отсутствие "серьезных" алгоритмов синтаксического анализа
(к которым принято относить методы основанные на автоматах и
преобразователях) пособие дает хороший урок проектирования парсеров,
т.к. на сегодняшний день многие парсеры, созданные для специальных нужд
используют именно метод рекурсивного спуска. Этот метод не требует
специальных, особых знаний и понятен большинству программистов.
Очень неплохо изложена теория формальных грамматик, однако не хватает
описания классов ЛЛ(k), LR(k) грамматик.
Несмотря на большое количество книг по данной тематике следует отметить
тот факт, что хорошо и полно проработан практически только вопрос
синтаксического анализа. Для него существует множество алгоритмов и
методов. Есть специальные средства, автоматизирующие этот процесс.
Немного хуже дела обстоят с лексическим анализом. Везде говорится, что
для этого необходимо использовать автоматы, но как их строить и
моделировать их работу описано не везде. К тому же очень неудачно, на
мой взгляд, описывается алгоритм преобразования недетерминированного
конечного автомата в детерминированный. Крайне мало и поверхностно
говорится об использовании регулярных выражений в лексическом анализе.
Исключение представляет книга Фридла, однако она не касается задачи
лексического анализа. Очень неплохо эта тема изложена в работе
Серебрякова.
Семантический анализ на сегодня является самой сложной и наформализуемой
фазой построения компилятора. Эта часть требует проявления большого
искусства от разработчиков. Попытка использовать для этого
атрибутные грамматики не решает проблему полностью, хотя и сильно ее
облегчает. Практически все авторы пишут о необходимости использовать
атрибуты, однако в том как их использовать, они не находят
взаимопонимания. Я бы посоветовал в этом вопросе обратится к "книге
дракона" Ахо, Сети и Ульмана. В ней можно найти множество практических
рекомендаций и пояснений.
Очень неполно и поверхностно рассматриваются вопросы разработки грамматик
для языков, а ведь это очень важная часть в разработке компилятора.
Ошибка на данной стадии может повлечь за собой очень много проблем
впоследствии, т.к. этот этап является одним из первых. Очень непросто
разработать формальную грамматику для языка, привести ее к реализуемому
(с помощью одного из методов синтаксического анализа) виду. Тем более
нет никаких средств для автоматизации этого процесса. Например
популярный пакет YACC требует на вход уже разработанную грамматику.
Лишь немногие алгоритмы приведены в литературе по преобразованию
грамматик, но практически нет рекомендаций по их приведению к
конкретному классу.
|