Мартыненко Б.К. Языки и трансляции

Подождите немного. Документ загружается.

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Б.К. Мартыненко

ЯЗЫКИ И ТРАНСЛЯЦИИ

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

ИЗДАТЕЛЬСТВО

С.-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

2004

ISBN 5-288-02870-2

УДК 519.685.3

ББК 32.81

М 25

Рецензенты: д-р физ.-мат. наук проф. И. Л. Братчиков (С.-Петербургский гос. ун-т),

канд. физ.-мат. наук Ю. Л. Костюк (Томский гос. ун-т)

Печатается по постановлению

Редакционно-издательского совета

С.Петербургского государственного университета

Мартыненко Б.К.

М 25 Языки и трансляции: Учеб. пособие  СПб.: Издательство С.-Петербургского

университета, 2003. 235 с.

ISBN 5-288-02870-2

В учебном пособии излагаются основы математической теории формальных языков и трансляций, знание

которой необходимо всем, кто работает в области теоретической или прикладной информатики. Излагаются ос-

новные

факты теории с доказательствами. Содержание основано на материалах лекций, читавшихся автором в

разные годы на математико-механическом факультете Ленинградского — С.-Петербургского государственного

университета.

Прекрасные монографии по затрагиваемой тематике, изданные в 60–70-е годы, к настоящему времени стали

библиографической редкостью. Предполагается, что настоящее пособие хотя бы частично компенсирует недос-

таток учебной литературы в данной области.

Пособие предназначено для студентов математических факультетов университетов, изучающих синтакси-

ческие методы в информатике.

Библиогр. 20 назв. Табл. 19. Ил. 30.

Тем. план 2002 г., № 64 ББК 32.81

С.-Петербургского

университета, 2004

ОГЛАВЛЕНИЕ

Предисловие .................................................................................................................................................... 5

Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ

................................................................................. 7

Глава 1. Языки и их представление..................................................................................................................—

§ 1.1. Алфавиты и языки................................................................................................................................—

§ 1.2. Представление языков .......................................................................................................................... 8

Глава 2. Грамматики...........................................................................................................................................12

§ 2.1. Мотивировка.........................................................................................................................................—

§ 2.2. Формальное определение грамматики ...............................................................................................13

§ 2.3. Типы грамматик ...................................................................................................................................16

§ 2.4. Пустое предложение ............................................................................................................................18

§ 2.5. Рекурсивность контекстно-зависимых грамматик ............................................................................20

§ 2.6. Деревья вывода в контекстно-свободных грамматиках....................................................................22

Глава 3. Конечные автоматы и регулярные грамматики............................................................................25

§ 3.1. Конечный автомат................................................................................................................................—

§ 3.2. Отношения эквивалентности и конечные автоматы .........................................................................27

§ 3.3. Недетерминированные конечные автоматы ......................................................................................30

§ 3.4. Конечные автоматы и языки типа 3....................................................................................................33

§ 3.5. Свойства языков типа 3 .......................................................................................................................36

§ 3.6. Алгоритмически разрешимые проблемы, касающиеся конечных

автоматов ..............................................................................................................................................41

Глава 4. Контекстно-свободные грамматики .................................................................................................43

§ 4.1. Упрощение контекстно-свободных грамматик .................................................................................—

§ 4.2. Нормальная форма Хомского..............................................................................................................48

§ 4.3. Нормальная форма Грейбах ................................................................................................................50

§ 4.4. Разрешимость конечности контекстно-свободных языков ..............................................................54

§ 4.5. Свойство самовставленности..............................................................................................................58

§ 4.6. ε-Правила в контекстно-свободных грамматиках.............................................................................61

§ 4.7. Специальные типы контекстно-свободных языков и грамматик.....................................................63

Глава 5. Магазинные автоматы ........................................................................................................................65

§ 5.1. Неформальное описание......................................................................................................................—

§ 5.2. Формальное определение ....................................................................................................................66

§ 5.3. Недетерминированные магазинные автоматы и контекстно-свободные языки .............................69

Глава 6. Машины Тьюринга .............................................................................................................................77

§ 6.1. Неформальное и формальное описания .............................................................................................—

§ 6.2. Методы построения машин Тьюринга ...............................................................................................81

§ 6.3. Машина Тьюринга как процедура ......................................................................................................87

§ 6.4. Модификации машин Тьюринга ........................................................................................................89

§ 6.5. Ограниченные машины Тьюринга, эквивалентные основной модели ...........................................95

Глава 7. Машины Тьюринга: проблема остановки, языки типа 0 ...........................................................99

§ 7.1. Универсальная машина Тьюринга......................................................................................................—

§ 7.2. Неразрешимость проблемы остановки.............................................................................................105

§ 7.3. Класс рекурсивных множеств...........................................................................................................107

§ 7.4. Машины Тьюринга и грамматики типа 0.........................................................................................108

Глава 8. Линейно ограниченные автоматы и контекстно-зависимые языки.......................................113

§ 8.1. Линейно ограниченные автоматы.......................................................................................................—

§ 8.2. Связь линейно ограниченных автоматов с контекстно-зависимыми языками .............................114

§ 8.3. Контекстно-зависимые языки — подкласс рекурсивных множеств..............................................116

Глава 9. Операции над языками ....................................................................................................................117

§ 9.1. Замкнутость относительно элементарных операций ........................................................................—

§ 9.2. Замкнутость относительно отображений........................................................................................ 120

Часть II: ТРАНСЛЯЦИИ И СИНТАКСИЧЕСКИЕ МЕТОДЫ ИХ РЕАЛИЗАЦИИ ............................130

Глава 1. Трансляции, их представление и реализация.................................................................................—

§ 1.1. Трансляции и трансляторы..................................................................................................................—

§ 1.2. Схемы синтаксически управляемой трансляции.............................................................................131

§ 1.3. Магазинные преобразователи и синтаксически управляемые трансляции...................................133

§ 1.4. Детерминированная генерация выходной цепочки трансляции по

левостороннему анализу входной цепочки.......................................................................................144

Глава 2. LL(k)-Грамматики и трансляции ....................................................................................................148

§ 2.1. Введение в LL(k)-грамматики ............................................................................................................—

§ 2.2. Свойства LL(k)-грамматик.................................................................................................................150

§ 2.3. k-Предсказывающие алгоритмы анализа ........................................................................................157

§ 2.4. Построение 1-предсказывающего алгоритма анализа по LL(1)-грамматике ................................160

§ 2.5. Анализ в LL(k)-грамматиках .............................................................................................................166

§ 2.6. Тестирование LL(k)-грамматик .........................................................................................................173

§ 2.7. Вычисление функции

FIRST

(β) ................................................................................................174

§ 2.8. Вычисление функции σ(A) ................................................................................................................177

§ 2.9. Алгоритм вычисления функции

()

.....................................................................181

§ 2.10. k-Предсказывающий алгоритм трансляции ...................................................................................184

§ 2.11. Непростые LL(k)-трансляции и магазинные процессоры .............................................................188

Глава 3. LR(k)-Грамматики и трансляции....................................................................................................192

§ 3.1. Синтаксический анализ типа “снизу—вверх” ...................................................................................—

§ 3.2. LR(k)- Грамматики .............................................................................................................................195

§ 3.3. LR(k)-Анализатор ...............................................................................................................................198

§ 3.4. Свойства LR(k)-грамматик.................................................................................................................200

§ 3.5. Тестирование LR(k)-грамматик.........................................................................................................217

§ 3.6. Канонические LR(k)-анализаторы.....................................................................................................219

§ 3.7. Корректность LR(k)-анализаторов ....................................................................................................222

§ 3.8. Простые постфиксные синтаксически управляемые LR-трансляции............................................227

§ 3.9. Простые непостфиксные синтаксически управляемые LR-трансляции........................................229

§ 3.10. LALR(k)-Грамматики........................................................................................................................230

Приложение: Неразрешимые и разрешимые проблемы, касающиеся формальных языков..............232

Указатель литературы......................................................................................................................................234

ПРЕДИСЛОВИЕ

В современных информационных технологиях синтаксические методы иг-

рают существенную роль. Трансляторы языков программирования (компилято-

ры, интерпретаторы, конверторы), синтаксические редакторы, машинный пере-

вод, различные средства обработки текстовой информации основаны на исполь-

зовании синтаксических методов. Теория формальных языков и трансляций со-

ставляет теоретический фундамент этих методов. Основы этой теории были за-

ложены Н. Хомским в 40–50-е годы XX столетия в связи с его лингвистически-

ми работами, посвященными изучению естественных языков, но уже в следую-

щем десятилетии синтаксические методы нашли широкое практическое приме-

нение в области разработки и реализации языков программирования. В настоя-

щее время применение технологических средств, основанных на синтаксиче-

ских методах, стало обыденным делом. Однако их грамотное и эффективное

применение требует от пользователя знания, по крайней мере, основ математи-

ческой теории, на которой они базируются.

Данное

пособие написано на основе лекций, читавшихся автором в Ленин-

градском

— Санкт-Петербургском государственном университете в разные го-

ды для студентов математико-механического факультета. На отделении инфор-

матики этот курс читался совместно с С. Я. Фитиаловым — доцентом кафедры

информатики, блестящим лектором, к сожалению, недавно ушедшим из жизни.

Отчасти этим печальным обстоятельством вызвана подготовка данного пособия.

Другая причина в том, что эта тематика, по-прежнему актуальная для специали-

стов и студентов, “вышла из моды”: фундаментальные монографии, изданные

четверть века назад, стали библиографической редкостью. Автор надеется, что

предлагаемое читателю пособие хотя бы в малой степени компенсирует сущест-

вующую нехватку учебной литературы по изучаемому предмету.

Разбиение текста пособия на две части: I. Языки, грамматики, автоматы и

II. Трансляции и синтаксические методы их реализации — соответствует было-

му распределению ролей двух лекторов, совместно читавших один курс. Часть I

представляет собой авторизованный перевод отдельных глав монографии [2], с

некоторыми дополнениями. Часть II является переложением нескольких тем из

двухтомной монографии [6], отличающимся от оригинала, главным образом,

тем, что в нем восстановлены полные доказательства многих утверждений, ос-

тавленных в первоисточнике в качестве упражнений. В Указателе литературы

эти два источника следует считать основными.

Методические установки данного учебного пособия сводятся к тому, чтобы

познакомить читателя с фундаментальными фактами классической теории язы-

ков и трансляций, дать ему представление о приемах доказательства утвержде-

ний в изучаемой области, а также снабдить его некоторым запасом практически

полезных алгоритмов. Почти все доказательства носят конструктивный харак-

тер и потому дают полезный материал для практики.

Схематически содержание первой части следует в основном классификации

языков по Н. Хомскому: в части I рассматриваются четыре типа грамматик и

соответствующих им распознавателей. Главу 6 о машинах Тьюринга в данном

пособии можно рассмативать как факультативную, поскольку эта тема традици-

онно излагается в курсе по теории алгоритмов. Однако ее материал необходим

для понимания последующих глав 7 и 8, в которых излагается связь языков типа

0 с машинами Тьюринга, и языков типа 1 — с линейно ограниченными автома-

тами. Несколько особняком стоит глава 9, в которой рассматриваются свойства

замкнутости языков относительно элементарных операций и отображений. Она

дополняет главу 3, в которой рассматриваются свойства замкнутости регуляр-

ных множеств.

Часть II посвящена описанию двух классов контекстно-свободных языков:

LL(k) и LR(k) ввиду их практической важности. Первый является наибольшим

естественным классом языков, допускающих детерминированный нисходящий

разбор посредством k-предсказывающего алгоритма анализа. Второй представ-

ляет столь же естественный класс языков, допускающих детерминированный

восходящий разбор посредством канонического анализатора Д. Кнута. Тот и

другой имеют линейную сложность по времени. Как известно, метод Кнута ис-

пользуется в инструменте YACC — популярном построителе синтаксических

