КОНСПЕКТ ЛЕКЦИЙ

По дисциплине «Теория автоматов и формальных языков»

Исполнитель

д. т. н., профессор ТГУ

Ю.Л. Костюк

Томск 2010

ОГЛАВЛЕНИЕ

1. ЯЗЫКИ И ГРАММАТИКИ 3

1.1. Язык как множество 3

1.2. Порождающая грамматика 3

1.3. Процесс порождения 4

1.4. Классификация грамматик по Хомскому 4

1.5. Классификация языков по Хомскому 5

1.6. Задача распознавания цепочек языка 6

2. ПРИНЦИПЫ ТРАНСЛЯЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 8

3. ЛЕКСИЧЕСКИЙ АНАЛИЗ 10

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

3.2. Построение детерминированного конечного автомата 10

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

3.4. Преобразование неоднозначной А-грамматики к однозначной 13

3.5. Удаление из грамматики бесполезных нетерминалов 14

3.6. Лексический анализатор 15

4. СИНТАКСИЧЕСКИЙ АНАЛИЗ 19

4.1. Дерево порождения для КС-грамматики 19

4.2. Автомат с магазинной памятью 19

4.3. LL-разбор КС-грамматики автоматом с магазинной памятью 21

4.4. Левая рекурсия и ее устранение 23

4.5. Преобразование КС-грамматики к обобщенной нормальной форме Грейбах 24

4.6. Детерминированный LL-разбор 24

5. ОБРАТНАЯ ПОЛЬСКАЯ СТРОКА, КАК ПРОМЕЖУТОЧНАЯ ФОРМА ПРОГРАММЫ 27

5.1. Обратная польская строка для арифметических выражений 27

5.2. Генерация ОПС для арифметических выражений 28

5.3. Вычисление ОПС для присваиваний и арифметических выражений с индексами 31

5.4. Генерация ОПС для присваиваний и арифметических выражений с индексами 33

5.5. ОПС для условных, циклических и составных операторов 35

5.6. ОПС для стандартных операторов 39

5.7. Распределение памяти и описание переменных 40

5.8. Обработка ошибок 42

6. Генерация команд в компиляторе 44

6.1. Распределение памяти при генерации команд 44

6.2. Генерация команд для присваиваний и арифметических выражений 45

6.3. Генерация команд с индексными выражениями 48

6.4. Генерация команд сравнения и перехода 53

1. Языки и грамматики

1.1. Язык как множество

Пусть задано некоторое конечное множество символов, называемое алфавитом. Из этих символов можно конструировать последовательности – цепочки символов. Пусть алфавит Σ содержит m символов. Из символов алфавита можно образовывать последовательности – цепочки символов. Количество символов в цепочке называют длиной. Пусть имеется некоторая цепочка α. Запись |α| обозначает длину этой цепочки. Две цепочки α и β, записанные подряд: αβ, обозначают цепочку, в которой вначале идут символы цепочки α, а затем символы цепочки β. Такое склеивание цепочек называют конкатенацией. Длина полученной цепочки равна сумме длин отдельных цепочек: |αβ| = |α| + |β|. Для общности удобно считать, что существует пустая цепочка длиной 0, для нее вводится особое обозначение λ, |λ| = 0. Заметим, что αλ = λα = α.

Из алфавита, содержащего m символов, можно составить ровно m различных всевозможных цепочек длиной 1, m² цепочек длины 2, и т.д., в общем случае количество различных цепочек длины n равно mⁿ. Множество всех цепочек длины 1 есть алфавит Σ, множество всех цепочек длины 2 обозначим как Σ², и т.д., множество всех цепочек длины n обозначим как Σⁿ. Множество всевозможных цепочек произвольной ненулевой длины, обозначаемое как Σ⁺, называется положительным транзитивным замыканием множества Σ. Оно равно объединению бесконечного количества множеств:

Σ⁺ = Σ U Σ² U Σ³ U … U Σⁿ U … 

Полное транзитивное замыкание множества Σ, обозначаемое как Σ^*, определяется как объединение Σ⁺ и множества из одной пустой цепочки λ:

Σ^* = Σ⁺ U {λ}.

Язык L над алфавитом Σ определяется как некоторое, возможно бесконечное, множество цепочек, являющееся подмножеством Σ^*, .

1.2. Порождающая грамматика

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

G(L) = {Σ, N, S, P},

где Σ – алфавит (множество) символов языка; N – алфавит (множество) символов грамматики; S – подмножество символов грамматики, называемых начальными, ; P – множество порождающих правил вида:

α → β,

где α и β – цепочки символов из алфавитов языка Σ и грамматики N, причем в цепочке α должно быть не менее одного символа из алфавита N. Каждое из правил задает подстановку, т.е. замену цепочки α на цепочку β.

Цепочку α называют левой, а цепочку β – правой частью порождающего правила. Если выполняется неравенство |α| ≤ |β|, то такое порождающее правило называют неукорачивающим. Если же |α| > |β|, то порождающее правило называется укорачивающим. В общем случае допустимо, чтобы в некоторых правилах цепочка β была пустой.

Далее в примерах заглавными латинскими буквами будут обозначаться символы грамматики (из алфавита N), строчными буквами и другими знаками – символы языка (из алфавита Σ), строчными греческими – цепочки символов (из обоих алфавитов N и Σ).