Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Креншоу Д. Пишем компилятор - файл 1.doc


Креншоу Д. Пишем компилятор
скачать (1604 kb.)

Доступные файлы (1):

1.doc1604kb.13.12.2011 22:49скачать

содержание
Загрузка...

1.doc

  1   2   3   4   5   6   7   8   9   ...   59
Реклама MarketGid:
Загрузка...
Лекции по построению компилятора на Pascal

Автор неизвестен

Оглавление

1. Введение 5

ВВЕДЕНИЕ 5

ОСНОВА 7

2. Синтаксический анализ выражений 10

     НАЧАЛО 10

ОДИНОЧНЫЕ ЦИФРЫ 10

ВЫРАЖЕНИЯ С ДВУМЯ ЦИФРАМИ 11

ОБЩАЯ ФОРМА ВЫРАЖЕНИЯ 13

ИСПОЛЬЗОВАНИЕ СТЕКА 13

УМНОЖЕНИЕ И ДЕЛЕНИЕ 14

КРУГЛЫЕ СКОБКИ 15

УНАРНЫЙ МИНУС 16

СЛОВО ОБ ОПТИМИЗАЦИИ 17

3. Снова выражения 19

ВВЕДЕНИЕ 19

ПЕРЕМЕННЫЕ 19

ФУНКЦИИ 20

ПОДРОБНЕЕ ОБ ОБРАБОТКЕ ОШИБОК 21

ПРИСВАИВАНИЕ 22

МНОГОСИМВОЛЬНЫЕ ТОКЕНЫ. 23

ПРОБЕЛЫ 24

4. Интерпретаторы 30

ВВЕДЕНИЕ 30

ИНТЕРПРЕТАТОР 31

НЕМНОГО ФИЛОСОФИИ 34

5. Управляющие конструкции 39

ВВЕДЕНИЕ 39

ПЛАН 39

НЕМНОГО ОСНОВ 40

ОПЕРАТОР IF 42

ОПЕРАТОР WHILE 44

ОПЕРАТОР LOOP 45

REPEAT-UNTIL 46

ЦИКЛ FOR 47

ОПЕРАТОР DO 49

ОПЕРАТОР BREAK 49

ЗАКЛЮЧЕНИЕ 52

6. Булевы выражения 57

ВВЕДЕНИЕ 57

ПЛАН 57

ГРАММАТИКА 57

ОПЕРАТОРЫ ОТНОШЕНИЙ 58

ИСПРАВЛЕНИЕ ГРАММАТИКИ 59

СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР 61

ОБЪЕДИНЕНИЕ С УПРАВЛЯЮЩИМИ КОНСТРУКЦИЯМИ 68

ДОБАВЛЕНИЕ ПРИСВАИВАНИЙ 68

7. Лексический анализ 71

ВВЕДЕНИЕ 71

ЛЕКСИЧЕСКИЙ АНАЛИЗ 71

КОНЕЧНЫЕ АВТОМАТЫ И АЛЬТЕРНАТИВЫ 73

ЭКСПЕРИМЕНТЫ ПО СКАНИРОВАНИЮ 73

ПРОБЕЛ 74

КОНЕЧНЫЕ АВТОМАТЫ 75

НОВЫЕ СТРОКИ 76

ОПЕРАТОРЫ 77

СПИСКИ, ЗАПЯТЫЕ И КОМАНДНЫЕ СТРОКИ. 78

СТАНОВИТСЯ ИНТЕРЕСНЕЙ 79

ВОЗВРАЩЕНИЕ СИМВОЛА 83

РАСПРЕДЕЛЕННЫЕ СКАНЕРЫ ПРОТИВ ЦЕНТРАЛИЗОВАННЫХ 85

ОБЪЕДИНЕНИЕ СКАНЕРА И ПАРСЕРА 85

   Пара комментариев: 91

ЗАКЛЮЧЕНИЕ 97

8. Немного философии 99

ВВЕДЕНИЕ 99

ДОРОГА ДОМОЙ 99

ПОЧЕМУ ЭТО ТАК ПРОСТО? 100

ЗДЕСЬ НЕТ НИЧЕГО СЛОЖНОГО! 101

ЗАКЛЮЧЕНИЕ 105

9. Вид сверху 106

ВВЕДЕНИЕ 106

ВЕРХНИЙ УРОВЕНЬ 106

СТРУКТУРА ПАСКАЛЯ 107

РАСШИРЕНИЕ 108

ОБЪЯВЛЕНИЯ 109

СТРУКТУРА   СИ 111

10. Представление "TINY" 116

ВВЕДЕНИЕ 116

ПОДГОТОВКА 116

ОБЪЯВЛЕНИЯ 119

ОБЪЯВЛЕНИЯ И ИДЕНТИФИКАТОРЫ 120

ИНИЦИАЛИЗАТОРЫ 121

ТАБЛИЦА ИДЕНТИФИКАТОРОВ 123

ВЫПОЛНИМЫЕ УТВЕРЖДЕНИЯ 123

БУЛЕВА ЛОГИКА 128

УПРАВЛЯЮЩИЕ СТРУКТУРЫ 132

ЛЕКСИЧЕСКИЙ АНАЛИЗ 134

МНОГОСИМВОЛЬНЫЕ ИМЕНА ПЕРЕМЕННЫХ 138

СНОВА ОПЕРАТОРЫ ОТНОШЕНИЙ 140

ВВОД/ВЫВОД 141

ЗАКЛЮЧЕНИЕ 143

11. Пересмотр лексического анализа 159

ВВЕДЕНИЕ 159

ПРЕДПОСЫЛКА 159

ПРОБЛЕМА 160

РЕШЕНИЕ 161

ИСПРАВЛЕНИЕ КОМПИЛЯТОРА 164

ЗАКЛЮЧЕНИЕ 166

TINY VERSION 1.1 166

12. Разное 179

ВВЕДЕНИЕ 179

ТОЧКИ С ЗАПЯТОЙ 179

СИНТАКСИЧЕСКИЙ САХАР 180

РАБОТА С ТОЧКАМИ С ЗАПЯТОЙ 181

КОМПРОМИСС 184

КОММЕНТАРИИ 184

ОДНОСИМВОЛЬНЫЕ РАЗДЕЛИТЕЛИ 184

МНОГОСИМВОЛЬНЫЕ РАЗДЕЛИТЕЛИ 186

ОДНОСТОРОННИЕ КОММЕНТАРИИ 187

ЗАКЛЮЧЕНИЕ 188

13. Процедуры 189

ВВЕДЕНИЕ 189

ПОСЛЕДНЕЕ ОТКЛОНЕНИЕ 189

ОСНОВЫ 190

ОСНОВА ДЛЯ ЭКСПЕРИМЕНТОВ 190

ОБЪЯВЛЕНИЕ ПРОЦЕДУРЫ 195

ВЫЗОВ ПРОЦЕДУРЫ 199

ПЕРЕДАЧА ПАРАМЕТРОВ 200

СЕМАНТИКА ПАРАМЕТРОВ 202

ПЕРЕДАЧА ПО ЗНАЧЕНИЮ 205

ЧТО НЕПРАВИЛЬНО? 209

ПЕРЕДАЧА ПО ССЫЛКЕ 212

ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ 214

ЗАКЛЮЧЕНИЕ 217

14. Типы 218

ВВЕДЕНИЕ 218

ЧТО БУДЕТ ДАЛЬШЕ? 218

ТАБЛИЦА ИДЕНТИФИКАТОРОВ 219

ДОБАВЛЕНИЕ ЗАПИСЕЙ 223

РАСПРЕДЕЛЕНИЕ ПАМЯТИ 224

ОБЪЯВЛЕНИЕ ТИПОВ 225

ПРИСВАИВАНИЯ 226

ТРУСЛИВЫЙ ВЫХОД 229

БОЛЕЕ ПРИЕМЛЕМОЕ РЕШЕНИЕ 230

ЛИТЕРАЛЬНЫЕ АРГУМЕНТЫ 232

АДДИТИВНЫЕ ВЫРАЖЕНИЯ 233

ПОЧЕМУ ТАК МНОГО ПРОЦЕДУР? 236

МУЛЬТИПЛИКАТИВНЫЕ ВЫРАЖЕНИЯ 237

УМНОЖЕНИЕ 237

ДЕЛЕНИЕ 239

ЗАВЕРШЕНИЕ 241

ПРИВОДИТЬ ИЛИ НЕ ПРИВОДИТЬ 242

ЗАКЛЮЧЕНИЕ 244

15. Назад в будущее 245

    ВВЕДЕНИЕ 245

НОВОЕ НАЧАЛО, СТАРОЕ НАПРАВЛЕНИЕ 245

НАЧИНАЕМ ЗАНОВО? 247

МОДУЛЬ INPUT 247

МОДУЛЬ OUTPUT 249

МОДУЛЬ ERROR 250

ЛЕКСИЧЕСКИЙ И СИНТАКСИЧЕСКИЙ АНАЛИЗ 251

МОДУЛЬ SCANNER 253

РЕШЕНИЯ, РЕШЕНИЯ 255

СИНТАКСИЧЕСКИЙ АНАЛИЗ 256

    ССЫЛКИ 259

16. Конструирование модулей 260

    ВВЕДЕНИЕ 260

СОВСЕМ КАК КЛАССИЧЕСКИЙ? 261

РАСШИРЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА 263

ТЕРМЫ И ВЫРАЖЕНИЯ 265

ПРИСВАИВАНИЯ 268

БУЛЕВА АЛГЕБРА 268
^

1. Введение

ВВЕДЕНИЕ


Эта серия статей является руководством по теории и практике разработки синтаксических анализаторов и компиляторов языков программирования. Прежде чем вы закончите чтение этой книги, мы раскроем все аспекты конструирования компиляторов, создадим новый язык программирования, и построим работающий компилятор.

Хотя я по образованию и не специалист в компьютерах, я интересовался компиляторами в течение многих лет. Я покупал и старался разобраться с содержимым практически каждой выпущенной на эту тему книги. И, должен признаться, это был долгий путь. Эти книги написаны для специалистов в компьютерной науке и  слишком трудны для понимания большинству из нас. Но с течением лет часть из прочитанного начала доходить до меня. Закрепить полученное позволило то, что я начал самостоятельно пробовать это на своем собственном компьютере. Сейчас я хочу поделиться с вами своими знаниями. После прочтения этой книги вы не станете ни специалистом, ни узнаете всех секретов теории конструирования компиляторов. Я намеренно полностью игнорирую большинство теоретических аспектов этой темы. Вы изучите только практические аспекты, необходимые для создания работающей системы.

В течение всей книги я буду проводить эксперименты на компьютере, а вы будете повторять их за мной и ставить свои собственные эксперименты. Я буду использовать Turbo Pascal 4.0 и периодически буду включать примеры, написанные в TP. Эти примеры вы будете копировать себе в компьютер и выполнять. Если у вас не установлен Turbo Pascal вам будет трудно следить за ходом обучения, поэтому я настоятельно рекомендую его поставить. Кроме того, это просто замечательный продукт и для множества других задач!

Некоторые тексты программ будут показаны как примеры или как законченные продукты, которые вы можете копировать без необходимости понимания принципов их работы. Но я надеюсь сделать гораздо больше: я хочу научить вас КАК это делается, чтобы вы могли делать это самостоятельно, и не только повторять то, что я делаю, но и улучшать.

Такую задачу не решить на одной странице. Я попытаюсь сделать это в нескольких статьях. Каждая статья раскрывает один аспект теории создания компиляторов и может быть изучена в отдельности от всех других. Если вас в настоящее время интересует только какой-то определенный аспект, тогда вы можете обратиться к нужной статье. Каждая статья будет появляться по мере завершения, так что вы должны дождаться последней для того, чтобы считать себя закончившими обучение. Пожалуйста, будьте терпеливы.

В общем, каждая книга по теории создания компиляторов раскрывает множество основ, которые мы не будем рассматривать. Типичная последовательность:

  • вступление, в котором описывается что такое компилятор.

  • одна или две главы, описывающие задание синтаксиса с использованием формы Бэкуса-Наура (БНФ).

  • одна или две главы с описанием лексического анализа, с акцентом на детерминированных и недетерминированных конечных автоматах.

  • несколько глав по теории синтаксического анализа, начиная с рекурсивного спуска и заканчивая LALR анализаторами.

  • глава, посвященная промежуточным языкам, с акцентом на P-код и обратную польскую запись.

  • множество глав об альтернативных путях для поддержки подпрограмм и передачи параметров, описания типов, и т.д.

  • завершающая глава по генерации кода, обычно для какого-нибудь воображаемого процессора с простым набором команд.

  • финальная глава или две, посвященные оптимизации. Эта глава часто остается непрочитанной, очень часто.

В этой серии я буду использовать совсем другой подход. Для начала, я не остановлюсь долго на выборе. Я покажу вам путь, который работает. Если же вы хотите изучить возможности, хорошо… я поддержу вас... но я буду держаться того, что я знаю. Я также пропущу большинство тех теорий, которые заставляют людей засыпать. Не поймите меня неправильно: я не преуменьшаю важность теоретических знаний, они жизненно необходимы, когда приходится иметь дело с более сложными элементами какого либо языка. Но необходимо более важные вещи ставить на первое место. Мы же будем иметь дело с методами, 95% которых не требуют много теории для работы.

