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

ОГЛАВЛЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. ГЕНЕРАЦИЯ КОМАНД В КОМПИЛЯТОРЕ.. 43

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

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

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

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

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

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

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

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

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

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

Σ^* = Σ⁺ U {λ}.

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

Дата добавления: 2015-07-26; просмотров: 232; Нарушение авторских прав

Мы поможем в написании ваших работ!