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

Л.Г. ГАГАРИНА
Е.В. КОКОРЕВА
ВВЕДЕНИЕ В ТЕОРИЮ 
АЛГОРИТМИЧЕСКИХ 
ЯЗЫКОВ И КОМПИЛЯТОРОВ
УЧЕБНОЕ ПОСОБИЕ
2-е издание, переработанное и дополненное
Москва
ИНФРА-М
2025

УДК 004.2(075.8)
ББК 32.973-02я73
 
Г12
А в т о р ы:
Гагарина Л.Г., доктор технических наук, профессор (предисловие, гл. 1);
Кокорева Е.В., кандидат технических наук, доцент (гл. 2–5, практикум)
Р е ц е н з е н т ы:
Портнов Е.М., доктор технических наук, профессор, профессор Национального 
исследовательского университета «Московский институт электронной техники»;
Лебедев А.В., кандидат технических наук, начальник отдела автоматизации 
систем управления общества с ограниченной ответственностью «НМ-ТЕХ»
Гагарина Л.Г.
Г12
 
 
Введение в теорию алгоритмических языков и компиляторов : учебное пособие / Л.Г. Гагарина, Е.В. Кокорева. — 2-е изд., перераб. и доп. — 
Москва : ИНФРА-М, 2025. — 207 с. — (Высшее образование). — 
DOI 10.12737/1872635.
ISBN 978-5-16-017756-4 (print)
ISBN 978-5-16-110525-2 (online)
В учебном пособии приведен систематизированный курс освоения теории формальных языков и грамматик — как регулярных, так и контекстносвободных. Рассмотрены современные задачи лексического, синтаксического и семантического анализа, известные принципы их использования 
для решения практических задач создания программного обеспечения. 
Строгий стиль изложения сопровождается многочисленными примерами, 
а также задачами для самостоятельного решения в составе практических 
заданий, необходимых для глубокого усвоения материала.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Для студентов, аспирантов, научных сотрудников, преподавателей высших учебных заведений, а также для тех, кто интересуется математическими основами программирования.
УДК 004.2(075.8)
ББК 32.973-02я73
© Гагарина Л.Г., Кокорева Е.В., 2009
© Гагарина Л.Г., Кокорева Е.В., с изменениями, 2024
ISBN 978-5-16-017756-4 (print)
ISBN 978-5-16-110525-2 (online)

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

Предисловие
быть использован при разработке текстовых редакторов. 
В главе 3 приведены различные методы синтаксического анализа, нисходящие (рекурсивного спуска, LL) и восходящие 
(LR и его варианты); подробно рассмотрен пример разработки 
синтаксического анализатора заданных конструкций языка 
С+. Глава 4 знакомит с принципиальными идеями семантического анализа, которые лежат в основе генерации промежуточного кода в типичном языке программирования. Глава 5 
посвящена проблемам, возникающим в процессе разработки 
трансляторов на практике; подробно рассмотрена вся технология программирования.
Структура пособия подчинена определенной внутренней 
логике, т.е. материал излагается последовательно, в соответствии с приобретением профессио 
нальных знаний. Особенностью данного пособия являются практические задания, необходимые для закрепления изученного теоретического материала. Только выполнив практические задания (фактически 
проверочные задачи для самостоятельной работы студентов 
к главам 1 и 2), можно перейти к лабораторным работам, представляющим собой своеобразный тренинг программиста-разработчика трансляторов на базе теории глав 3–5.
Данное учебное пособие предназначено в первую очередь 
для студентов высших учебных заведений, бакалавров и магистров, обучающихся по направлениям подготовки 09.03.04, 
09.04.04 «Программная инженерия», 01.03.04, 01.04.04 «Прикладная математика», 09.03.01, 09.04.01 «Информатика и вычислительная техника». Может быть полезно аспирантам, 
преподавателям вузов, курсов повышения квалификации 
и центров сертификации.
В результате освоения курса обучающийся будет:
знать
 
• правила построения трансляторов;
 
• методы лексического, синтаксического и семантического 
анализа алгоритмических языков;
 
• принципы трансляции и интерпретации;
4

Предисловие
уметь
 
• строить КС-грамматики формальных языков; 
 
• выделять лексический и синтаксический уровни языка;
 
• программировать основные классы трансляторов;
 
• разрабатывать алгоритмы и программы, пригодные 
для практического использования;
 
• проектировать, конструировать и тестировать программные 
продукты;
владеть
 
• методами анализа и трансляции алгоритмических языков;
 
