- •Автор: старший преподаватель кафедры Прикладной Математики и Информатики им. Ю.В.Кожевникова Сергей Викторович Сотников.
- •2.3. Общие методы синтаксического анализа 81
- •1. Класс контекстно-свободных языков (V-3.0 28.02.2009)
- •1.1. Свойства кс-языков
- •1.1.1. Теорема Огдена. Лемма о разрастании кс-языков
- •1.2. Приведение кс-грамматик
- •1.2.5. Удаление цепных правил
- •Удаление недостижимых символов;
- •Удаление бесплодных (бесполезных) символов;
- •Удаление цепных правил;
- •1.2.5.1. Алгоритм удаления цепных правил
- •1.3. Нормализация грамматик (Приведение кс-грамматик к нормальной форме)
- •1.3.1.1. Алгоритм преобразования к нормальной форме Хомского
- •1.3.2.1. Устранение левой (правой) рекурсии
- •1.3.2.1.1. Алгоритм устранения левой рекурсии
- •1.3.2.2. Преобразование нелеворекурсивной приведенной кс-грамматики к нормальной форме Грейбах
- •1.3.2.2.1. Алгоритм преобразования нелеворекурсивной приведенной кс-грамматики к нормальной форме Грейбах
- •1.3.2.3. Другой способ преобразования кс-грамматики к нормальной форме Грейбах (Метод Розенкранца)
- •1.3.2.3.1. Алгоритм метода Розенкранца
- •1.4. Автоматы с магазинной памятью (mп-автоматы)
- •1.5. Соотношения между различными мп-автоматами
- •1.5.1. Алгоритм построения мп-автомата по расширенному мп-автомату
- •1.5.2. Алгоритм построения расширенного мп-автомата по мп-автомату
- •1.5.3.1. Алгоритм построения по мп-автомату мп-автомата, допускающего цепочки опустошением магазина
- •1.5.3.1. Алгоритм построения мп-автомата по мп-автомату, допускающего цепочки опустошением магазина
- •1.6. Эквивалентность мп-автоматов и кс-грамматик
- •1.6.1. Алгоритм построения мп-автомата по произвольной кс-грамматике
- •1.6.2. Алгоритм построения расширенного мп-автомата по произвольной кс-грамматике
- •1.6.3. Алгоритм построения кс-грамматики для произвольного мп-автомата
- •1.6.4. Алгоритм построения кс-грамматики для произвольного расширенного мп-автомата
- •2. Методы трансляции
- •2.1. Теория перевода
- •2.1.1. Формализмы, используемые для определения перевода
- •2.1.1.1. Перевод и семантика
- •2.1.1.2. Схемы синтаксически управляемого перевода ( су-схемы)
- •2.1.1.3. Конечные преобразователи
- •2.1.1.4. Преобразователь с магазинной памятью
- •2.1.1.5. Эквивалентность простых су-схем и преобразователей с магазинной памятью
- •2.1.1.5.1. Алгоритм построения мп-преобразователя для простой су-схемы
- •2.1.1.5.2. Алгоритм построения простой су-схемы по мп-преобразователю
- •2.1.2. Лексический анализ
- •2.1.2.1. Непрямой лексический анализ
- •2.1.2.2. Прямой лексический анализ
- •2.1.2.3. Программное моделирование конечных преобразователей
- •2.1.3. Синтаксический анализ
- •2.1.3.1. Определение разбора
- •2.2. Общие методы синтаксического анализа
- •2.2.1. Синтаксический анализ с возвратами
- •2.2.1.1. Алгоритм нисходящего разбора с возвратами
- •2.2.1.2. Проблемы алгоритм нисходящего разбора с возвратами
- •2.2.1.3. Алгоритм восходящего разбора с возвратами
- •Синтаксический анализ с возвратами
- •2.3. Общие методы синтаксического анализа универсальные методы синтаксического анализа. Табличные методы синтаксического анализа Алгоритм Кока-Янгера-Касами
- •Алгоритм разбора Кока-Янгера-Касами
- •Алгоритм нахождения левого разбора по таблице разбора
- •Алгоритм Эрли
- •Алгоритм разбора Эрли
- •Алгоритм построения правого разбора по списку разбора
1.5.2. Алгоритм построения расширенного мп-автомата по мп-автомату
Вход: - МП-автомат.
Выход:
- расширенный МП-автомат.
Метод:
Идея метода: МП-автомат по определению является расширенным !!!
Домашнее задание: Самостоятельно рассмотреть алгоритм построения расширенного МП-автомата по МП-автомату.
1.5.3. МП-автоматы, опустошающие магазин
Рассмотрим МП-автоматы, которые могут по входным цепочкам опустошать магазин.
Определение: Пусть
- МП-автомат. Будем говорить, что
допускает
цепочку
опустошением магазина,
если
для некоторого
.
Пусть
- множество цепочек, допускаемым автоматом
опустошением магазина.
Лемма: Для любого МП-автомата можно построить МП-автомат, допускающий цепочки опустошением магазина и наоборот.
1.5.3.1. Алгоритм построения по мп-автомату мп-автомата, допускающего цепочки опустошением магазина
Вход: - МП-автомат.
Выход:
- МП-автомат, допускающий цепочки
опустошением магазина такой, что
Метод:
Идея метода:
Пусть
моделирует
.
Всякий раз, когда
переходит в заключительное состояние,
решает, продолжать ли моделирование
или перейти в специальное состояние
,
которое опустошит магазин. Но есть одно
осложнение. Для некоторой входной
цепочки
автомат
может сделать последовательность
тактов, приводящую к опустошению
магазина, а управляющее устройство
окажется при этом не в заключительном
состоянии. Тогда для того, чтобы помешать
допустить в этом случае цепочку
,
добавим к
специальный маркер, отмечающий дно
магазина, который автомат
может устранить только в состоянии
.
Формально положим
,
где соответствующие элементы определяются
следующим образом:
- множество
состояний результирующего МП-автомата;- входной алфавит результирующего автомата;
- начальный символ магазина результирующего автомата;
- алфавит магазинных символов автомата ;
- начальное
состояние автомата
;
- множество
заключительных состояний автомата
;
Примечание. Для МП-автомата, допускающего язык опустошением магазина, множество заключительных состояний обычно берется пустым. Его, очевидно, можно сделать каким угодно, т.к. МП-автомат заканчивает работу при опустошении магазина.
Определим множество
результирующего МП-автомата
следующим образом:Если множество содержит переход вида
,
то
будет содержать
для
,
,
;Добавим переход вида
,
то есть на первом такте автомат
записывает в магазин
и переходит в начальное состояние
автомата
(
играет роль маркера, отмечающего дно
магазина);Добавим переход вида
для
,
;Добавим переход вида
для
.
Пример :
Для МП-автомата из примера :
построить эквивалентный МП-автомат , допускающий цепочки опустошением магазина;
построить последовательность тактов работы построенного МП-автомата для цепочек , ;
сравнить полученный МП-автомат и последовательность тактов работы МП-автомата с МП-автоматом и последовательностью тактов работы МП-автомата из примера .
Решение:
МП-автомат имеет вид
где функции перехода следующие
;
;
;
;
;
.
Построим эквивалентный МП-автомат . Здесь каждый элемент примет соответственно следующий вид
Множество состояний результирующего автомата будет иметь вид
;Входной алфавит символов результирующего автомата совпадает с входным алфавитом исходного автомата, т.е.
;Алфавит магазинных символов автомата будет следующим
;- начальный символ магазина результирующего автомата;
- начальное состояние автомата ;
- множество заключительных состояний автомата ;
Определим множество результирующего автомата следующим образом:
Добавим в множество переходы вида
,
,
,
,
,
;
Добавим в множество переход вида
;
Добавим в множество переход вида
,
,
;
Добавим в множество переход вида
,
,
.
Теперь построим последовательность тактов работы автомата для различных цепочек.
Последовательность тактов работы автомата для цепочки будет иметь вид
.
Последовательность тактов работы автомата для цепочки будет иметь вид
.
Делая сравнение МП-автоматов и последовательности тактов, то видно во-первых, МП-автомат, допускающий цепочки опустошением магазина чуть сложнее исходного МП-автомата и гарантирует, что в магазине никаких символов не останется, во-вторых, количество тактов построенного автомата для нетривиальных цепочек (т.е. для непустых) немного больше, чем у исходного.