анализаторов, а также в более развитых модификациях этого технологического

средства. Фактически в них используются LR(1)-грамматики с дополнительны-

ми оптимизирующими ограничениями — так называемые LALR(1)-грамматики.

Последние обсуждаются в конце этой части. В части II рассматриваются также

некоторые классы синтаксически-управляемых трансляций с входными языками

упомянутых классов и соответствующие алгоритмы их реализации. Последние

описываются с достаточной для практики полнотой и обоснованием корректно-

сти и оценок сложности.

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

неразрешимых проблем, касающихся формальных языков. Она позволит прак-

тикующему читателю сориентироваться, что возможно или невозможно в мире

формальных языков.

В пособии имеется достаточное число примеров, но нет задач и упражнений.

Автор надеется исправить этот недостаток, подготавливая к изданию «Сборник

задач и упражнений по теории формальных языков и трансляций».

Автор признателен рецензентам: профессору И. Л. Братчикову из Санкт-

Петербургского государственного университета и доценту Ю. Л. Костюку из

Томского государственного университета — за критические замечания, которые

по возможности были приняты во внимание.

Особую благодарность хочется выразить заведующему лабораторией Java-

технологии Научно-исследовательского института математики и механики

СПбГУ им. академика В. И.

Смирнова профессору В. О. Сафонову, предоставив-

шему

технические средства для подготовки оригинал-макета данного пособия.

Б. К. Мартыненко

Старый Петергоф,

Июнь 2002 г.

Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ

Глава 1

ЯЗЫКИ ИХ ПРЕДСТАВЛЕНИЕ

§ 1.1. Алфавиты и языки

Приступая к изучению теории языков, прежде всего следует определить, что

мы подразумеваем под термином язык. Энциклопедическое определение языка

как ”важнейшего средства общения, обмена мыслями и взаимного понимания в

человеческом обществе”

недостаточно точно для построения математической

теории языков. Поэтому мы определим язык абстрактно — как математическую

систему. Эта формальность даст нам возможность делать строгие утверждения о

формальных языках, которые надлежащим образом будут моделироваться. С

этой мыслью мы дадим следующие определения.

Определение 1.1. Алфавит или словарь есть конечное множество символов.

Что такое символ — не определяется, как не определяется, например, точка в

геометрии.

Некоторые примеры алфавитов: латинский {A, B, ..., Z}; греческий {α, β, ...,

ω}; бинарный {0, 1}.

Определение 1.2. Предложение (строка, слово) есть любая цепочка конеч-

ной длины, составленная из символов алфавита. Предложение, не содержащее

ни одного символа, называется пустым предложением. Оно обозначается гре-

ческой буквой ε.

Если V — некоторый алфавит, то V

обозначает множество всех предложе-

ний, составленных из символов алфавита V, включая и пустое предложение.

Будем обозначать посредством V

множество V

\{ε}. Так, например, если

V = {0, 1}, то V

= {ε, 0, 1, 00, 01, 10, 11, 000, ...}, а V

= {0, 1, 00, 01, 10, 11, ...}.

Если x ∈V

, то |x | обозначает длину цепочки x, т. е. число символов, ее со-

ставляющих. Естественно считать, что длина пустой цепочки ε равна 0.

Определение 1.3. Язык есть любое множество предложений над некоторым

алфавитом. Формально, если V — алфавит, L — язык, то L ⊆ V

Естественно возникают три вопроса:

1. Как представить язык, т. е. как определить предложения, составляющие

язык?

2. Для каждого ли языка существует конечное представление?

3. Какова структура тех классов языков, для которых существуют конечные

представления?

Энциклопедический словарь. — М.: Большая советская энциклопедия, 1955. С. 716.

На первый вопрос ответить легко, если язык конечен. Надо просто перечис-

лить все предложения, т. е. составить список. Если язык бесконечен, то возника-

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

Это конечное представление само будет строкой символов над некоторым алфа-

витом с подразумеваемой интерпретацией, которая связывает это конкретное

представление с данным языком.

На второй вопрос ответ отрицателен. В следующем параграфе будет показа-

