- •1.1. Основные понятия
- •1.1.1. Трансляторы, интерпретаторы и компиляторы
- •1.1.2. Стадии работы компилятора
- •1.1.3. Построение компилятора
- •1.2. Определение формальной грамматики и языка
- •1.2.1. Первичные понятия
- •1.3.3. Грамматики типа 2
- •1.3.4. Грамматики типа 3
- •1.3.5. Вывод в КС-грамматиках и правила построения дерева вывода
- •1.3.6. Синтаксический разбор
- •1.3.7. Левый и правый выводы
- •1.3.8. Неоднозначные и эквивалентные грамматики
- •1.4. Способы задания схем грамматик
- •1.4.1. Форма Наура-Бэкуса
- •1.4.2. Итерационная форма
- •1.4.3. Синтаксические диаграммы
- •2. Контекстно-свободные грамматики и автоматы
- •2.1. Приведенные грамматики
- •2.2. Удаление непроизводящих символов
- •2.3. Определение недостижимых символов
- •2.4. Определение бесполезных символов
- •2.5. Исключение леворекурсивных правил
- •2.6. Исключение цепных правил
- •2.7. Преобразование неукорачивающих грамматик
- •2.8. Магазинные автоматы
- •2.9. Работа магазинного автомата
- •2.10. Язык, допускаемый магазинным автоматом
- •2.11. Построение магазинного автомата
- •2.12. Пример построения автомата
- •3. Нисходящие распознаватели
- •3.1. Распознаватели и LL(K) - грамматики
- •3.2. Разделенные грамматики
- •3.3. Построение детерминированного нисходящего распознавателя
- •3.4. Множество выбора
- •3.4.1. Функции ПЕРВ, СЛЕД и множество ВЫБОР
- •3.4.2. Построение функции ПЕРВ(µ)
- •3.4.3. Построение функции СЛЕД(<B>)
- •3.4.4. Построение множества ВЫБОР
- •3.5. Слаборазделенные грамматики
- •3.6. LL(1) - грамматики
- •3.7. Построение магазинного автомата
- •3.8. Преобразование грамматик к виду LL(1)
- •3.8.1. Исключение леворекурсивных правил
- •3.8.2. Выделение общих частей
- •3.9. Восходящие распознаватели
- •4. Методы трансляции
- •4.1. Основные понятия
- •4.2. Синтаксически управляемые схемы
- •4.3. Перевод, определяемый СУ - схемой
- •4.4. Простая СУ – схема
- •4.5. Построение простой СУ - схемы
- •4.6. Транслирующие грамматики
- •4.7. Входная и выходная грамматики заданной транслирующей граммагики
- •4.8. Построение транслирующей грамматики по СУ - схеме
- •4.8.1. Бесскобочные выражения
- •4.8.1.1. Префиксная польская запись (ПрПЗ)
- •4.8.1.2. Вычисление префиксных польских записей
- •4.8.1.3. Постфиксная польская запись
- •4.8.1.4. Вычисление постфиксных записей
- •4.9. Магазинные преобразователи
- •4.9.1. Определение магазинного преобразователя
- •4.9.2. Описание работы магазинного преобразователя
- •4.9.5. Пример построения преобразователя
- •4.9.6. Порядок построения детерминированного магазинного преобразователя
- •5.1. Определение AT-грамматик
- •5.2. Пример АТ-грамматики
- •5.3. Вычисление значений атрибутов с левым выводом
- •5.4. L - атрибутные транслирующие грамматики
- •5.4.1. Форма простого присваивания АТ-грамматик
- •5.4.2. Преобразование LАТ-грамматики в LАТ-грамматику в форме простого присваивания
- •5.4.3. Расширенный вывод для АТ-грамматики
Преобразование можно выполнить следующим образом. Разобьем R на два подмножест-
ва R1 и R2, включая в R1 все правила вида <A> → < B>. Для каждого правила из R1 стро-
ится множество правил S(<A>) следующим образом: если <A> * <A'> и в R2 есть пра-
вило <A'> → α, где α (VT VA)*, то в S(<A>) включается правило <A'> → α. Построим новую схему R' путем объединения правил R2 и всех построенных множеств S(<A>), т.е.
R' = ( S(<A>)) R2. Получим грамматику Г' = { VT , VA , I , R'}, которая эквивалентна заданной и не содержит правил вида <A> → <B>.
В качестве примера исключим цепные правила из грамматики Г1. 9 со схемой:
Г1. 9: R={<E> → <E> + <T> | <T>, <T> → < T> * <F> | <F>, <F> → ( <E> ) | a}.
Вначале разобьем правила грамматики на два подмножества:
R1 = { <E> → <T>,<T> → <F> } ,
R2 = { <E> → <E>+<T>, <T> → <T>*<F>, <F>→ (<E>) | a }
Для каждого правила из R1 построим соответствующие подмножества.
S(<E>) = { <E> →< T>*<F>, <E> → (<E>) | a }, S(<T>) = { <T> → (<E>) | a}
В результате получаем искомую схему грамматики без цепных правил в виде:
R2 S(<E>) S(<T>) = { <E> → <E> + <T> | <T>*<F> | (<E>) | a, <T> → <T>*<F> | (<E>) | a,
<F> → (<E>) | a }
2.7. Преобразование неукорачивающих грамматик
Определение. Правило вида <A> → $ называется аннулирующим правилом а нетерминальный символ <A> - аннулирующим нетерминалом.
Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если схема грамматики не содержит аннулирующих правил, либо схема грамматики содержит только одно правило вида <I> → $, где <I> - начальный символ грамматики, и символ <I> не встречается в правых частях остальных правил грамматики.
18
Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение: для каждой КС-грамматики Г', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).
Построение неукорачивающей грамматики предполагает увеличение числа правил заданной грамматики путем построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть пра-
вило вида <I> → $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I> → $ двумя новыми правилами: <I'> → $ и <I'>→ <I>.
В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:
Г2. 3 : R = { <I> → a<I>b<I>, <I> → b<I>a<I>, <I> → $ }
Выполняя все возможные замены символа <I> в первом правиле грамматики, получаем четыре правила вида:
<I> → a<I>b<I>, <I> → ab<I>, <I>→ a<I>b, <I>→ ab .
Поступая аналогично со вторым правилом, имеем:
<I> → b<I>a<I>, <I> → ba<I>, <I> → b<I>a, <I> → ba.
Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило <I> → $ правилами вида <I'>→ $ и <I'>→ <I>. Построенная совокупность правил образует схему искомой неукорачивающей грамматики.
2.8. Магазинные автоматы
Магазинные автоматы позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке определяется её принадлежность заданному языку. Модель магазинного автомата, состоит из входной лен-
19
ты, устройства управления и вспомогательной ленты, называемой магазином или сте-
ком.
Входная лента разделяется на клетки (позиции) , в каждой из которых может быть записан символ входного алфавита. При этом предполагается, что в неиспользуемых клетках входной ленты расположены пустые символы .
Вспомогательная лента также разделена на клетки, в которых могут располагаться символы магазинного алфавита. Начало вспомогательной ленты называется дном магазина. Связь устройства управления с лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.
Головка входной ленты может перемещаться только в одну сторону - вправо или оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись. Эти операции связаны с перемещением головки определенным образом:
-при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,
-при чтении символ, находящийся против головки считывается с ленты, а затем головка сдвигается на одну позицию вниз. Позицию, находящуюся в рассматриваемый момент времени против головки, называют вершиной магазина.
Определение.Магазинный автомат М определяется следующей совокупностью семи
20
объектов: M={P , S , sо , f , F , H , hо },
где
P - входной алфавит,
S - алфавит состояний, sо - начальное состояние, sо S ,
F - множество конечных состояний (F является подмножеством S),
H - алфавит магазинных символов, записываемых на вспомогательную ленту, hо- маркер дна, он всегда записывается на дно магазина , hо H,
f - функция переходов
f : S x {P {ε}} x H → S x H* ,
если М-автомат - детерминированный, и f: S x {P {ε}} x H → {S x H*},
если М-автомат - недетерминированный.
Функция f отображает тройки (sj, pi, hk ) в пары ( sr, β ) , где β H* и hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и перемещении входной головки.
Имеются также две дополнительные разновидности функций переходов, изменяющих состояние автомата без перемещения входной головки:
1) функция переходов с пустым символом в качестве входного символа: f0(s, ε, h) = (s', β),
которая, независимо от того какой символ находится против читающей головки входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние ав-
томата на s' и записать цепочку β в магазин.
2)функция переходов с определенным входным символом: f*(s, a, h) = (s', β),
которая предписывает изменение состояния и запись цепочки в магазин при условии, что символ a читается входной головкой, а в вершине магазина находится символ h
21