• классическими подходами к разработке алгоритмических 
языков, проектированию и программированию лексических 
и синтаксических анализаторов языков на основе методов 
формального описания языков.
5

Глава 1. 
ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ
Для построения трансляторов необходимо однозначное 
и точное задание входного и выходного языков. Такое задание 
предполагает определение правил построения допустимых 
конструкций выражений языка.
Существует целый ряд математических формализмов 
для задания языков. Наиболее распространенным механизмом являются порождающие грамматики, которые задают 
все цепочки языка с помощью некоторых правил. Одно из достоинств грамматик заключается в том, что существует множество систем, которые по заданной грамматике генерируют 
программу, проверяющую соответствие входной цепочки 
определяемому языку.
Грамматика представляет собой математическую систему, 
порождающую язык. Строки языка строятся способом, точно 
определенным правилами грамматики [1–4].
1.1. ТЕРМИНОЛОГИЯ ПРЕДМЕТНОЙ ОБЛАСТИ
По мнению ученых, развитие разума на нашей планете происходило под влиянием языка, что позволило не только выражать 
и сохранять информацию, но и обмениваться ею друг с другом.
С созданием и развитием компьютерной техники возникла 
необходимость в появлении специальных языков для обмена 
информацией с устройством, понятных и удобных для человека и в то же время воспринимаемых компьютером. Совмещение обоих этих свойств в одном языке оказалось невозможным, по 
это 
му были разработаны специальные средства 
для перевода текста (исходного кода) с языка, понятного программисту, на язык, понятный устройству (машинный код), 
называемые трансляторами. Процесс преобразования исход6

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

Глава 1.  Основы теории формальных языков
В языке С директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа #. Рассмотрим некоторые наиболее известные из них:
#define идентификатор строка текста
Директива обеспечивает замену идентификатора, встречающегося в тексте программы, на соответствующую строку 
текста. Наиболее часто она применяется для символического 
обозначения константы, которая встречается многократно 
в различных частях программы. Например, размерность массива:
#define SIZE 100
int A[SIZE];
for (i=0; i<SIZE; i++)
В данном примере вместо имени SIZE в текст программы 
будет подставлена строка, содержащая константу 100. В том 
случае, если нас не устраивает размерность массива, нам достаточно увеличить это значение в директиве define и повторно оттранслировать программу:
#include <имя файла>
#include "имя файла"
В текст программы вместо указанной директивы включается текст файла, находящегося в системном или, соответственно, в текущем (явно указанном) каталоге. При этом 
в программу включаются тексты заголовочных файлов, содержащие информацию о функциях, находящихся в других объектных модулях и библиотеках. Например, текст
#include <stdio.h>
включает в программу текст заголовочного файла, содержащего объявления внешних функций из библиотеки стандартного ввода-вывода.
Работу транслятора можно представить состоящей из нескольких фаз. Первая фаза собственно трансляции называется 
8

1.1. Терминология предметной области
лексическим анализом, а программа, выполняющая ее, — лексическим анализатором (иногда — сканером).
Лексика языка программирования представляет собой 
правила составления слов программы (идентификаторы, константы, служебные слова, комментарии) из символов языка. 
Особенность любой лексики заключается в том, что ее элементами являются регулярные линейные последовательности 
символов. Например, идентификатор — это произвольная 
последовательность букв, цифр и символа подчеркивания, начинающаяся с буквы или символа подчеркивания.
На вход лексического анализатора подается последовательность символов входного языка, в которой анализатор выделяет простейшие конструкции языка (перечисленные выше), 
называемые лексическими единицами, и заменяет их внутренним представлением — лексемами.
Вторую фазу работы транслятора называют синтаксическим анализом, а соответствующую ей программу — синтаксическим анализатором (парсер, от англ. parse — анализ, разбор).
Синтаксис языка программирования — это правила составления предложений языка из отдельных слов. Такими 
предложениями являются операции, операторы, определения функций и переменных. К особенностям синтаксиса 
относится принцип вложенности (рекурсивность) правил построения предложений. Это значит, что элемент синтаксиса 
языка в своем определении прямо или косвенно в одной из его 
частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частный случай 
которого — все тот же оператор цикла.
Синтаксический анализатор получает на вход набор лексем 
и преобразует их в промежуточный код, представляющий 
собой последовательность символов действия, или атомов. 
Каждый атом включает описание операции, которую нужно 
выполнить, с указанием используемых операндов. При этом 
последовательность расположения атомов, в отличие 
9

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