- •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. Расширенный вывод для АТ-грамматики
вают нисходящими распознавателями.
Отметим, что доказательство допустимости цепочки нисходящим магазинным автоматом (НМА) предусматривает поиск подходящей последовательности конфигураций. Такой поиск может существенно увеличить время работы автомата. Детерминированные автоматы работают быстрее, поэтому такие автоматы применяются на практике. Детерминированные автоматы-распознаватели могут быть построены не для всех видов КСграмматик.
Определение. Если язык L допускается детерминированным М-автоматом, то он называ-
ется детерминированным языком.
В дальнейшем будем рассматривать детерминированные автоматы.
3. Нисходящие распознаватели
3.1. Распознаватели и LL(K) - грамматики
Распознаватели можно разделить на два вида: нисходящие и восходящие. Каждый ха-
рактеризуется порядком, в котором располагаются правила в дереве вывода. Нисходящие распознаватели обрабатывают правила сверху вниз, верхние правила раньше нижних, в то время как восходящие распознаватели раньше используют нижние правила.
Рассмотрим нисходящие распознаватели, допускающие языки, порождаемые грамматиками вида LL(K).
Определение. Грамматика относится к классу LL(K) грамматик, если для нее можно построить нисходящий детерминированный распознаватель, учитывающий K входных символов, расположенных справа от текущей входной позиции.
Название LL происходит от слова Left, поскольку анализатор просматривает входную цепочку слева-направо , и слова Leftmost, поскольку он обнаруживает появление правила по одному или группе символов, образующих левый край цепочки. На практике наибольшее применение имеет класс LL(1) грамматик, для которых детерминированный распознаватель работает по одному входному символу, расположенному в текущей позиции.
Рассмотрим построение нисходящих распознавателей для подкласса LL(1) грамматик.
28
3.2. Разделенные грамматики
Определение. Контекстно-свободная грамматика, не содержащая аннулирующих правил, называется разделенной или простой , если выполняются следующие два условия:
1.Правая часть каждого правила начинается терминалом.
2.Если два правила имеют одинаковые левые части, то правые части этих правил должны начинаться различными терминальными символами.
Грамматика, заданная схемой:
Г3. 0: R = {<I> → ab<B>, <I> → b<B>b<I>, <B> →a,
<B> →b<B>},
является разделенной грамматикой, т.к. выполняются условия (1) и (2).
Для каждой разделенной грамматики можно построить детерминированный нисходя-
щий распознаватель.
3.3. Построение детерминированного нисходящего распознавателя
Согласно рассмотренному ранее способу построения распознавателей для КС-грамматик каждому правилу разделенной грамматики, имеющему вид:
<A> → a α, где α - цепочка символов полного словаря и a принадлежит терминальному словарю, ставится в соответствие команда
(*) f0( s0, ε, <A> ) = ( s0, α'a),
которая задает такт работы без сдвига входной головки и в которой α' зеркальное ото-
бражение цепочки α. В результате выполнения этой команды, в вершине магазина будет находиться терминал a. Данный способ построения предусматривает также построение для каждого символа a грамматики команды:
(**)f( s0, a, a ) = ( s0, $ )
которая удаляет этот терминал из магазина и сдвигает входную головку.
Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда
(*) должна выполняться только в том случае, когда под входной головкой находится
29
терминал a, и после нее всегда должна выполняться команда (**).
Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя команды вида (*) и (**) объединяются в одну команду. Построение такой команды выполняется следующим образом: каждому правилу разделенной грамматики
<A> → aα ставится в соответствие команда
f ( s0 , a , <A>) = ( s0 , α ') ,
которая определяет такт работы распознавателя со сдвигом входной головки. Если терминальные символы расположены в правых частях правил не только на самой левой позиции, то для таких терминалов создаются команды вида:
f ( s0, b, b ) = ( s0, $ )
Для перехода в заключительное состояние добавляется правило:
f( s0, $, h0 ) = ( s1, $ ),
ав качестве начальной конфигурации распознавателя используется
( s0, α, h0<I> ),
где <I> - начальный символ грамматики, а α - заданная входная цепочка.
Применяя рассмотренные правила, построим распознаватель для разделенной граммати-
ки Г3. 0.
М 4 : P = { a, b }, H = { a, b, <I>, <B>, h0 }, S = {s0}, F= {s0}, f( s0, a, <I>) = ( s0, <B>b )
f( s0, a, <B>) = ( s0, $ )
f( s0, b, <I> ) = ( s0, <I> b <B> ) f( s0, b, <B> ) = ( s0, <B> )
f( s0, b, b ) = ( s0, $ ) f*( s0, ε, h0 ) = ( s0, $ )
Спомощью построенного автомата проанализируем цепочку bbabab.
( s0, bbababa, h0<I> ) |− ( s0, bababa, h0<I>b<B> ) |−
( s0, ababa, h0<I>b<B> ) |− ( s0, baba, h0<I>b ) |−
( s0, aba, h0<I> ) |− ( s0, ba, h0<B>b ) |− ( s0, a, h0<B> ) |−
( s0, $, h0 ) |− ( s0, $, $ ).
30