Реферат: Проектирование трансляторов
LR(1)-анализатора. Входит в класс несущественно неоднозначных
УКС-языков.
Функции b1 и b2 обычно задаются в виде общей таблицы, сос-
тоящей из конечного числа "рядов". Каждый ряд соответствуют неко-
торому состоянию и имеет следующую структуру:
- состояние;
- наблюдаемая цепочка;
- функция действия (b1);
- символ нижнего м-на;
- функция b2 (переходное состояние). Для заключительного
состояния Sr имеется сл. строка:
- состояние Sr;
- наблюдаемая цепочка - ##### - k раз - маркеры Z0;
- функция действия (b1) - допуск;
- символ нижнего м-на;
- функция b2 (переходное состояние). Таблица наз. анализи-
рующей таблицей LR(k)-анализатора.
┌──────────┬───────────────────┬─────┬───────────────┬──────┐
│ │ k │ │ │ │
│ U │ X │ b1 │ H │ b2 │
│ Состояние│ Наблюдаемая строка│ │ Символ нижнего│ │
│ │ │ │ магазина │ │
├──────────┼───────────────────┼─────┼───────────────┼──────┤
│ │ Xi1 │(p,A)│ Zi1 │ Si1 │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ Xi2 │ Q │ Zi2 │ Si2 │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ ... │(p,B)│ ... │ ... │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ Xij │ Q │ Zij │ Sij │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ ... │ ... │ ... │ ... │
└──────────┴───────────────────┴─────┴───────────────┴──────┘
LR(k)-грамматики образут широкий класс грамматик, анализи-
руемых естественным образом снизу вверх с помощью ДМП-автомата.
Пусть ах - правовыводимая цепочка какой-то грамматики при-
чем а - либо пустая цепочка либо оканчивается нетерминалом. Тог-
да а называется открытой частью цепочки ах , х - замкнутой. Гра-
ницу между а и х назовем рубежом.
Алгоритм разбора типа "перенос-свертка" можно рассматривать
как программу расширенного ДМП-преобразователя который проводит
разбор "снизу-вверх". Для данной входной цепочки W ДМП-преобразо-
ватель смоделирует в обратном порядке ее правый вывод.
S=a(0)=>a(1)=>...=>a(m)=W
Это правый вывод цепочки W. Каждая правовыводимая цепочка
а(i) распределяется в памяти ДМП так, что ее открытая часть хра-
нится в магазине а замкнутая - на входной ленте справа от голов-
ки. Затем ДМП должен локализовать правый конец основы и сделать
свертку. Число принимаемых ДМП решений - два: решения о переносе
и о свертке (по конкретному правилу).
Грамматика будет LR(K) грамматикой, если для произвольного
правого вывода
S=a(0)=>a(1)=>...=>a(m)=Z
в каждой правовыводимой цепочки а(i), читая ее слева напра-
во, можно выделить основу и определить, каким нетерминалом надо
ее заменить, дойдя при этом не более чем до k-го символа, распо-
ложенного справа от правого конца этой основы.
ОПРЕДЕЛЕНИЕ:
Пусть G=(N,E,P,S) - КС грамматика.
Пополненной грамматикой, полученной из G, будем называть
G'=(N+S',E,P+{S'->S},S').
S' - новый начальный символ, не принадлежащий N.
S' -> S - это нулевое правило грамматики G', добавляемое для
того, чтобы свертку , в которой используется нулевое правило,
можно было интерпретировать как сигнал о том, что цепочка допус-
кается.
ОПРЕДЕЛЕНИЕ: пусть G - КС грамматика, а G' - полученная из
нее пополненная. Будем называть G LR(k) грамматикой для k >= 0,
если из условий:
1) S' -> aAw -> abw;
2) S' -> gBx -> aby;
3) FIRST(k;w) = FIRST(k;y) где k соответствует грамматике.
Из условий следует, что
aAy = gBx (т.е. a=g, A=B, x=y)
Интуитивно это определение говорит о том, что если abw и aby
-правовыводимые цепочки пополненной грамматики, у которых
FIRST(w)=FIRST(y), и A->b -последнее правило, использованное в
правом выводе цепочки abw, то правило A->b должно использоваться
также в правом разборе при свертке aby к aAy.
Так как A дает b независимо от w, то LR(k) условие говорит о
том , что в FIRST(w) содержится информация, достаточная для того,
что ab за один шаг выводится из aA. Поэтому никогда не может воз-
никнуть сомнений относительно того, как свернуть очередную право-
выводимую цепочку пополненной грамматики.
Кроме того, работая с LR(k)-грамматикой, мы всегда знаем,
допустить ли данную входную цепочку или продолжать разбор.
Если начальный символ S не встречается в правых частях пра-
вил, то в определении LR(k) грамматики вместо S' можно взять S, а
именно G будет LR-грамматикой, если из трех условий:
1: S=>aAw=>abw;
2: S=>yBx=>aby;
3: FIRST(w)=FIRST(y)
следует, что aAy=yBX.
В данном разделе мы кратко рассмотрим, как для каждой
LR-грамматики G можно построить детерминированный правый анализа-
тор, который ведет себя следующим образом.
Прежде всего, этот анализатор строится по пополненной грам-
матике G'. Ведет он себя также, как анализатор типа "пере-
нос-свертка", за исключением того, что после каждого символа
грамматики в магазин будет записываться специальный информацион-
ный символ, называемый LR(k)-таблицей, которые могут определить,
что нужно делать на очередном шаге-свертку или перенос, и в слу-
чае свертки - номер правила.
┌──────────┬─────────────────────┬──────────────────────┐
│состояния │ действие │ переход │
├──────────┼─────────────────────┼──────────────────────┤
│ │ a b e │ S a b │
│ │ │ │
│ │ │ │
│ T0 │ 2 X 2 │ T1 X X │
│ │ │ │
│ Т1 │ S X A │ X T2 X │
│ │ │ │
│ T2 │ 2 2 X │ T3 X X │
│ │ │ │
│ T3 │ S S X │ X T4 T5│
│ │ │ │
│ T4 │ 2 2 X │ T6 X X │
│ │ │ │
│ T5 │ 1 X 1 │ X X X │
│ │ │ │
│ T6 │ S S X │ X T4 T7│
│ │ │ │
│ T7 │ 1 1 X │ X X X │
└──────────┴─────────────────────┴──────────────────────┘
Рис. LR(1) анализатор для грамматики G (i-свертка,при кото-
рой применено i-е правило, S-перенос, A-допуск, X-ошибка.
Возьмем для примера грамматику G. Ee правила:
1:S->SaSb
2:S->e
и правый вывод S->SaSb->SaSaSbb->SaSabb->Saabb->aabb.
Это LR(1)-грамматика.
Пополненная грамматика состоит G' правил:
0:S'->S
1:S ->SaSb
2:S ->e
LR(1)-анализатор для грамматики G приведен на Рис.
LR(k)-анализатор для КС-грамматики G - это множество строк
большой таблицы, каждая строка которой называется LR(k)-таблицей.
Т0 выделяется в качестве начальной LR(k)-таблицы. Каждая из
таблиц состоит из двух функций - функции действия f и функции пе-
реходов g:
(1) Аргументом функции действия f служит аванцепочка, а
соответствующее значение функции f - один из символов "действий":
перенос, свертка i, ошибка или допуск;
(2) Аргументом функции переходов g служит символ X, принад-
лежащий N+E, а соответствующее значение g(X)-либо имя некоторой
LR(k)-таблицы, либо ошибка.
LR-анализатор ведет себя также, как алгоритм типа "пере-
нос-свертка", используя в процессе работы магазин, входную и вы-
ходную ленты. Вначале магазин содержит начальную таблицу Т0 и ни-
чего больше. На входной ленте находится анализируемая цепочка, а
выходная лента вначале пустая. Если предположить, что надо разоб-
рать входную цепочку aabb ,то начальной конфигурацией анализато-
ра будет (T0,aabb,e). Далее разбор осуществляется по следующему
алгоритму.
LR(k)-алгоритм разбора
Вход. Множество LR(k) таблиц для грамматики G с начальной
таблицей Т0 и входная цепочка z , которую надо разобрать.
Выход. Если z+ L(G), то правый разбор цепочки z в граммати-
ке, в противном случае сигнал об ошибке.
Метод. Выполнять шаги (1) и (2) до тех пор, пока не будет
допущена входная цепочка или не встретится сигнал об ошибке. В
случае допуска цепочка на выходной ленте представляет собой пра-
вый разбор цепочки z.
(1) Определяется аванцепочка u ,состоящая из k очередных
входных символов (или менее чем k символов ,если обрабатывается
конец входной цепочки)
(2) Функция действия f таблицы ,расположенной наверху мага-
зина, применяется к аванцепочке u.
(а) Если f(u) =перенос, то следующий входной символ, скажем
a ,переносится со входа в магазин. К a применяется функция пере-
ходов g верхней таблицы магазина и определяется новая таблица,ко-
торую надо поместиь наверху магазина. После этого вернуться к ша-
гу (1). Если следующего входного символа нет или значение g(a) не
определено, остановиться и выдать сигнал об ошибке.
(б) Если f(u) свертка i и A->a-правило с номером i , то из
верхней части магазина устраняется 2|a| символов и на выходной
ленте записывается номер правила i. Наверху магазина оказывается
тргда новая таблица T', и ее функция переходов применяется к А
для определения следующей таблицы, которую надо поместить навер-
ху магазина. Помещаем А и эту новую таблицу наверху магазина и
переходим к шагу (1).
(в) Если f(u)= ошибка , разбор прекращается (на практике на-
до перейти к процедуре исправления ошибок).
(г) Если f(u) =допуск, остановиться и обьявить цепочку, за-
писанную на выходной ленте, правым разбором первоначальной вход-
ной цепочки.
Конец работы алгоритма.
G является LR -грамматикой тогда и только тогда , когда для
нее можно построить LR(k)-анализатор. Она также будет LR-грамма-
тикой, если просмотрев только часть кроны дерева вывода в этой
грамматике, расположенную слева от данной внутренней вершины, и
часть кроны , выведенную из нее, а также следующие k терми-
нальных символов, можно установить, какое правило было применено
к этой вершине.
Определение. Допустим, что S->aAw->abw- правый вывод в грам-
матике. Назовем цепочку g АКТИВНЫМ ПРЕФИКСОМ грамматики, если
gпрефикс цепочки ab, т.е g- префикс некоторой правовыводимой це-
почки, не выходящие за правый конец ее основы.
Ядро анализатора составляют таблицы. Для LR(k)-грамматики
каждая таблица соответствует некоторому активному префиксу. Таб-
лица, соответствующая активному префиксу g, для данной аванцепоч-
ки. состоящей из k символов, сообщает о том достигнут ли правый-
конец основы. Если да, то она сообщает также какова эта основа и
какое правило надо применить для ее свертки.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
