Содержание. 1 Формальные языки и грамматики

1 Формальные языки и грамматики.....................................................................

1.1 Операции над цепочками символов...............................................................

1.2 Способы задания языков................................................................................

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

1.2.2 Формы Бэкуса-Наура...................................................................................

1.2.3 Диаграммы Вирта........................................................................................

1.2.4 Формальные грамматики.............................................................................

1.2.4.1 Определение формальной грамматики....................................................

1.2.4.2 Классификация языков и грамматик........................................................

1.2.4.3 Эквивалентность грамматик.....................................................................

1.2.5 Механизмы распознавания языков.............................................................

1.2.5.1 Определение распознавателя....................................................................

1.2.5.2 Схема работы распознавателя.................................................................

1.2.5.3 Классификация распознавателей..............................................................

2 Регулярные языки..............................................................................................

2.1 Регулярные выражения...................................................................................

2.2 Лемма о разрастании для регулярных языков..............................................

2.2 Конечные автоматы.........................................................................................

2.2.1 Определение конечного автомата...............................................................

2.2.2 Распознавание строк конечным автоматом................................................

2.2.3 Преобразование конечных автоматов........................................................

2.2.3.1 Преобразование конечного автомата к детерминированному виду......

2.2.3.2 Минимизация конечного автомата...........................................................

2.2.3.2.1 Устранение недостижимых состояний автомата...................................

2.2.3.2.2 Объединение эквивалентных состояний автомата................................

2.4 Взаимосвязь способов определения регулярных языков.............................

2.4.1 Построение конечного автомата по регулярной грамматике....................

2.4.2 Построение регулярной грамматики по конечному автомату.................

3 Контекстно-свободные языки............................................................................

3.1 Задача разбора................................................................................................

3.1.1 Вывод цепочек..............................................................................................

3.1.2 Дерево разбора............................................................................................

3.1.2.1 Нисходящее дерево разбора....................................................................

3.1.2.2 Восходящее дерево разбора.....................................................................

3.1.3 Однозначность грамматик...........................................................................

3.2 Преобразование КС-грамматик....................................................................

3.2.1 Проверка существования языка..................................................................

3.2.2 Устранение недостижимых символов..........................................................

3.2.3 Устранение e-правил....................................................................................

3.2.4 Устранение цепных правил..........................................................................

3.2.5 Левая факторизация правил........................................................................

3.2.6 Устранение прямой левой рекурсии...........................................................

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

3.3.1 Определение МП-автомата..........................................................................

3.3.2 Разновидности МП-автоматов.....................................................................

3.3.3 Взаимосвязь МП-автоматов и КС-грамматик............................................

3.3.3.1 Построение МП-автомата по КС-грамматике.........................................

3.3.3.2 Построение расширенного МП-автомата по КС-грамматике................

3.4 Нисходящие распознаватели языков.............................................................

3.4.1 Рекурсивный спуск.......................................................................................

3.4.1.1 Сущность метода.......................................................................................

3.4.1.2 Достаточные условия применимости метода...........................................

3.4.2 Распознаватели LL(k)-грамматик................................................................

3.4.2.1 Определение LL(k)-грамматики................................................................

3.4.2.2 Необходимое и достаточное условие LL(1)-грамматики........................

3.4.2.3 Построение множеств FIRST(1, A)...........................................................

3.4.2.4 Построение множеств FOLLOW(1, A)......................................................

3.4.2.5 Алгоритм «сдвиг-свертка» для LL(1)-грамматик....................................

3.5 Восходящие распознаватели языков..............................................................

3.5.1 Грамматики предшествования.....................................................................

3.5.1.1 Грамматики просторного предшествования...........................................

3.5.1.1.1 Определение грамматики простого предшествования.........................

3.5.1.1.2 Поиск основы сентенции........................................................................

3.5.1.1.3 Построение множеств L(A) и R(A)........................................................

3.5.1.1.4 Матрица предшествования....................................................................

3.5.1.1.5 Алгоритм «сдвиг-свертка» для грамматик простого предшествования

3.5.1.2 Грамматики операторного предшествования..........................................

3.5.1.2.1 Определение грамматики операторного предшествования.................

3.5.1.2.2 Построение множеств L^t(A) и R^t(A).......................................................

3.5.1.2.3 Матрица операторного предшествования............................................

3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматик простого предшествования

3.5.2 Распознаватели LR(k)-грамматик................................................................

3.6 Соотношение классов КС-грамматик.............................................................

4 Принципы построения трансляторов................................................................

4.1 Лексика, синтаксис и семантика языка...........................................................

4.2 Определение транслятора, компилятора, интерпретатора и ассемблера....

4.3 Общая схема работы транслятора.................................................................

4.5 Лексический анализ.........................................................................................

4.5.1 Задачи лексического анализа......................................................................

4.5.2 Диаграмма состояний с действиями............................................................

4.5.3 Функция scanner...........................................................................................

4.6 Синтаксический анализ..................................................................................

4.6.1 Задачи синтаксического анализа.................................................................

4.6.2 Нисходящий синтаксический анализ...........................................................

4.7 Семантический анализ....................................................................................

4.8 Генерация кода................................................................................................

4.8.1 Формы внутреннего представления программы........................................

4.8.1.1 Тетрады.....................................................................................................

4.8.1.2 Триады.......................................................................................................

4.8.1.3 Синтаксические деревья............................................................................

4.8.1.4 Польская инверсная запись......................................................................

4.8.1.5 Ассемблерный код и машинные команды...............................................

4.8.2 Преобразование дерева операций в код на языке ассемблера..................

4.9 Оптимизация кода...........................................................................................

4.9.1 Сущность оптимизации кода.......................................................................

4.9.2 Критерии эффективности результирующей объектной программы.........

4.9.3 Методы оптимизации кода..........................................................................

4.9.4 Оптимизация линейных участков программ..............................................

4.9.4.1 Свертка объектного кода..........................................................................

4.9.4.2 Исключение лишних операций.................................................................

4.9.5 Оптимизация циклов....................................................................................

4.9.6 Оптимизация логических выражений.........................................................

4.9.7 Оптимизация вызовов процедур и функций...............................................

4.9.8 Машинно-зависимые методы оптимизации................................................

5 Формальные методы описания перевода..........................................................

5.1 Синтаксически управляемый перевод............................................................

5.1.1 Схемы компиляции......................................................................................

5.1.2 СУ-схемы......................................................................................................

5.1.3 МП-преобразователи...................................................................................

5.1.4 Практическое применение СУ-схем............................................................

5.2 Транслирующие грамматики.........................................................................

5.2.1 Понятие Т-грамматики.................................................................................

5.2.2 Т-грамматика с подпрограммами...............................................................

5.2.3 МП-преобразователь для Т-грамматики....................................................

5.3 Атрибутные транслирующие грамматики.....................................................

5.3.1 Синтезируемые и наследуемые атрибуты...................................................

5.3.2 Определение и свойства АТ-грамматики....................................................

5.3.3 ФормированиеАТ-грамматики...................................................................