Конструирование компиляторов

1. Детерминированный нисходящий СА. Устройство LL(1) анализатора. Конфигурация LL(1) анализатора. Структура управляющей таблицы разбора. 1-предсказывающий алгоритм разбора

Детерминированный нисходящий СА - цепочка считывается один раз и процесс разбора полностью детерминирован (в отличие от алгоритмов с возвратом). Это накладывает ограничения на класс грамматик, для которых такой разбор возможен.

Неформальные определения:

LL(k) - грамматики - для которых левый анализатор работает детерминировано, если видит на k символов вперед (то есть если видим следующие k символов, то можем однозначно выбрать подходящее правило выбора).

LR(k) - грамматики-то же самое, только для правого разбора.

Формально:

КС-грамматика называется LL(k) - грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

1)

2)

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

Соответственно, LL(1) - грамматика позволяет просматривать только один символ из входного потока на каждом шаге. LL(1) - анализатор представляет собой магазинный автомат, состоящий из входной ленты, входной головки, магазина, управляющей таблицы и выходной ленты.



При чтении цепочки головка может заглядывать вперед только на один символ u (аванцепочки). В магазине: X - верхний символ магазина, $ - маркер дна. Алфавит магазинных символов обозначается Г.

Конфигурация предсказывающего алгоритма представляется в виде тройки , где

1) x - неиспользованная часть входной цепочки.

2) - цепочка в магазине.

3) - цепочка на выходной ленте.

Работой 1-предсказывающего алгоритма руководит управляющая таблица M, задающая отображение множества в множество, в которое входят:

(1) , где , а i - номер правила ( - или правая часть этого правила, или некоторое его представление). (2) Выброс. (3) Допуск. (4) Ошибка.

1-предсказывающий алгоритм:

На каждом такте считывается символ u и определяется верхний символ магазина Х. Потом рассматривается элемент управляющей таблицы M (u, X), который и подсказывает, что надо делать:

1) М (u, X)= , тогда (верхний символ магазина заменяется цепочкой, а в выход пишется номер правила).

2) М (u, X)=выброс и , тогда (символ в магазине совпал с входным символом - оба символа выбрасываются).

3) М (u, X)=допуск, значит, разбор завершен успешно и мы в конфигурации

4) М (u, X)=ошибка, значит, разбор не получится - выходим.

2. Детерминированный нисходящий СА. LL(1) - условие. LL(1) - условие для грамматик без e-правил. LL(k) - условие для сильно LL(k) - грамматик. LL(k) - условие (общий случай). Проверка LL(k) - условия

Детерминированный нисходящий СА - цепочка считывается один раз и процесс разбора полностью детерминирован (в отличие от алгоритмов с возвратом). Это накладывает ограничения на класс грамматик, для которых такой разбор возможен.

Неформальные определения:

LL(k) - грамматики - для которых левый анализатор работает детерминировано, если видит на k символов вперед (то есть если видим следующие k символов, то можем однозначно выбрать подходящее правило выбора).

LR(k) - грамматики-то же самое, только для правого разбора.

Формально: КС-грамматика называется LL(k) - грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

1)

2)

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

и или и

Неформально: FIRSTk(a) - это множество всех терминальных префиксов длины k (или меньше, если из a выводится цепочка длины < k) терминальных цепочек, выводимых из a.

и , где k - целое число,

Неформально: FOLLOWk(A) - это множество терминалов, которые могут встречаться сразу после А в каких-либо выводимых цепочках. Если А - самый правый символ, то e также включается в FOLLOW.

FIRST и FOLLOW иногда употребляются с аргументами-множествами цепочек (происходит объединение результатов функций для каждого элемента из множества-аргумента).

LL(k) - условие (общий случай):

Грамматика является LL(k) тогда и только тогда, когда для двух ее различных правил и пересечение пусто при всех , выводимых из S.

LL(1) - условие:

Грамматика является LL(1) тогда и только тогда, когда для двух ее различных правил и пересечение пусто при всех A.

LL(1) - условие для грамматик без e-правил:

Множества попарно не пересекаются, где - правые части правил вывода.

LL(k) - условие для сильно LL(k) - грамматик:

Грамматика является сильно LL(k) тогда и только тогда, когда для двух ее различных правил и пересечение пусто. Все LL(1) - сильно LL(k).

Проверка LL(k) условия:

(1) Для каждого нетерминала, имеющего две или более альтернативы, вычислить и существует такая цепочка , что и

(2) Если - различные А-правила, то для каждого вычислить . Если , то грамматика не LL(k), выход. Если для всех , повторить шаг (2) для всех различных пар А-правил.

(3) Повторить шаги (1) и (2) для всех нетерминалов.

(4) Если дошли сюда, значит, грамматика LL(k).

Примечание: - подмножества , тогда операция определяется так: для некоторых либо , если , либо состоит из первых k символов цепочки

3. Детерминированный нисходящий СА. Функции FIRST и FOLLOW и их интерпретация. Алгоритм построения корректной управляющей таблицы для LL(1) - грамматики

Детерминированный нисходящий СА - цепочка считывается один раз и процесс разбора полностью детерминирован (в отличие от алгоритмов с возвратом). Это накладывает ограничения на класс грамматик, для которых такой разбор возможен.

Неформальные определения:

LL(k) - грамматики - для которых левый анализатор работает детерминировано, если видит на k символов вперед (то есть если видим следующие k символов, то можем однозначно выбрать подходящее правило выбора).

LR(k) - грамматики-то же самое, только для правого разбора.

Формально:

КС-грамматика называется LL(k) - грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

1)

2)

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

и или и

Неформально: FIRSTk(a) - это множество всех терминальных префиксов длины k (или меньше, если из a выводится цепочка длины < k) терминальных цепочек, выводимых из a.

и , где k - целое число,

Неформально: FOLLOWk(A) - это множество терминалов, которые могут встречаться сразу после А в каких-либо выводимых цепочках. Если А - самый правый символ, то e также включается в FOLLOW.

Построение корректной управляющей таблицы для LL(1) - грамматики:

Считаем, что $ - маркер дна магазина. Таблица M определяется на множестве следующим образом:

(1). Если - правило грамматики с номером i, то M (A, a)= для всех a!=e, принадлежащих . Если , то M (A, b)= для всех .

(2). M (a, a)=выброс

(3). M($, e)=допуск

(4). В остальных случаях - ошибка

4. Детерминированный нисходящий СА. Функции FIRST и FOLLOW и их интерпретация. Вычисления FIRST для грамматического символа при k=1. Вычисления FOLLOW для нетерминала при k=1. Вычисление FIRST для цепочки символов. Вычисление FIRST для множества цепочек

Детерминированный нисходящий СА - цепочка считывается один раз и процесс разбора полностью детерминирован (в отличие от алгоритмов с возвратом). Это накладывает ограничения на класс грамматик, для которых такой разбор возможен.

Неформальные определения:

LL(k) - грамматики - для которых левый анализатор работает детерминировано, если видит на k символов вперед (то есть если видим следующие k символов, то можем однозначно выбрать подходящее правило выбора).

LR(k) - грамматики-то же самое, только для правого разбора.

Формально:

КС-грамматика называется LL(k) - грамматикой для некоторого фиксированного k, если из существования двух левых выводов:

1)

2)

для которых FIRSTk(x) = FIRSTk(y), вытекает, что .

и или и

Неформально: FIRSTk(a) - это множество всех терминальных префиксов длины k (или меньше, если из a выводится цепочка длины < k) терминальных цепочек, выводимых из a.

и , где k - целое число,

Неформально: FOLLOWk(A) - это множество терминалов, которые могут встречаться сразу после А в каких-либо выводимых цепочках. Если А - самый правый символ, то e также включается в FOLLOW.

Вычисления FIRST для грамматического символа при k=1 (и при всех других k тоже).

(1) Если X - терминал длины меньшей или равной k, то FIRST(X) = {X}

(2) Если есть правило , добавляем e к FIRST(X)

(3) Если есть правило , добавим a в FIRST(X), если для некоторого i и e входит во все множества . Если e входит во все множества , то добавляем e к FIRST(X).

Вычисление FIRST для цепочки символов.

определяется так: добавим к FIRST все не-e символы из . Добавим также все не-e символы из , если . Добавим также все не-e символы из , если и . И т.д.

Вычисление FIRST для множества цепочек.

Объединим множества FIRST для каждой цепочки множества.

Вычисления FOLLOW для нетерминала при k=1 (и при всех других k)

Для всех продукций вида занести в FOLLOW(B) все элементы множества , кроме e. Для всех продукций вида или , где содержит e, все элементы из множества FOLLOW(A) поместить в множество FOLLOW(B). Повторить перечисленные действия, пока ни к одному множеству FOLLOW для нетерминалов нельзя будет добавить ни одного символа.

5. Детерминированный восходящий СА. Устройство LR(1) - анализатора. Конфигурация LR(1) - анализатора. Структура управляющей таблицы разбора. LR(1) - алгоритм разбора

Все определения и алгоритмы даются для LR(k), не проблема перейти к LR(1).

LR(k) - грамматика - для которой можно построить анализатор, осуществляющий детерминированный восходящий анализ, заглядывая на k символов вперед.

Неформально:

Грамматика будет LR(k), если для произвольного правого вывода в каждой промежуточной правовыводимой цепочке, читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя не более чем до k-го символа правее основы.

Формально:

Даны грамматики G и G' (пополненная от G, т.е. с правилом SS'). Тогда если из условий:

(1)

(2)

(3)

следует, что (т.е. ), то грамматика LR(k).

Анализатор LR(1) - детерминированный преобразователь с магазинной памятью, моделирует в обратном порядке правый вывод входной цепочки. Анализатор строится по пополненной грамматике G'. Работает по принципу «перенос-свертка», за исключением того, что после каждого символа грамматики в магазин записывается информационный символ, называемый состоянием анализатора. Таблица синтаксического анализа состоит из двух частей - функции действий action (возвращает (1) перенос s, где s - состояние (2) свертка в соответствии с правилом i (3) допуск (4) ошибка) и функции переходов goto (возвращает новое состояние). Конфигурация анализатора: (а, б, в), где а - содержимое магазина (изначально там состояние ), б - оставшаяся часть входной цепочки, в-выходная лента.

Алгоритм разбора:

Пусть s - состояние на вершине магазина, a - входной символ.

Если action [s, a] = «перенос s'», то поместить в стек a, затем s'; начать снова.

Если action [s, a] = «свертка i: », то снять с магазина символов. Пусть s' - текущее состояние на вершине магазина. Поместить в стек A, затем goto [s', A], вывести на входную ленту i.

Если action [s, a] = «допуск», то конец разбора.

Если ничего из вышеперечисленного, выход с ошибкой.

6. Детерминированный восходящий СА. LR(0) - ситуации. Алгоритм вычисления closure для SLR(1) - грамматик. Алгоритм вычисления goto для SLR(1) - грамматик. Алгоритм построения канонической системы множеств LR(0) - ситуаций. Алгоритм построения SLR(1) - таблиц разбора

Грамматика будет LR(k), если для произвольного правого вывода в каждой промежуточной правовыводимой цепочке, читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя не более чем до k-го символа правее основы.

LR(0) - ситуация - это правило грамматики с точкой в некоторой позиции правой части, например, . Одной продукции может соответствовать несколько ситуаций. Ситуация указывает, какую часть правой части мы уже видим. Приведенный пример означает, что у нас есть строка, порожденная X, и мы ожидаем получить из входного потока строку, порождаемую YZ. LR(0) - ситуация допустима, если для активного префикса , если существует вывод .

Идея SLR-метода - построить детерминированный КА для распознавания активных префиксов; ситуации группируются в множества, которые приводят к состояниям SLR-анализатора.

Функция closure (замыкание) от множества I ситуаций грамматики:

(1) Изначально в closure(I) входят все ситуации из I.

(2) Если входит в closure(I) и - правило грамматики, то добавляем в closure(I) ситуацию (если ее там еще нет). Применяем правило, пока есть что добавлять.

Функция goto (I, X), где I - множество ситуаций, X - символ грамматики. goto (I, X) определяется как замыкание множества ситуаций , принадлежащих I.

Алгоритм построения канонической системы С множеств LR(0) - ситуаций (для расширенной грамматики).

(1) Занесем в С closure от множества ситуаций, состоящего из одной ситуации

(2) Для каждого множества ситуаций I из С и каждого символа X, такого, что goto (I, X) не является пустым и не принадлежит С, добавить к С goto (I, X). Повторять шаг (2), пока есть множества, которые можно добавить к С.

Алгоритм построения SLR(1) - таблиц разбора:

(1) Построим - система множеств LR(0) - ситуаций для грамматики G'

(2) Состояние i строится на основе следующим образом:

(а) Если и , то action [i, a] = «перенос j» (a должен быть терминалом).

(б) Если , то action [i, a] = «свертка » для всех a из FOLLOW(A), причем A не равно S'.

(в) Если , то action [i,$] = «допуск».

Если по этим правилам возникают конфликты, значит, грамматика не SLR(1).

(3) Построение goto: если , то

(4) Все записи, оставшиеся пустыми, определяются как «ошибка».

(5) Начальным состоянием будет состояние, построенное из множества ситуаций, содержащего

Пример:

Расширенная грамматика арифметических выражений:

Каноническая система множеств LR(0) - ситуаций для этой грамматики:

Диаграмма переходов детерминированного конечного автомата для активных префиксов:

Таблица SLR(1) разбора для этой грамматики:

Состояние	action	goto
	Id	+	*	(	)	$	E	T	F
0	П 5			П 4			1	2	3
1		П 6				Д
2		С 2	П 7		С 2	С 2
3		С 4	С 4		С 4	С 4
4	П 5			П 4			8	2	3
5		С 6	С 6		С 6	С 6
6	П 5			П 4				9	3
7	П 5			П 4					10
8		П 6			П 11
9		С 7	П 7		С 1	С 1
10		С 3	С 3		С 3	С 3
11		С 5	С 5		С 5	С 5

7. Детерминированный восходящий СА. LR(1) - ситуации. Алгоритм вычисления closure для LR(1) - грамматик. Алгоритм вычисления goto для LR(1) - грамматик. Алгоритм построения канонической системы множеств LR(1) - ситуаций. Алгоритм построения LR(1) - таблиц разбора

Грамматика будет LR(k), если для произвольного правого вывода в каждой промежуточной правовыводимой цепочке, читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя не более чем до k-го символа правее основы.

LR(1) - ситуация: , где - правило грамматики, a - терминал или маркер конца строки. LR(1) - ситуация допустима для активного префикса , если существует вывод , где и либо a является первым символом w, либо w=e и a=$.

Функция closure (замыкание) от множества I ситуаций грамматики:

Для каждой ситуации , каждого правила и каждого терминала b из , такого, что , добавить в I. Делать все этого, пока есть ситуации, которые можно добавить в I.

Функция goto (I, X), где I - множество ситуаций, X - символ грамматики. goto (I, X) определяется как замыкание множества ситуаций , принадлежащих I.

Алгоритм построения канонической системы С множеств LR(1) - ситуаций (для расширенной грамматики).

(1) Занесем в С closure от множества ситуаций, состоящего из одной ситуации

(2) Для каждого множества ситуаций I из С и каждого символа X, такого, что goto (I, X) не является пустым и не принадлежит С, добавить к С goto (I, X). Повторять шаг (2), пока есть множества, которые можно добавить к С.

Алгоритм построения LR(1) - таблиц разбора:

(1) Построим - система множеств LR(1) - ситуаций для грамматики G'

(2) Состояние i строится на основе следующим образом:

(а) Если и , то action [i, a] = «перенос j» (a должен быть терминалом).

(б) Если , то action [i, a] = «свертка », причем A не равно S'.

(в) Если , то action [i,$] = «допуск».

Если по этим правилам возникают конфликты, значит, грамматика не LR(1).

(3) Построение goto: если , то

(4) Все записи, оставшиеся пустыми, определяются как «ошибка».

(5) Начальным состоянием будет состояние, построенное из множества ситуаций, содержащего

LR-таблица, как правило, содержит на порядок больше строк, чем SLR или LALR.

8. Детерминированный восходящий СА. Ядро множества LR(1) - ситуаций. Алгоритм прямого построения LALR(1) - таблиц разбора

Грамматика будет LR(k), если для произвольного правого вывода в каждой промежуточной правовыводимой цепочке, читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя не более чем до k-го символа правее основы.

LALR=look ahead LR. Часто используется, поскольку таблицы получаются сильно меньше LR.

Ядро множества LR(1) - ситуаций - подмножество этого множества, первые компоненты (до запятой) ситуаций которых совпадают. Если рассматривать систему множеств, то множества с общими ядрами объединяются. Ядро goto (I, X) зависит только от ядра I, так что значения goto объединяемых множеств также объединяются.

Алгоритм прямого построения LALR(1) - таблицы.

(1) Построим - система множеств LR(1) - ситуаций для грамматики G'

(2) Для каждого ядра, имеющегося среди множества LR(1) - ситуаций, находим все множества, имеющие это ядро, и заменяем эти множества их объединением.

(3) Пусть - полученные в результате множества LR(1) - ситуаций. Состояние i строится на основе следующим образом:

(а) Если и , то action [i, a] = «перенос j» (a должен быть терминалом).

(б) Если , то action [i, a] = «свертка », причем A не равно S'.

(в) Если , то action [i,$] = «допуск».

Если по этим правилам возникают конфликты, значит, грамматика не LALR(1).

(4) Построение goto. Если - объединение одного или нескольких множеств LR(1) - ситуаций, то ядра множеств одни и те же, поскольку все I от 1 до k имеют одно ядро. Обозначим через K объединение всех множеств ситуаций, имеющих то же ядро, что и . Тогда goto (J, X)=K.

9 Грамматики предшествования. Отношения предшествования Вирта-Вебера. Грамматики простого предшествования. Алгоритм типа «перенос-свертка» для грамматик простого предшествования

Отношения предшествования Вирта-Вебера

Для всех грамматических символов вводятся отношения (не одинаковы с = > <):

(при разборе с лева на право для цепочки abw)

> - конец основы, выполняется между последним символом цепочки b и первым символом цепочки w;

<. - начало основы, выполняется между последним символом цепочки a и первым символом цепочки b;

=. - выполняется между смежными символами основы.

а) X<.Y: A => бXBb, что есть такие правила B=>+Yy;

б) X.>a: A=>бBYb; B=>+yX; Y=>*ab; (X.>a - всегда терминальный символ с права, так как конец основы)

в) X.=Y если в P есть правило A=>aXYb; XY - основа (элементы, между которыми имеется отношение эквивалентности)

Прим: S-> aSc|bSc|c (правила 1,2,3)



	S	a	b	c	$
S				=
a	=	<	<	<
b	=	<	<	<
c				>	>
$		<	<	<

а) S.=c - есть правило S->aSc (см. в) остальные.= аналогично.

б) a<.a - существует правило S->aSc, если применим правило 1 ещё раз то получим aaSc, как видим a) выполняется.

$<a $<b $<c - по определению ($ <. любого X, если S->+X…), так же можно рассматривать $ и как начальный маркер $aS. $bS. $c

в) с.>c с.>$ обозначают конец основы и дают сигнал к свёртке.

Количество отношений предшествования в ячейке зависит от правил

КС грамматика G=(N, E, P, S) - грамматика предшествования = приведенная (без эпсилон-правил, цепных правил и бесполезных символов) + не более 1 отношения предшествования для любых x, y.

Обратимая гр. Предшествования - гр. простого предшествования

(грамматика обратима = правые части всех правил различны (всегда можно сделать откат))

Алгоритм перенос-свёртка

На каждом шаге алгоритма по состоянию магазина и входной цепочки решается какую операцию сделать - перенос(f) символа в магазин или свёртка(g) символов в магазине. Работу алгоритма можно рассматривать в терминах конфигураций - тройках вида (x, a, p) x - содержимое магазина, a - оставшаяся цепочка, p - цепочка применённых правил. $ - рассматривается как маркер дна магазина / правый концевой маркер

Перенос f (X, a) если X<.a или X.=a

Свёртка f (X, a) если X.>a

Допуск f ($S,$)

В остальных случаях ошибка

	(	a	*	+	)	$
)			>	>	>	>
a			>	>	>	>
*	<	<	>	>	>	>
+	<	<	<	>	>	>
(	<	<	<	<	=
$	<	<	<	<

Пример:

магазин	вход	Выход
$	(a+a)*a
$(	a+a)*a
$(a	+a)*a	6
$(E	+a)*a	6
$(E+	a)*a	6
$(E+a	)*a	6
$(E+E	)*a	66

E->E+E (1)

E->E*E (3)

E->(E) (4)

E->a (6)

(a+a)*a

10. Грамматики предшествования. Грамматики расширенного и слабого предшествования. Алгоритм перехода от обратимой грамматики слабого предшествования к грамматике простого предшествования

Расширенного - происходит анализ в на m символов на лево и n на право (см рис!) -(m, n) предшествование; m, n <= 2, > 2 - редко. Чаще всего используется 2,1 предшествование.



Грамматика (m, n) предшествования = приведенная (без эпсилон-правил, цепных правил и бесполезных символов) и отношения предшествования попарно не пересекаются.

	S	a	b	$
$$		<.
$a	=	<.	=
aS			=
аa	=	<.	=
аb			=
Sb			=
bb			>	>

На каждом шаге анализируем m с лева и n с права. Для всех цепочек выводимых из языка выделяют подцепочки длинной m+n (методом полного перебора к примеру / поиск в глубину).

Прим: S->aSbb|abb (на данном примере в гр. Простого предшествования будет конфликт).

Все цепочки длинны 3 из S: $$$ $S$ $a$ aSb Sbb bb$ $ab abb $$a $aa aaS abb bbb aaa. Подцепочки расчленяются на 2 и 1, и строится отношения Вирта-Вебера. (существует только для 7 случаев)

Нет конфликтов (b<->b).

Грамматики слабого предшествования

Допускается пересечение 2 ух отношений <. и.=. Отношение.> по-прежнему используется для локализации правого конца сворачиваемой основы (для выдачи сигнала о свертке).

Предполагается что грамматика обратимая и кандидатом на свёртку берется самая длинная прав. часть. Примером такой грамматики может послужить:

G: E->E+T|+T|T; T->T*F|F; F->(E)|a.

Для грамматики простого предшествования будет 2 конфликта [(, E) [+, T]

Коррективы вносятся для функции свертки:

g(Xb) = i (i - номер правила) если B->b и не существует такого A->aXb (отношения.>.= и.><. можно устранить за счет грамматич. преобразований).

Теорема: любую грамматику слабого предшествования можно всегда преобразовать в грамматику простого предшествования.

(Это делается введением нового нетерминального символа и правил вывода.)

Прим перехода

E->E+T|+T|T; T->T*F|F; F->(E)|a. (подчеркнутое - кандидаты на замену на новый не терминал)

Алгоритм перехода: вход - обратимая грамматика слабого предшествования G

Допустим нашлись X, Y такие что X.=Y X.<Y, Устраняем из P каждое правило вида A=>aXYb и заменяем на A=>aX[Yb] где [Yb] - новый не терминал. Для каждого правила B->Yb заменяем его на B->[Yb] и все Yb заменяем на [Yb]