Главная >> Реферат >> Информатика

1 2 3

Предсказывающие алгоритмы разбора.

Разбор для LL(k)-грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может «заглядывать» вперед на очередные k символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой (x,Xa,n), где

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

Xa - цепочка в магазине и Х - верхний символ

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

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

{(верхний символ магазина)Х(аванцепочка)}

и множеством

{(правая часть правила и его номер)|ошибка|выброс|допуск}.

Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.

ПРМ:

Пусть дана грамматика с правилами :

  1. SaAS

  2. Sb

  3. Aa

  4. AbSA

Для такой грамматики будет построена таблица:

аванцепочка

a b e

верхний S aAS,1 b,2 ошибка

символ A a,3 bSA,4 ошибка

магазина a выброс ошибка ошибка

b ошибка выброс ошибка

$ ошибка ошибка допуск

По такой таблице будет проведен анализ:

(abbab,S$,e) |-( abbab,aAS$,1)

|-( bbab,AS$,1)

|-( bbab,bSAS$,14)

|-( bab,SAS$,14)

|-( bab,bAS$,142)

|-( ab,AS$,142)

|-( ab,aS$,1423)

|-( b,S$,1423)

|-( b,b$,14232)

|-( e,$,14232)

k- предсказывающий алгоритм разбора КС-грамматики G можно моделировать на детерминированном МП- преобразователе с концевым маркером на входной ленте. Так как входная головка МП- преобразователя может обозреть только один входной символ, аванцепочка должна храниться в конечной памяти управляющего устройства. Остальные детали моделирования очевидны.

ТРМ: Пусть А - k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда существует такой детерминированный МП- преобразователь, который позволяет разобрать любую цепочку из этой грамматики. Иначе говоря можно промоделировать любой алгоритм на указанном преобразователе.

СЛВ: Пусть А - k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда для G существует детерминированный левый анализатор.

Следствия определения LL(k)-грамматики.

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

В определении LL(k)- грамматики утверждается, что для данной выводимой цепочки wAa цепочка w и непосредственно следующие за ней k входных символов однозначно определяют, какое применить правило для развертки нетерминала A. Поэтому на первый взгляд может показаться, что для определения нужного правила надо помнить всю цепочку w. Однако это не так. Докажем теорему, очень важную для понимания LL(k)-грамматик:

ТРМ: КС-грамматика G=(N,E,P,S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил Ab` и Ac` из P пересечение FIRST(b`a`)FIRST(c`a`) пусто для всех таких wAa`, что SwAa`.

ДКВ: Необходимость. Допустим, что w, A, a`, b` и c` удовлетворяют условиям теоремы, а FIRST(b`a`)FIRST(c`a`) содержит x. Тогда по определению FIRST для некоторых y и z найдутся выводы SwAa`wb`a`wxy и SwAa`wc`a`wxz. (Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных терминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k то y = z = e. Так как b` c`, то G не LL(k)- грамматика.

Достаточность. Допустим, что G не LL(k)- грамматика. Тогда найдутся такие два вывода SwAa`wb`a`wx и SwAa`wc`a`wy, что цепочки x и y совпадают в первых k позициях, но b`c`. Поэтому Ab` и Ac` - различные правила из P и каждое из множеств FIRST(b`a`) и FIRST(c`a`) содержит цепочку FIRST(x) совпадающую с FIRST(y). ЧТД.

ПРМ: Грамматика G из правила SaS|a, не будет LL(1)- грамматикой, так как FIRST1(aS)=FIRST1(a)=a. Это можно объяснить так - видя только первый символ цепочки мы не можем определить какое правило необходимо применить (левое или правое). С другой стороны эта грамматика является LL2(k) грамматикой - что вполне очевидно.

ОПР: Пусть G=(N,E,P,S) - КС-грамматика. Определим FOLLOWk(b`) как множество терминальных символов, которые могут встречаться после нетеминала, являющегося аргументом функции.

ТРМ: КС-грамматика G=(N,E,P,S) является LL(1)-грамматикой тогда и только тогда, когда для двух различных правил Ab` и Ac` пересечение FIRST1(b` FOLLOW1(A))FIRST1(c` FOLLOW1(A)) пусто при всех AN. (Без ДКВ).

Теорему можно выразить следующим : по первому символу после нетерминала необходимо выбрать применимое правило - следовательно эти символы различны и пересечение пусто. Эта теорема может применяться к LL(k)- грамматикам, но не всегда выполняться. Грамматики для которых выполняется теорема называются сильными, таким образом все LL(1) грамматики - сильные. Необходимо так же заметить что каждая LL(k)- грамматика однозначна, поэтому если имеется неоднозначная грамматика - то она не LL(k). Имеется неразрешимая проблема распознавания, существует ли для данной КС-грамматики G, не являющейся LL(k), эквивалентная ей LL(k)- грамматика. Однако в ряде случаев такое преобразование возможно. Применяется два способа:

Первый способ - устранение левой рекурсии.

ПРМ: Пусть G - грамматика SSa|b которая не является LL- грамматикой. Заменим правила на следующие:

S bS`

S`aS`|e

получив при этом эквивалентную LL(1)- грамматику.

Другой способ - левая факторизация.

ПРМ: Рассмотрим LL(2)- грамматику G с двумя правилами SaS|a. В этих двух правилах «вынесем влево за скобки» символ a, записав их в виде Sa(S|e). Иными словами, мы считаем что операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти правила на :

SaA

AS|e

тем самым получим эквивалентную LL(1)-грамматику.

Разбор для LL(1)- грамматик.

1 2 3

Похожие работы: