Главная страница
Навигация по странице:

  • ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ РЕАЛИЗАЦИЯ

  • Язык и его реализация

  • Компилятор, интерпретатор, конвертор

  • Свердлов 2015 Конструирование компиляторов. Свердлов 2015 Конструирование компиляторов Учебное пособие Есть. Задача разбора


    Скачать 5.16 Mb.
    НазваниеЗадача разбора
    АнкорСвердлов 2015 Конструирование компиляторов
    Дата28.07.2022
    Размер5.16 Mb.
    Формат файлаpdf
    Имя файлаСвердлов 2015 Конструирование компиляторов Учебное пособие Есть .pdf
    ТипЗадача
    #637411
    страница1 из 41

    С этим файлом связано 1 файл(ов). Среди них: Беременность и БА.docx.
    Показать все связанные файлы
    Подборка по базе: Doulci Activator Software Download - 2015.docx, 5 задача.docx, Реферат борьба с пожарами как задача ГО.doc, Менеджемнт 3 задача.docx, 1 задача техмех.docx, Самостоятельная задача.docx, Дисконтирование денежного потока Задача.docx, БЖД задача 44.docx, презентация по задачам генетика.pdf, Геот задача3,4.docx
      1   2   3   4   5   6   7   8   9   ...   41





    ОГЛАВЛЕНИЕ
    ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ
    РЕАЛИЗАЦИЯ ................................................................................... 9
    Язык и его реализация ................................................................. 9
    Компилятор, интерпретатор, конвертор ................................... 9
    Метаязыки .................................................................................. 16
    ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ ........ 17
    Ф
    ОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ
    ........................................... 17
    Основные термины и определения .......................................... 17
    Примеры языков ........................................................................ 20
    Порождающие грамматики (грамматики Н. Хомского) ........ 22
    Еще несколько определений ..................................................... 27
    Дерево вывода ............................................................................ 29
    Задача разбора ............................................................................ 31
    Для чего надо решать задачу разбора ...................................... 32
    Домино Де Ремера ..................................................................... 33
    Разновидности алгоритмов разбора ......................................... 34
    Эквивалентность и однозначность грамматик ....................... 35
    Иерархия грамматик Н. Хомского ........................................... 38
    А
    ВТОМАТНЫЕ ГРАММАТИКИ И ЯЗЫКИ
    ........................................... 43
    Граф автоматной грамматики................................................... 43
    Конечные автоматы ................................................................... 45
    Преобразование недетерминированного конечного автомата
    (НКА) в детерминированный конечный автомат (ДКА) ....... 47

    2
    Таблица переходов детерминированного конечного автомата
    ..................................................................................................... 50
    Программная реализация автоматного распознавателя ........ 51
    Дерево разбора в автоматной грамматике .............................. 52
    Пример автоматного языка ....................................................... 53
    Синтаксические диаграммы автоматного языка .................... 57
    Регулярные выражения и регулярные множества ................. 60
    Эквивалентность регулярных выражений и автоматных грамматик ................................................................................... 62
    Для чего нужны регулярные выражения ................................ 63
    Регулярные выражения как языки ........................................... 64
    Расширенная нотация для регулярных выражений ............... 65
    К
    ОНТЕКСТНО
    -
    СВОБОДНЫЕ
    (КС)
    ГРАММАТИКИ И ЯЗЫКИ
    ............... 66
    Однозначность КС-грамматики ............................................... 66
    Алгоритмы распознавания КС-языков .................................... 68
    Распознающий автомат для КС-языков .................................. 69
    Самовложение в КС-грамматиках ........................................... 69
    Синтаксические диаграммы КС-языков .................................. 70
    Определение языка с помощью синтаксических диаграмм .. 73
    Синтаксический анализ КС-языков методом рекурсивного спуска .......................................................................................... 77
    Требование детерминированного распознавания .................. 87
    LL- грамматики ........................................................................... 88
    Левая и правая рекурсия ........................................................... 89
    Синтаксический анализ арифметических выражений ........... 89
    Включение действий в синтаксис ............................................ 97

    3
    Обработка ошибок при трансляции ....................................... 109
    Табличный LL(1)-анализатор ................................................. 113
    Рекурсивный спуск и табличный анализатор ....................... 128
    Т
    РАНСЛЯЦИЯ ВЫРАЖЕНИЙ
    ........................................................... 130
    Польская запись ....................................................................... 130
    Алгоритм вычисления выражений в обратной польской записи ........................................................................................ 132
    Перевод выражений в обратную польскую запись .............. 135
    Интерпретация выражений ..................................................... 137
    Семантическое дерево выражения ......................................... 139
    Упражнения для самостоятельной работы ........................... 152
    ГЛАВА 3. ТРАНСЛЯЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
    ......................................................................................................... 160
    О
    ПИСАНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
    .................................. 160
    Метаязыки ................................................................................ 161
    БНФ ........................................................................................... 161
    Синтаксические диаграммы ................................................... 162
    Расширенная форма Бэкуса-Наура (РБНФ) .......................... 162
    Описания синтаксиса языков семейства Си ......................... 164
    Описания синтаксиса языка Ада ............................................ 165
    Я
    ЗЫК ПРОГРАММИРОВАНИЯ
    «О» ................................................. 166
    Краткая характеристика языка «О» ....................................... 167
    Синтаксис «О» ......................................................................... 168
    Пример программы на «О» ..................................................... 170
    С
    ТРУКТУРА КОМПИЛЯТОРА
    .......................................................... 171

    4
    Многопроходные и однопроходные трансляторы ............... 173
    К
    ОМПИЛЯТОР ЯЗЫКА
    «О» ............................................................ 176
    Вспомогательные модули компилятора ................................ 178
    Л
    ЕКСИЧЕСКИЙ АНАЛИЗАТОР
    (
    СКАНЕР
    ) ......................................... 181
    Виды и значения лексем ......................................................... 183
    Лексический анализатор языка «О» ...................................... 184
    С
    ИНТАКСИЧЕСКИЙ АНАЛИЗАТОР
    .................................................. 204
    К
    ОНТЕКСТНЫЙ АНАЛИЗ
    ................................................................ 209
    Таблица имен ........................................................................... 209
    Контекстный анализ модуля ................................................... 220
    Трансляция списка импорта ................................................... 223
    Трансляция описаний .............................................................. 225
    Контекстный анализ выражений ............................................ 229
    Контекстный анализ операторов ............................................ 233
    Г
    ЕНЕРАЦИЯ КОДА
    .......................................................................... 236
    Виртуальная машина ............................................................... 236
    Архитектура виртуальной машины ....................................... 238
    Программирование в коде виртуальной машины ................ 246
    Реализация виртуальной машины .......................................... 252
    Генератор кода ......................................................................... 258
    Распределение памяти ............................................................. 260
    Генерация кода для выражений ............................................. 263
    Генерация кода для операторов ............................................. 277
    Завершение генерации ............................................................ 288
    Назначение адресов переменным .......................................... 289

    5
    Т
    РАНСЛЯЦИЯ ПРОЦЕДУР
    ............................................................... 293
    Расширенный набор команд виртуальной машины ............. 293
    Процедуры без параметров и локальных переменных ........ 294
    Процедуры с параметрами-значениями без локальных переменных .............................................................................. 297
    Процедуры с параметрами-значениями и локальными переменными ............................................................................ 302
    Простейшая оптимизация кода .............................................. 304
    Процедуры-функции с параметрами-значениями и локальными переменными...................................................... 305
    Трансляция оператора RETURN ............................................ 308
    Особенность трансляции параметров-переменных ............. 308
    Пример программы на языке «О с процедурами» ............... 310
    К
    ОНСТРУКЦИЯ ПРОСТОГО АССЕМБЛЕРА
    ....................................... 314
    Язык ассемблера виртуальной машины ................................ 315
    Реализация ассемблера ............................................................ 321
    А
    ВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ И МОБИЛЬНОСТЬ ТРАНСЛЯТОРОВ
    ...................................................................................................... 330
    Автоматический анализ и преобразование грамматик ........ 331
    Автоматическое построение компилятора и его частей...... 332
    Использование языков высокого уровня .............................. 339
    Самокомпилятор. Раскрутка ................................................... 343
    Примеры раскрутки ................................................................. 349
    Унификация промежуточного представления ...................... 350
    ПРИЛОЖЕНИЕ 1. ЯЗЫК ПРОГРАММИРОВАНИЯ ОБЕРОН-2
    ......................................................................................................... 357

    6
    О
    Т ПЕРЕВОДЧИКА
    ......................................................................... 357 1.
    В
    ВЕДЕНИЕ
    ................................................................................. 361 2.
    С
    ИНТАКСИС
    .............................................................................. 362 3.
    С
    ЛОВАРЬ И ПРЕДСТАВЛЕНИЕ
    .................................................... 362 4.
    О
    БЪЯВЛЕНИЯ И ОБЛАСТИ ДЕЙСТВИЯ
    ........................................ 365 5.
    О
    БЪЯВЛЕНИЯ КОНСТАНТ
    ........................................................... 367 6.
    О
    БЪЯВЛЕНИЯ ТИПОВ
    ................................................................. 367 6.1 Основные типы .................................................................. 368 6.2 Тип массив .......................................................................... 368 6.
    3 Тип запись .......................................................................... 369 6.4 Тип указатель ..................................................................... 370 6.5 Процедурные типы ............................................................ 371 7.
    О
    БЪЯВЛЕНИЯ ПЕРЕМЕННЫХ
    ...................................................... 371 8.
    В
    ЫРАЖЕНИЯ
    .............................................................................. 372 8.1 Операнды ............................................................................ 372 8.2 Операции ............................................................................ 374 9.
    О
    ПЕРАТОРЫ
    ............................................................................... 378 9.1 Присваивания ..................................................................... 378 9.2 Вызовы процедур ............................................................... 379 9.3 Последовательность операторов ...................................... 380 9.4 Операторы IF ...................................................................... 380 9.5 Операторы CASE ............................................................... 381 9.6 Операторы WHILE ............................................................ 382 9.7 Операторы REPEAT .......................................................... 383 9.8 Операторы FOR ................................................................. 383

    7 9.9 Операторы LOOP ............................................................... 384 9.10 Операторы возврата и выхода ........................................ 384 9
    .11 Операторы WITH ............................................................. 385 10.
    О
    БЪЯВЛЕНИЯ ПРОЦЕДУР
    ......................................................... 385 10.1 Формальные параметры .................................................. 387 10.2 Процедуры, связанные с типом ...................................... 389 10.3 Стандартные процедуры ................................................. 390 11.
    М
    ОДУЛИ
    .................................................................................. 394
    П
    РИЛОЖЕНИЕ
    A:
    О
    ПРЕДЕЛЕНИЕ ТЕРМИНОВ
    ................................ 396
    Целые типы .............................................................................. 396
    Вещественные типы ................................................................ 396
    Числовые типы ......................................................................... 396
    Одинаковые типы .................................................................... 396
    Равные типы ............................................................................. 396
    Поглощение типов ................................................................... 397
    Расширение типов (базовый тип) ........................................... 397
    Совместимость по присваиванию .......................................... 397
    Совместимость массивов ........................................................ 398
    Совместимость выражений .................................................... 398
    Совпадение списков формальных параметров ..................... 399
    П
    РИЛОЖЕНИЕ
    B:
    С
    ИНТАКСИС
    О
    БЕРОНА
    -2 ................................... 400
    П
    РИЛОЖЕНИЕ
    C:
    М
    ОДУЛЬ
    SYSTEM ........................................... 403
    П
    РИЛОЖЕНИЕ
    D:
    С
    РЕДА
    О
    БЕРОН
    ................................................. 405
    D1. Команды ............................................................................. 406
    D2. Динамическая загрузка модулей ..................................... 407

    8
    D3. Сбор мусора ....................................................................... 408
    D4. Смотритель ........................................................................ 408
    D5. Структуры данных времени выполнения ....................... 409
    ПРИЛОЖЕНИЕ 2. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА
    ПАСКАЛЕ ...................................................................................... 411
    ПРИЛОЖЕНИЕ 3. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА
    ОБЕРОНЕ ....................................................................................... 443
    О
    ТЛИЧИЯ ВЕРСИЙ ДЛЯ КОМПИЛЯТОРОВ
    JOB
    И
    XDS ................... 443
    И
    ЗМЕНЕНИЕ ОБОЗНАЧЕНИЙ
    .......................................................... 444
    И
    ЗМЕНЕНИЯ В СТРУКТУРЕ КОМПИЛЯТОРА
    ................................... 444
    ПРИЛОЖЕНИЕ 4. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА
    СИ/СИ++ ........................................................................................ 480
    ПРИЛОЖЕНИЕ 5. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ
    ПРОГРАММИРОВАНИЯ ЯВА ................................................... 511
    ПРИЛОЖЕНИЕ 6. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ
    ПРОГРАММИРОВАНИЯ СИ# .................................................... 540
    ЛИТЕРАТУРА ............................................................................... 568

    9
    ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ
    РЕАЛИЗАЦИЯ
    С начала 50-х годов XX века создаются и развиваются языки программирования. Чтобы язык программирования можно было реально применять — писать программы на этом языке и испол- нять их на компьютере, язык должен быть реализован.
    Язык и его реализация
    Реализацией языка программирования называют создание ком- плекса программ, обеспечивающих работу на этом языке. Такой набор программ называется системой программирования.
    Основу каждой системы программирования составляет транс-
    лятор. Это программа, переводящая текст на языке программи- рования в форму, пригодную для исполнения (на другой язык).
    Такой формой обычно являются машинные команды, которые могут непосредственно исполняться компьютером. Совокуп- ность машинных команд данного компьютера (процессора) об- разует его систему команд или машинный язык. Программу, ко- торую обрабатывает транслятор, называют исходной програм-
    мой, а язык, на котором записывается исходная программа —
    входным языком этого транслятора.
    Компилятор, интерпретатор, конвертор
    Различают несколько видов трансляторов: компиляторы, интер- претаторы, конверторы (рис. 1.1).
    Компилятор, обрабатывая исходную программу, создает экви- валентную программу на машинном языке, которая называется также объектной программой или объектным кодом. Объект- ный код, как правило, записывается в файл, но не обязательно представляет собой готовую к исполнению программу. Для про- грамм, состоящих из многих модулей, может образовываться много объектных файлов. Объектные файлы объединяются в ис-

    10 полняемый модуль с помощью специальной программы-
    компоновщика, которая входит в состав системы программиро- вания. Возможен также вариант, когда модули не объединяются заранее в единую программу, а загружаются в память при вы- полнении программы по мере необходимости.
    Интерпретатор, распознавая, как и компилятор, исходную про- грамму, не формирует машинный код в явном виде. Для каждой операции, которая может потребоваться при исполнении исход- ной программы, в программе-интерпретаторе заранее заготовле- на машинная команда или команды. «Узнав» очередную опера- цию в исходной программе, интерпретатор выполняет соответ- ствующие команды, потом — следующие, и так всю программу.
    Интерпретатор — это переводчик и исполнитель исходной про- граммы.
    Различие между интерпретаторами и компиляторами можно проиллюстрировать такой аналогией. Чтобы пользоваться ка- ким-либо англоязычным документом, мы можем поступить по- разному. Можно один раз перевести документ на русский, запи- сать этот перевод и потом пользоваться им сколько угодно раз.
    Это ситуация, аналогичная компиляции. Заметьте, что после вы- полнения перевода переводчик (компилятор) больше не нужен.
    Интерпретация же подобна чтению и переводу «с листа». Пере- вод не записывают, но всякий раз, когда нужно воспользоваться документом, его переводят заново, каждый раз при этом исполь- зуя переводчика
    1 1
    Одно из основных значений английского interpreter — устный (синхронный) пе- реводчик.

    11
    Рис. 1.1. Схема работы компилятора и интерпретатора
    Нетрудно понять преимущества и недостатки компиляторов и интерпретаторов.
    Компилятор обеспечивает получение быстрой программы на машинном языке, время работы которой намного меньше време- ни, которое будет затрачено на исполнение той же программы интерпретатором. Однако компиляция, являясь отдельным эта- пом обработки программы, может потребовать заметного време- ни, снижая оперативность работы. Откомпилированная про- грамма представляет собой самостоятельный продукт, для ис- пользования которого компилятор не требуется. Программа в машинном коде, полученная компиляцией, лучше защищена от внесения несанкционированных искажений, раскрытия лежащих в ее основе алгоритмов.
    Интерпретатор исполняет программу медленно, поскольку дол- жен распознавать конструкции исходной программы каждый раз, когда они исполняются. Если какие-то действия расположе- ны в цикле, то распознавание одних и тех же конструкций про- исходит многократно. Зато интерпретатор может начать испол-

    12 нение программы сразу же, не затрачивая времени на компиля- цию, — получается оперативней. Интерпретатор, как правило, проще компилятора, но его присутствие требуется при каждом запуске программы. Поскольку интерпретатор исполняет про- грамму по ее исходному тексту, программа оказывается неза- щищенной от постороннего вмешательства.
    Но даже при использовании компилятора получающаяся ма- шинная программа работает, как правило, медленнее и занимает в памяти больше места, чем такая же программа, написанная вручную на машинном языке или языке ассемблера квалифици- рованным программистом. Компилятор использует набор шаб- лонных приемов для преобразования программы в машинный код, а программист может действовать нешаблонно, отыскивая оптимальные решения. Разработчики тратят немало усилий, стремясь улучшить качество машинного кода, порождаемого компиляторами.
    В действительности различие между интерпретаторами и ком- пиляторами может быть не столь явным. Некоторые интерпрета- торы выполняют предварительную трансляцию исходной про- граммы в промежуточную форму, удобную для последующей интерпретации. Некоторые компиляторы могут не создавать файла объектного кода. Например, Turbo Pascal может компили- ровать программу в память, не записывая машинный код в файл, и тут же ее запускать. А поскольку компилирует Turbo Pascal быстро, то такое его поведение вполне соответствует работе ин- терпретатора.
    Существуют трансляторы, переводящие программу не в машин- ный код, а на другой язык программирования. Такие транслято- ры иногда называют конверторами. Например, в качестве пер- вого шага при реализации нового языка часто разрабатывают конвертор этого языка в язык Си. Дело в том, что Си — один из самых распространенных и хорошо стандартизованных языков.

    13
    Обычно ориентируются на версию ANSI Си — стандарт языка, принятый Американским Национальным Институтом Стандар- тов (American National Standards Institute, ANSI). Компиляторы
    ANSI
    Си есть практически в любой системе.
    Кросскомпиляторы (cross-compilers) генерируют код для маши- ны, отличной от той, на которой они работают.
    Пошаговые компиляторы (incremental compilers) воспринимают исходный текст программы в виде последовательности задавае- мых пользователем шагов (шагом может быть описание, группа описаний, оператор, группа операторов, заголовок процедуры и др.); допускается ввод, модификация и компиляция программы по шагам, а также отладка программ в терминах шагов.
    Динамические компиляторы (Just-in-Time — JIT compilers), по- лучившие в последнее время широкое распространение, транс- лируют промежуточное представление программы в объектный код во время исполнения программы.
    Двоичные компиляторы (binary compilers) переводят объектный код одной машины (платформы) в объектный код другой. Такая разновидность компиляторов используется при разработке но- вых аппаратных архитектур, для переноса больших системных и прикладных программ на новые платформы, в том числе —
    операционных систем, графических библиотек и др.
    Транслятор — это большая и сложная программа. Размер про- граммы-транслятора составляет от нескольких тысяч до сотен тысяч строк исходного кода. Вместе с тем разработка транслято- ра для не слишком сложного языка — задача вполне посильная для одного человека или небольшого коллектива. Методы раз- работки трансляторов и будут рассмотрены в этой книге.

    14
    Рис. 1.2. Компилятор языка Оберон, написанный Никлаусом Виртом, с его
    «автографом» (NW). Фрагмент исходного текста основного модуля показан в левом окне Оберон-системы, частью которой является компилятор.
    Компилятор написан на языке Оберон и может компилировать сам себя
    Транслятор связан в общем случае с тремя языками. Во-первых, это входной язык, с которого выполняется перевод. Во-вторых, целевой (объектный) язык, на который выполняется перевод. И, наконец, третий язык — это язык, на котором написан сам транслятор, — инструментальный язык. Трансляторы удобно изображать в виде Т-диаграмм
    2
    (рис. 1.3), которые предложил
    Х. Брэтман (H. Bratman) в 1961 году. Слева на такой диаграмме записывается исходный язык, справа — объектный, снизу — ин- струментальный.
    2
    Кроме того, что диаграмма имеет форму буквы «Т», примечательно, что с этой буквы начинается и само слово «транслятор», как русское, так и английское.

    15
    Рис. 1.3. Диаграммы трансляторов
    Первые трансляторы, появившиеся в 1950-е годы, программиро- вались на машинном языке или на языке низкого уровня — язы- ке ассемблера (автокоде, как принято было говорить в то время).
    Сейчас для разработки трансляторов используются языки высо- кого уровня.
    Изображая Т-диаграммы, мы можем не знать, на каком языке написан транслятор. В этом случае, а также когда недоступен исходный текст транслятора (т.е. мы располагаем только его ис- полняемой откомпилированной версией), на Т-диаграмме в ка- честве инструментального записывают машинный язык или обо- значение того компьютера, на котором этот транслятор работает.
    Можно считать, что на рис. 1.3а изображен компилятор Turbo
    Pascal, Delphi или Free Pascal, транслирующий с языка Паскаль в машинный код IBM PC-совместимого компьютера и сущест- вующий в виде программы в машинном коде IBM PC. На рис. 1.3б показана Т-диаграмма компилятора c языка Оберон
    (см. рис. 1.2), транслирующего в машинный код компьютера
    Ceres и написанного на языке Оберон. Рисунок 1.3в соответству- ет конвертору. Си# — язык программирования, созданный в корпорации Microsoft. Первая реализация Си# вполне могла

    16 быть выполнена по такой схеме. В дальнейшем мы еще обра- тимся к Т-диаграммам и узнаем, как они могут сочетаться по- добно костям домино, иллюстрируя процесс получения одних трансляторов с помощью других.
    Интерпретатор, кстати, можно изобразить в виде I-диаграммы
    (Interpreter — интерпретатор). Сверху записываем название входного, а внизу — инструментального языка. Пример диа- граммы для интерпретатора Бейсика, работающего на IBM PC, можно видеть на рис. 1.3г.
    Метаязыки
    Говоря о Т-диаграммах, мы забыли еще об одном, четвертом языке, который неизбежно присутствует в разговоре о трансля- торах и языках программирования. Это язык, например, русский, на котором мы ведем сам разговор. Язык, используемый для описания других языков, и называется метаязыком. В дальней- шем мы рассмотрим формализованные метаязыки, а пока в этой роли будем применять родной, естественный язык.
    Понятно, что бессмысленно обсуждать сколько-нибудь содержа- тельно сразу многие языки программирования, если не знаешь и одного, не имеешь хотя бы небольшого опыта программирова- ния. Я рассчитываю, что у вас такой опыт есть. Я даже предпо- лагаю, что вы, скорее всего, знакомы с языком Паскаль или, мо- жет быть, Си. Эти языки в нашем обзоре тоже будут в известном смысле играть роль метаязыков. Рассматривая другие языки, мы будем сравнивать имеющиеся в них средства с теми, что есть в
    Паскале или Си.

    17
      1   2   3   4   5   6   7   8   9   ...   41


    написать администратору сайта