Я также буду рассматривать только один метод синтаксического анализа: рекурсивный спуск, который является единственным полностью пригодным методом при ручном написании компилятора. Другие методы полезны только в том случае, если у вас есть инструменты типа Yacc, и вам совсем неважно, сколько памяти будет использовать готовый продукт.

Я также возьму страницу из работы Рона Кейна, автора Small C. Поскольку почти все другие авторы компиляторов исторически использовали промежуточный язык подобно P-коду и разделяли компилятор на две части («front end», который производит P-код, и «back end», который обрабатывает P-код, для получения выполняемого объектного кода), Рон показал нам, что очень просто заставить компилятор непосредственно производить выполняемый объектный код в форме языковых утверждений ассемблера. Такой код не самый компактный в мире код... генерация оптимизированного кода - гораздо более трудная работа. Но этот метод работает и работает достаточно хорошо. И чтобы не оставить вас с мыслью, что наш конечный продукт не будет представлять никакой ценности, я собираюсь показать вам как создать компилятор с небольшой оптимизацией.

Наконец, я собираюсь использовать некоторые приемы, которые мне показались наиболее полезными для того, чтобы понимать, что происходит, не продираясь сквозь дремучий лес. Основным из них является использование одно-символьных токенов, не содержащих пробелов, на ранней стадии разработки. Я считаю, что если я могу создать синтаксический анализатор для распознавания и обработки I-T-L, то я смогу сделать тоже и с IF-THEN-ELSE. На втором уроке я покажу вам, как легко расширить простой синтаксический анализатор для поддержки токенов произвольной длины. Следующий прием состоит в том, что я полностью игнорирую файловый ввод/вывод, показывая этим, что если я могу считывать данные с клавиатуры и выводить результат на экран я могу также делать это и с файлами на диске. Опыт показывает, что как только транслятор заработает правильно очень просто перенаправить ввод/вывод на файлы. Последний прием заключается в том, что я не пытаюсь выполнять коррекцию/восстановление после ошибок. Программа, которую мы будем создавать, будет распознавать ошибки и просто остановится на первой из них, точно также как это происходит в Turbo Pascal. Будут и некоторые другие приемы, которые вы увидите по ходу дела. Большинство из них вы не найдете в каком либо учебнике по компиляторам, но они работают.

Несколько слов о стиле программирования и эффективности. Как вы увидите, я стараюсь писать программы в виде маленьких, легко понятных фрагментов. Ни одна из процедур, с которыми мы будем работать, не будет состоять более чем из 15-20 строк. Я горячий приверженец принципа KISS (Keep It Simple, Sidney – Делай это проще, Сидней) в программировании. Я никогда не пытаюсь сделать что-либо сложное, когда можно сделать просто. Неэффективно? Возможно, но вам понравится результат. Как сказал Брайан Керниган, сначала заставьте программу работать, затем заставьте программу работать быстро. Если позднее вы захотите вернуться и подправить что-либо в вашем продукте, вы сможете сделать это т.к. код будет совершенно понятным. Если вы поступаете так, я, тем не менее, убеждаю вас подождать пока программа не будет выполнять все, что вы от нее хотите.

Я также имею тенденцию не торопиться с созданием модулей до тех пор, пока не обнаружу, что они действительно нужны мне. Попытка предусмотреть все необходимое в будущем может свести вас с ума. В наши время, время экранных редакторов и быстрых компиляторов  я буду менять модули тогда, когда почувствую необходимость в более мощном. До тех пор я буду писать только то, что мне нужно.

Заключительный аспект: Один из принципов, который мы будем применять здесь, заключается в том, что мы не будем никого вводить в заблуждение с P-кодом или воображаемыми ЦПУ, но мы начнем с получения работающего, выполнимого объектного кода, по крайней мере, в виде программы на ассемблере. Тем не менее, вам может не понравиться выбранный мной ассемблер… это – ассемблер для микропроцессора 68000, используемый в моей системе (под SK*DOS). Я думаю, что вы найдете, тем не менее, что трансляция для любого другого ЦПУ, например 80x86, совершенно очевидна, так что я не вижу здесь проблемы. Фактически, я надеюсь что кто-то, кто знает язык 8086 лучше, чем я, предоставит нам эквивалент объектного кода.
  1   2   3   4   5   6   7   8   9   ...   59



Скачать файл (1604 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru