ВВЕДЕНИЕ. Основные структуры данных и алгоритмы компиляции

М. А. Шамашов

ОСНОВНЫЕ СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ КОМПИЛЯЦИИ

Учебное пособие

Самара

УДК 681.3

Основные структуры данных и алгоритмы компиляции. Учебное пособие./ М.А. Шамашов. Самара: Научно–внед­рен­чес­кая фирма “Сенсоры, модули, системы”, 1999, 115 с.

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

Пособие ориентировано на студентов, изучающих компьютерные науки, и специалистов в области проектирования системного и прикладного программного обеспечения в самых разных областях. Рекомендуется в качестве учебника для использования в учебном процессе специальности 01.02 “Прикладная математика”, специализация 01.02.01 – математическое и программное обеспечение систем (информационные технологии в производстве), а также специальностей “Автоматизированные системы обработки информации и управления” и “Программное обеспечение вычислительных и автоматизированных систем”. Выполнено на кафедре “Информатика”и в лаборатории “Открытые системы” Университета Наяновой.

Ил. 68. Табл. 6. Библ. 18 наимен.

Печатается по решению редакционно–издательского совета научно–внедренческой фирмы “Сенсоры, модули, системы”.

Ó М. А. Шамашов, 1999.

Ó Университет Наяновой, 1999.

ПРЕДИСЛОВИЕ

Перед вами учебное пособие, которое задумывалось как вторая часть учебника для одно– или двухсеместрового курса по теории формальных языков и основам построения компиляторов. Напомним, что в первом пособии этой серии – “Теория формальных языков. Грамматики и автоматы”[16] освещается та часть математической теории формальных языков и автоматов, на которой базируется синтаксически управляемый перевод. Данное пособие, напротив, более конструктивно. В нем рассмотрены структуры данных, алгоритмы и реализационные аспекты трансляторов, компиляторов, интерпретаторов и ассемблеров. И в этой связи пособие должно представлять несомненный самостоятельный интерес.

На наш взгляд, нельзя быть специалистом в области Computer Science и не знать принципов функционирования различных трансляторов для языков высокого уровня и ассемблеров, стоящих в ряду наиболее сложных и интересных программных систем.

Кроме того, развитие вычислительной техники невозможно без изобретения новых языков общения с ней. Человеку вообще свойственно создавать новые языки. Современные информационные технологии предполагают привлечение конечного пользователя, ученого или инженера, специалиста в конкретной предметной области, а не вычислительной техники и технологии программирования к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс, – пользователь должен ставить задачу и получать результаты в терминах известной ему предметной области. То есть, нужен предметно ориентированный язык. Думаю, что многим из Вас придется столкнуться с разработкой таких языков. Да и при разработке любой простейшей автоматизированной системы, пакета программ необходимо помнить о входном языке этой системы, знать как его анализировать, контролировать, транслировать и воплощать в действие. И для того, чтобы не “изобретать велосипед”, надо, конечно же, знать методы, алгоритмы, способы организации данных и средства автоматизации, лежащие в основе построения подобных систем.

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

В первой главе пособия кратко рассмотрена вся совокупность задач, решаемых компилятором в их взаимосвязи. Последующие главы посвящены детальному рассмотрению наиболее интересных и важных фаз компиляции. Во второй главе рассмотрены алгоритмы и структуры данных лексического анализатора (сканера). В третьей главе обсуждаются возможные способы организации таблиц компиляторов. Четвертая и пятая, наиболее объемные главы посвящены описанию различных методов синтаксического анализа. Рассматриваются недетерминированные алгоритмы (алгоритмы с возвратами) нисходящего и восходящего синтаксического анализа, наименее эффективные, но подходящие для произвольных контекстно–свободных языков. Обсуждаются детерминированные LL(k) анализаторы, а также анализаторы языков простого и операторного предшествования. В шестой главе дано введение в семантику, обеспечивающую перевод программ во внутреннюю форму (ПОЛИЗ, тетрады) с ее последующей интерпретацией или генерацией кода. В седьмой главе обсуждаются методы машинно–независимой оптимизации программ. В восьмой главе дан обзор машинно-зависимых фаз компиляции. Там же приводятся некоторые сведения о трансляции с языка ассемблера.

ВВЕДЕНИЕ

Транслятор – это программа перевода текста (программы) с одного языка (исходного) на другой (объектный).

Если исходный язык является языком программирования высокого уровня, например, таким как ФОРТРАН, АЛГОЛ, АДА, ПАСКАЛЬ, СИ или МОДУЛА – 2 и, если объектный язык автокод (язык ассемблера) или машинный язык, то транслятор называют компилятором. Машинный язык иногда называют кодом машины, и поэтому объектная программа зачастую называется объектным кодом. Трансляция исходной программы в объектную выполняется во время компиляции, а фактическое выполнение объектной программы во время выполнения готовой программы.

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

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

В процессе изложения материала мы будем рассматривать синтаксически управляемые методы компиляции. Почти половина курса будет посвящена автоматическому распознаванию синтаксиса языков, что в свою очередь основывается на теории формальных языков, которую мы рассматривали в первой части курса и учебном пособии “Теория формальных языков. Грамматики и автоматы”. Вам необходимо вспомнить азы этого курса и, в первую очередь, автоматные и контекстно–свободные языки и грамматики, конечные автоматы и автоматы с магазинной памятью. Знание теории формальных языков позволяет глубже понять процессы компиляции, поможет систематически и эффективно проводить проектирование и реализацию компилятора.

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