Реферат: Проектирование трансляторов
где:
Q - конечное множество символов состояний, представляющих
всевозможные состояния управляющего устройства;
Х - конечный входной алфавит;
Г - конечный алфавит магазинных символов;
b - отображение множества Q * (X U {e}) * Г в множество ко-
нечных модмножеств множества Q * Г";
q0 C Q - начальное состояние управляющего устройства;
Z0 С Г - символ, находящийся в магазине в начальный момент
(начальный символ);
F C Q - множество заключительных состояний.
ОПРЕДЕЛЕНИЕ: МП-автомат P=(Q,X,Г,b,q0,Z0,F) называется де-
терминированным (сокращенно ДМП-автоматом), если для каждых q C Q
и Z C Г либо
1) b (q,a,Z) содержит не более одного элемента для каждого
а С Х и b (q,e,Z) = 0, либо
2) b (q,a,Z) = 0 для всех а С Х и b (q,e,Z) cодержит не бо-
лее одного элемента.
Утверждение. Любой LR(k) - анализатор может быть преобразо-
ван в детерминированный МП-автомат.
При доказательстве этого утверждения используют свойство
анализатора записывать по одному символу в верхний и нижний мага-
зины. Исключаться из магазина эти символы могут только одновре-
менно и только на этапе свертки, следовательно верхний магазин
может быть исключен, если каждый символ нижнего магазина снаб-
дить индексом. Индекс соответствует тому состоянию, которое запи-
сывается в нижний магазин. Каждый символ нижнего магазина должен
иметь N модификаций, где N - число состояний анализатора, соот-
ветствующих этому символу.
Для любого языка, распознаваемого LR(k)-анализатором, сущес-
твует распознающий этот язык LR(1)-анализатор (класс языков,
распознаваемых LR(k)-анализатором, совпадает с классом языков
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, а
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
