Введение в теорию алгоритмических языков и компиляторов


Л. Г. Гагарина, Е. В. Кокорева





                ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМИЧЕСКИХ ЯЗЫКОВ И КОМПИЛЯТОРОВ






Допущено Учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся но направлению 09.03.01 «Информатика и вычислительная техника»







Электронно-




znanium.com


Москва
ИД «ФОРУМ» — ИНФРА-М
2022

УДК 004.2(075.32)
ББК 32.973-02я723
      Г12


   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

      Рецензенты:
         кандидат технических наук, генеральный директор ОАО «ОТИК-групп» (Общероссийский технический информационный канал) Д.Б. Ломоносов;
         кандидат технических наук, доцент А.А. Петров (кафедра «Информационные технологии» филиала Санкт-Петербургского гуманитарного университета профсоюзов)

      Гагарина Л. Г.
Г12 Введение в теорию алгоритмических языков и компиляторов : учебное пособие / Л.Г. Гагарина, Е.В. Кокорева ; под ред. Л.Г. Гагариной. — Москва : ИД «ФОРУМ», 2022. — 176 с: ил. — (Высшее образование).

         ISBN 978-5-8199-0404-6

         Учебник написан в соответствии с Федеральным государственным образовательным стандартом 3-го поколения. Приведен систематизированный курс освоения теории формальных языков и грамматик — как регулярных, так и контекстно-свободных. Рассмотрены современные задачи лексического, синтаксического и семантического анализа, известные принципы их использования для решения практических задач создания программного обеспечения. Строгий стиль изложения сопровождается многочисленными примерами, а также задачами для самостоятельного решения в составе практических заданий, необходимых для глубокого усвоения материала.
         Для студентов, аспирантов, научных сотрудников, преподавателей высших учебных заведений, а также для тех, кто интересуется математическими основами программирования.

УДК 004.2(075.32)
ББК 32.973-02я723

ISBN 978-5-8199-0404-6

© Л. Г. Гагарина, Е. В. Кокорева, 2014
© ИД «ФОРУМ», 2014

            Предисловие







   Предлагаемое учебное пособие посвящено технологии преобразования программ для выполнения их на компьютере с помощью трансляторов — специальных средств для перевода программ с языка программирования на машинный язык. Со времени появления первого такого средства в мире разработки компиляторов произошли значительные изменения: эволюционировали языки программирования, архитектура компьютеров; появилось множество различных вычислительных ресурсов, грамотное использование которых необходимо для получения лучших результатов. Приведенные в пособии методы — грамматики, регулярные выражения, синтаксические анализаторы, а также методы оптимизации — сегодня находят применение не только в компиляторах, но и в инструментарии для поиска ошибок в программном обеспечении и, что особенно важно, при проверке безопасности существующего кода.
   По всей видимости, далеко не все читатели книги будут заниматься разработкой или хотя бы поддержкой компилятора для какого-либо языка программирования, однако изложенный далее систематизированный материал может применяться для решения широкого диапазона задач проектирования и разработки программного обеспечения.
   Основной текст пособия состоит из пяти взаимосвязанных глав, в каждой из которых содержатся примеры, поясняющие излагаемый теоретический материал, предусмотрены контрольные вопросы. Глава 1 содержит терминологический и понятийный аппарат теории формальных языков, классификации грамматик, языков, распознавателей. Глава 2 посвящена лексическому анализу, регулярным выражениям, конечным автоматам и инструментарию для создания детерминированных конечных автоматов. Материал главы может быть использован при разработке текстовых редакторов. В гл. 3 приведены различные методы синтаксического анализа, нисходящие (рекурсивного спуска, LL)

Предисловие

и восходящие (LR и его варианты); подробно рассмотрен пример разработки синтаксического анализатора заданных конструкций языка СИ+. Глава 4 знакомит с принципиальными идеями семантического анализа, которые лежат в основе генерации промежуточного кода в типичном языке программирования. Глава 5 посвящена проблемам, возникающим в процессе разработки трансляторов на практике, подробно рассмотрена вся технология программирования.
   Структура пособия подчинена определенной внутренней логике, т. е. материал излагается последовательно, в соответствии с приобретением профессиональных знаний. Особенностью данного пособия являются практические задания, необходимые для закрепления изученного теоретического материала. Только выполнив практические задания (фактически проверочные задачи для самостоятельной работы студентов к гл. 1 и 2), можно перейти к лабораторным работам, представляющим собой своеобразный тренинг программиста-разработчика трансляторов на базе теории гл. 3—5.
   Данное учебное пособие предназначено, в первую очередь, для студентов высших учебных заведений, обучающихся по специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем» по направлению подготовки специалистов 654600 «Информатика и вычислительная техника» и направлению подготовки бакалавров и магистров 552800 «Информатика и вычислительная техника». Может быть полезно аспирантам, преподавателям вузов, курсов повышения квалификации и центров сертификации.
   Труд авторов распределился следующим образом: предисловие, гл. 1, практические задания к гл. 5 — профессор, доктор технических наук Л. Г. Гагарина, гл. 2—5, практические задания к гл. 1—3 — доцент Е. В. Кокорева.
   Авторский коллектив выражает глубокую признательность ведущему специалисту Государственного унитарного предприятия Научно-технический центр «Спурт» В. Г. Дорогову за конструктивную поддержку, оказанную при написании пособия, а также аспиранту кафедры «Информатика и программное обеспечение вычислительных систем» Московского института электронной техники А. В. Солякову за верификацию практических заданий.

Глава 1


            ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ
            ЯЗЫКОВ







   Для построения трансляторов необходимо однозначное и точное задание входного и выходного языков. Такое задание предполагает определение правил построения допустимых конструкций выражений языка.
   Существует целый ряд математических формализмов для задания языков. Наиболее распространенным механизмом являются порождающие грамматики, которые задают все цепочки языка с помощью некоторых правил. Одно из достоинств грамматик заключается в том, что существует множество систем, которые по заданной грамматике генерируют программу, проверяющую соответствие входной цепочки определяемому языку.
   Грамматика представляет собой математическую систему, порождающую язык. Строки языка строятся способом, точно определенным правилами грамматики [2—5].


        1.1. Терминология предметной области

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

Глава 1. Основы теории формальных языков

   Технология преобразования программ для выполнения их на компьютере сформировалась в начале 1960-х гг. и с тех пор не претерпела существенных изменений.
   Подготовка программы начинается с редактирования файла, содержащего текст этой программы, который имеет стандартное расширение для данного языка. Затем выполняется его трансляция, которая включает несколько этапов [1, 2]:
   • препроцессор;
   • анализ, который включает в себя три фазы:
     —  лексический анализ;
     —  синтаксический анализ;
     —  семантический анализ;
   • синтез (генерация машинного представления кода программы), включающий все или некоторые из нижеперечисленных фаз:
     —  генерация машинно-независимого кода;
     —  оптимизация машинно-независимого кода;
     —  распределение памяти;
     —  генерация машинного кода;
     —  оптимизация машинного кода.
   В результате трансляции получается объектный модуль. Файл объектного модуля имеет стандартное расширение .obj. Компоновка (сборка) программы заключается в объединении одного или нескольких объектных модулей программы и объектных модулей, взятых из библиотечных файлов и содержащих стандартные функции. В результате получается исполняемая программа в виде отдельного файла (загрузочный модуль, программный файл) со стандартным расширением .exe, который затем загружается в память и выполняется.

   Фазы трансляции
   Препроцессор — это предварительная фаза трансляции, которая выполняет замену одних частей текста на другие.
   В языке Си директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа #. Рассмотрим некоторые наиболее известные:

   #define идентификатор строка текста

   Директива обеспечивает замену идентификатора, встречающегося в тексте программы, на соответствующую строку текста. Наиболее часто она применяется для символического обозначе

1.1. Терминология предметной области

7

ния константы, которая встречается многократно в различных частях программы. Например, размерность массива:

    #define SIZE 100
    int A[SIZE];
    for (i=0; i<SIZE; i++) {...}

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

    #include <имя файла>
    #include "имя файла"

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

    #include <stdio.h>

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

Глава 1. Основы теории формальных языков

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

1.1. Терминология предметной области

9

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

    Структура транслятора
    Процесс трансляции не является линейным. Анализ фрагментов программы, формирование внутреннего промежуточного представления и синтез выходного представления программы не являются последовательными процедурами. Эти процессы протекают в несколько этапов, оказывают влияние друг на друга и могут осуществляться параллельно.
    Таким образом, обобщенную структуру транслятора можно описать следующим образом:
    • каждая фаза транслятора получает файл данных от предыдущей фазы, обрабатывает его, создает внутренние таблицы данных и по ним формирует выходной файл с данными для следующей фазы;
    • фазы трансляции вызывают одна другую в процессе обработки соответствующих языковых единиц;

Глава 1. Основы теории формальных языков

   Обработка исходного текста начинается, как правиёо, с синтаксического анализа — центрального элемента такой структуры, т. е. основной программой транслятора является синтаксический анализатор, который при разборе структурной единицы языка, называемой предложением (выражение, оператор, определение типа или переменной), вызывает лексический анализатор, для чтения очередной лексической компоненты (идентификатора, константы), а по завершении разбора — семантическую процедуру, процедуры генерации кода или интерпретации.
   Из этой схемы выпадает только препроцессор, который обычно представляет собой независимую предварительную фазу трансляции.


        1 .2. Основные понятия и определения

   Формальная грамматика, или просто грамматика, в теории формальных языков — это способ описания формального языка, т. е. выделения некоторого подмножества из множества всех слов некоторого алфавита [4].

   Определение 1.1. Алфавит — это конечное множество символов [5].

   Пример 1.1. Алфавит X = {a, b, c, +, -, *, /} содержит семь букв, а алфавит Y = {00, 01, 10, 11} — четыре буквы, каждая из которых состоит из двух символов.

   Определение 1.2. Цепочкой символов в алфавите Vназывается любая конечная последовательность символов этого алфавита.

   В качестве соглашения примем, что для обозначения отдельных символов будем использовать буквы латинского алфавита: a, b, c, d и т. д., а для обозначения цепочек символов — буквы греческого алфавита: а, р, у и т. д.

   Определение 1.3. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ X.

   Определение 1.4. Длина цепочки — это число составляющих ее символов.