- •3. Опорный конспект лекций
- •3.1. Введение, определение языка
- •3.1.1. Элементы теории языка и их грамматика. Символы, цепочки и операции над ними
- •Формальное определение языка
- •3.1.3. Отношения и операции над ними
- •3.1.4. Требования, предъявляемые к грамматикам
- •Способы представления синтаксиса языка. Задание бесконечного текста конечными средствами. Проблема разбора. Классификация языков
- •3.2. Сканеры (лексические анализаторы)
- •3.2.1. Автоматные грамматики и диаграмма состояний
- •Регулярные выражения и конечные автоматы
- •Недетерминированные конечные автоматы
- •3.3. Грамматики простого предшествования
- •3.3.1. Простые предшествования.
- •Отношения предшествования и их вычисление
- •Операторное предшествование
- •Вычисление отношений операторного предшествования. Алгоритм разбора на основе операторного предшествования
- •3.3.5. Предшествование более высокого порядка
- •3.3.6. Способ представления грамматики в оп
- •3.3.7. Предшествование более высокого порядка
- •3.3.8. Ограниченный контекст
- •Определение 1:1 ограниченного контекстного распознавателя
- •Алгоритм 1:1 ограниченного контекстного преобразователя
- •Примеры разбора цепочек по алгоритму 1:1 ограниченного контекстного преобразователя
- •Определение m: n - ограниченного контекста
- •3.4. Автоматы с магазинной памятью, [ мп-автомат ]
- •Операции над магазином:
- •Операции над состоянием:
- •Операции над входной цепочкой:
- •Автомат задаётся:
- •Варианты мп-автоматов (доопределение)
- •Эквивалентность мп-автоматов и кс-грамматик
- •Мп, работающий снизу вверх
- •Формальное определение для левой свертки
- •Восходящий распознаватель
- •Детерминированный мп-автомат
- •Проблема зацикливания
- •3.4.1. Общие методы синтаксического анализа.
- •Вопросы для самопроверки
- •Нисходящий разбор
- •Нисходящий преобразователь (распознаватель)
- •Моделирование мп –преобразователя. Нисходящий анализ с возвратом Синтез процедуры
- •Нисходящий разбор в терминах грамматик
- •Алгоритм нисходящего разбора
- •Пример:
- •Алгоритм восходящего разбора
- •3.4.2. Польская запись, тетрады, триады, деревья.
- •Перевод индексной записи в тетрады
- •3.5. Теория перевода
- •3.5.1. Формализмы определения перевода
- •3.5.2. Синтаксически управляемый перевод
- •3.5.3. Конечные преобразователи. (Простейший транслятор)
- •3.5.4. Преобразователи с магазинной памятью
- •Лабораторная работа №7 Поиск основы в грамматиках простого предшествования
- •5. Контроль знаний
- •Глоссарий
Глоссарий
Алфавит- это любое множество символов.
Грамматика - алфавит и совокупность правил формализующих построение цепочек языка.
Грамматика простого предшествования – это грамматика, при которой между двумя любыми символами из словаря определено не более чем одно отношение и ни у каких двух правил нет одинаковых правых частей.
Грамматика операторного предшествования – это такая грамматика, где отношения рассматриваются между операторами (терминальными символами).
Грамматика m,n предшествования – это такая грамматика, которая удовлетворяет условиям: 1) все правые части правил единственны; 2) для любой пары цепочек xy таких, что |x| = m; |y| = n, выполняется не более одного из трех рассмотренных выше отношений
Имя куста – это нетерминальный символ.
Итерация – это сцепление произвольного числа цепочек языка.
Куст символа – это множество подчинённых ему символов.
Левосторонний вывод – это такой вывод, при котором на каждом шаге заменяется самый левый символ.
Начальный символ – это 1) общая запись всех возможных конструкций языка, построенных из элементов данного алфавита по определенным правилам, образующим систему правил; 2) искусственно введенный в грамматику символ, предназначенный для формализации процедуры разбора предложения.
Нетерминальные символы – это символы, из которых возможен дальнейший вывод цепочки.
Основа – это самая левая простая фраза.
Первичная фраза сентенциальной формы - это такая фраза, в которую входит, по крайней мере, один терминал и сама она не содержит других первичных фраз.
Переменные – это последовательности знаков, заключенные в скобки <>.
Правосторонний вывод - это такой вывод, при котором на каждом шаге заменяется самый правый символ.
Предложение – это сентенциальная форма, которая содержит только терминальные символы.
Простая фраза – это высказывание, выводимое за один шаг.
Пустая цепочка – это цепочка, не содержащая ни одного символа.
Сентенциальная форма – любое высказывание, выводимое из начального символ, которое может содержать как терминальные, так и нетерминальные символы.
Синтаксическое дерево- это граф без контуров и петель, где корневой вершине поставлен в соответствие начальный символ.
Сканер - это та часть транслятора, которая читает литеры исходной программы и строит из них слова.
Терминальные символы – это символы, из которых нет дальнейшего вывода.
Фраза – это высказывание, выводимое за несколько шагов.
Цепочка – это последовательность символов алфавита.
Язык - это система дискретных звуков, необходимая для описания внешнего мира.
Язык в алфавите S - множество цепочек, состоящих из элементов этого алфавита.
(*)(*)в этой ситуации автомат может воспользоваться вторым правилом: он может либо разгрузить, либо перейти в состояние сравнения. Если он перейдёт в состояние сравнения, то цепочка принята не будет, так как входная цепочка не пуста, следовательно нужно перейти в состояние загрузки
(**)(**)на данном шаге переходим в состояние сравнения, иначе магазин будет не пуст и цепочка принята не будет.