- •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. Контроль знаний
- •Глоссарий
Примеры разбора цепочек по алгоритму 1:1 ограниченного контекстного преобразователя
Пример №1. Задана цепочка: #a0011#.
Шаг№1.
а) Считываем символ цепочки в переменную R:
R=#.
б) Увеличиваем переменную i на единицу:
i=1.
в) Проверяем совпадение с таблицей - совпадений нет.
г) Переносим символ из переменной R в стек STK:
STK=#.
Шаг№2.
а) Считываем символ цепочки в переменную R:
R=a.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а.
Шаг№3.
а) Считываем символ цепочки в переменную R:
R=0.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а0.
Шаг№4.
а) Считываем символ цепочки в переменную R:
R=0.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а00.
Шаг№5.
а) Считываем символ цепочки в переменную R:
R=1.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а001.
Шаг№6.
а) Считываем символ цепочки в переменную R:
R=1.
б) Проверяем совпадение с таблицей - совпадение есть.
в) Производим замену верхней части стека по правилам:
STK=#а0W.
г) Проверяем совпадение с таблицей - совпадений нет.
д) Переносим символ из переменной R в стек STK:
STK=#а0W1.
Шаг№7.
а) Считываем символ цепочки в переменную R:
R=#.
б) Увеличиваем переменную i на единицу:
i=2.
в) Проверяем совпадение с таблицей - совпадение есть.
г) Производим замену верхней части стека по правилам:
STK=#аW.
д) Проверяем совпадение с таблицей – совпадения есть.
е) Производим замену верхней части стека по правилам:
STK=#Z.
ж) Проверяем совпадение с таблицей – совпадений нет.
з) Переносим символ из переменной R в стек STK:
STK=#Z#.
и) Так как i=2 и в стеке содержится #Z#, то делаем вывод, что
цепочка построена по правилам.
Пример №2. Задана цепочка: #a001#
Шаг№1.
а) Считываем символ цепочки в переменную R:
R=#.
б) Увеличиваем переменную i на единицу:
i=1.
в) Проверяем совпадение с таблицей - совпадений нет.
г) Переносим символ из переменной R в стек STK:
STK=#.
Шаг№2.
а) Считываем символ цепочки в переменную R:
R=a.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а.
Шаг№3.
а) Считываем символ цепочки в переменную R:
R=0.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а0.
Шаг№4.
а) Считываем символ цепочки в переменную R:
R=0.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а00.
Шаг№5.
а) Считываем символ цепочки в переменную R:
R=1.
б) Проверяем совпадение с таблицей - совпадений нет.
в) Переносим символ из переменной R в стек STK:
STK=#а001.
Шаг№6.
а) Считываем символ цепочки в переменную R:
R=#.
б) Увеличиваем переменную i на единицу:
i=2.
в) Проверяем совпадение с таблицей – совпадений нет.
г) Переносим символ из переменной R в стек STK:
STK=#а001#.
д) Так как i=2 и в стеке не содержится #Z#, то делаем вывод, что
цепочка построена неверно.