но, что множество всех предложений над данным словарем счетно-бесконечно.

То, что множество всех подмножеств счетно-бесконечного множества не яв-

ляется счетно-бесконечным, есть хорошо известный факт теории множеств

Другими словами, множество всех языков над данным алфавитом не счетно. Яс-

но, что конечное представление языка будет предложением какого-то (обычно,

другого) языка (метаязыка). Но этот последний, как и любой другой язык, не

более чем счетно-бесконечное множество предложений. Так что существует

значительно больше языков, чем конечных представлений.

Ответу на третий вопрос посвящена бóльшая часть дальнейшего изложения.

§ 1.2. Представление языков

Распознавание. Один из способов представления языка состоит в том, чтобы

дать алгоритм

, который определяет, есть ли данное предложение в данном

языке или нет.

Более общий способ — дать процедуру, которая прекращает работу с отве-

том “да” для предложений в языке и либо не завершается

, либо завершается с

ответом “нет” для предложений не из языка. Говорят, что такие алгоритм и

процедура распознают язык.

Существуют языки, которые можно распознать при помощи процедуры, но

не при помощи алгоритма.

Порождение. Другой способ представления языка — дать процедуру, кото-

рая систематически порождает предложения языка последовательно в некото-

ром порядке.

Если имеется алгоритм или процедура, которые распознают предложения

языка над алфавитом V, то на их основе можно построить порождающий меха-

низм — алгоритм или процедуру, порождающий этот язык. Именно, можно сис-

тематически генерировать все предложения из множества V

, проверять каждое

Теорема Г. Кантора (1878 г.).

Согласно Д. Кнуту [11] алгоритм — это свод конечного числа правил, задающих после-

довательность выполнения операций при решении той или иной конкретной задачи. Для алго-

ритма характерны следующие пять особенностей: (1) конечность — завершаемость после вы-

полнения конечного числа шагов; (2) определенность — однозначность; (3) ввод — исходные

данные; (4) вывод — результат; (5) эффективность — выполнимость любой операции за ко-

нечное время. В вырожденных случаях ввод и (или) вывод могут отсутствовать.

Этим она и отличается от алгоритма.

предложение на принадлежность его языку с помощью распознающего меха-

низма и выводить в список только предложения языка. Однако если использует-

ся распознающая процедура, а не алгоритм, то есть опасность, что процесс по-

рождения никогда не продвинется дальше первого же предложения, на котором

процедура не завершается.

Для предотвращения этой опасности надо организовать проверку таким об-

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

предложения вечно. Сделать это можно следующим образом.

Пусть в алфавите V имеется p символов. Предложения из множества V

можно рассматривать как числа p-ичной системы счисления плюс пустое пред-

ложение ε. Пронумеруем предложения из V

в порядке увеличения длины, при-

чем все предложения одинаковой длины будем нумеровать в “числовом” поряд-

ке. Например, если V = {a, b, c}, то предложения из V

будут занумерованы сле-

дующим образом:

10.

11.

12. ...

Тем самым показано, что множество предложений над алфавитом V счетно.

Пусть P — распознающая процедура для языка L. Предполагается, что она

разбита на шаги так, что имеет смысл говорить об i-м шаге этой процедуры для

любого заданного предложения.

Прежде чем дать процедуру перечисления предложений языка L, определим

способ нумерации пар положительных целых. Можно отобразить все множество

пар положительных целых (i, j) на множество положительных целых, как пока-

зано в табл. 1.1, при помощи следующей формулы:

(1)(2)

ij ij

+− +−

Табл. 1.1

1 2 3 4 5

1 1 3 6 10 15

2 2 5 9 14 ...

3 4 8 13 ...

4 7 12 ...

5 11 ...

Замечание 1.1. Поясним, как получена вышеприведенная формула. Пусть имеется

некоторое k, занимающее в сетке позицию (i , j). Ясно, что k = N + j , здесь N — число

элементов внутри треугольной сетки с основанием, концы которого имеют координаты

(i, 1) и (1, i). Очевидно, что

(1)

123... ,

=+++ + =