- •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. Контроль знаний
- •Глоссарий
Моделирование мп –преобразователя. Нисходящий анализ с возвратом Синтез процедуры
Пусть есть грамматика с правилами:
S:=aSbS;
S:=aS;
S:=c.
Рассмотрим цепочку aacbc и запишем для нее функцию отбражения:
1. d (q, e, SZ) = (q, aSbS, 1); Группу 1.,2. можно заменить на:
2. d (q, e, SZ) = (q, aS, 2); d (q, e, SZ) = (q, SbS, 1);
3. d (q, e, SZ) = (q, c, 3); d (q, e, SZ) = (q, S, 2).
d (q, i, iZ) = (q, Z, e).
Один из способов нахождения всех разборов входной цепочки состоит в определении всех допускающих конфигураций, достижимых из С0.
Прослеживая левую ветвь, видим, что заключительная конфигурация С6 не является допускающей. Чтобы определить, существует ли другая допускающая конфигурация, необходимо сделать возврат по дереву, пока не встретится конфигурация, для которой возможен еще не рассмотренный выбор очередного такта. Так как в вершине С6 других выборов нет, то необходимо выполнить возврат до вершины С1. Вершина С9 является завершением альтернативной ветви для рассмотренной вершины, она допускающая.
Если важен факт принадлежности цепочки данной грамматике, следует вернуться к вершине С0 и перепробовать оставшиеся конфигурации. Если исследуемая цепочка построена неверно, то придется рассмотреть все конфигурации и выдать сообщение об ошибке.
Нисходящий разбор в терминах грамматик
Будем использовать входной указатель, который в начальный момент времени указывает на самый левый символ рассматриваемой цепочки. Процесс начнем с корня. Вершина, которую мы рассматриваем в данный момент, – активная. Если активная вершина помечена некоторым нетерминалом «А», нужно выбрать первую его альтернативу. (Пусть A:=x1…xk) К вершине А добавить к прямых потомков и сделать активной вершину х1 (самую левую). Если активная вершина помечена терминалом, нужно сравнить с ним текущий входной символ и сделать активной вершину справа от нее, а также сдвинуть входной указатель на одну позицию вправо. Если этот терминал не совпадает с текущим входным символом, нужно вернуться к вершине, где было использовано предыдущее правило.
Если альтернатив больше нет, нужно вернуться к следующей предыдущей вершине. Таким образом, предпринимается попытка сохранить совместимость строящегося дерева с входной цепочкой.
Начало: первая активная вершина – корень дерева (S). Правила занумерованы (альтернативы нетерминала). В соответствии с установленным порядком выбираемая альтернатива в данном случае 1.Входной указатель стоит на первом символе исследуемой цепочки. В рассматриваемом случае активная вершина – терминал.
Осуществляется сравнение с символом во входной цепочке, который помечен указателем. Имеет место совпадение. Передвинуть указатель вправо на одну позицию. Активной становится вершина S (первая справа от проанализированного нетерминала а).
Снова используется альтернатива 1. Активный символ - терминал (а) совпадает с символом, который помечен указателем. Передвигаем указатель вправо. Активная вершина S. У первых двух альтернатив первый терминал не совпадает с символом, который помечен указателем. Испытывается 3-я альтернатива. Передвинуть указатель. Активная вершина – вершина, помеченная терминальным символом (b). Сравнить и передвинуть указатель. Активная вершина – вершина справа от b. Используем альтернативу 3. Вершины совпадают, входная цепочка прочитана. Однако в дереве остались 2 неиспользованных вершины. Последовательность используемых правил не позволила констатировать факт принадлежности рассматриваемой цепочки к данной грамматике.
Осуществить возврат по дереву до вершины, у которой имеется не опробованная альтернатива.
Вернуть указатель к следующему символу входной цепочки и использовать альтернативу 2, у которой активной вершиной является терминал а. Сравнить первый символ с указателем. Передвинуть указатель и активизировать справа от а.