Вопрос 27. Магазинный автомат. Детерминированный и недетерминированный магазинный автомат. Теорема о магазинном автомате и КС-языках.
СП- не является автоматом типа 1
Магазинный автомат –(М ) – совокупность пяти (шести ) объектов М=<A,Q,S,P,I,(B)>
A- конечный входной алфавит
Q- множество состояний
P- система комманд магазинного автомата
S — конечный стековый алфавит
B- выходной алфавит
Р : Q*S*A-> Q*S*
P={qi sj a n -> qi’ s’ }
I=qi a – начальное состояние и строка состояния стека в начальный момент времени .
Множство принимаемых строк (М) – если задан М =<A,Q,S,P,I> то можно говорить о множестве Х которое состоит из строк входного алфавита приподаче на вход которых автомат в начальном состоянии (конфигурации) прейдет в некоторое заключительное состоянии Х ?А* I= q, ? , K =q0? ?,??S* ? ? ?X I= q,? => K=q0?
Автоматное (магазинное отображение ) М(Х) =Y , Y?B*
Теорема (о КС- грамматиках и магазинных автоматах )
Для любого языка порождаемого КС – грамматикой существует магазинный автомат (возможно недетерминированный ) такой , что его множество принимаемых строк совпдает с этим языком . Верно и обратное . Если L(M) язык принимаемый некоторым магазинным автоматом то этот язык может быть порожден КС- грамматикой
Докозательство :
А) ? G2 ? M=<A,Q,S,P,I> ? L(G2)=L(M)
пусть L(G2) ? A* (V=A) G=<V,W,PG,IG >
определим М =<V,{ q0,q1 } , S=VU WUU{*} ,P, I=q1Ig*>
P= { q1Ae-> q1? для всех продукций (А-> ?)?PG
q1aa -> q1 e для всех а ?V
q1*e -> q0e
Магазинный автомат М :
а) удаляем из входной очереди и вершины стека совпадающие терминальные знаки
б) самый левый нетерминальный знак (нах-ся на вершине стека ) заменяется на строку соответсвующим образом (1)
в) таким образом в стеке порождается некоторая строка языка L(G2) и при ее наличии во входной очереди автомат останавливется (3) В этом случае стек исчерпан , автомат находится в закдючительном состоянии q0 и из входной очереди удалена порожденная строка .
г) тк грамматика может содержать не одну продукцию раскрывающую некоторый нетерминальный знак А то автомат в общем случае недетерминирован Р –не является функцией
д) то магазинный автоамат М принимает все строки L(G2) и не принимает ни одной строки языку не принадлежащей
Б) (обратная теорема )
1 Пусть задан М=<A,Q,S,P,I> построим КС- грамматику G2 порождающий язык принимаемый автоматом М
2 поставим в соответствие каждому знаку стекового алфавита S , такой нетерминальный знак Аi j ?W
что из них может быть выведены строки в результате ввода которых автомат переходит из состояния qi в qj
3множество продукций PG зададим следующим образом
а) переименуем заключительное состояние автомата из q0 в qn
б) зададим W={ Aij ! Aij ? S , i <= j , j<=n }
в) добавим в множество PG продукции
— если имеется в Р команда qi A a -> q j A(1)A(2)……A(k) A(s)?S 1<=S<=k то в PG добавим
Aij -> a A(1)i n1 A(2) n1n2 ….. A(k) nk-1 j ?ns 1<=n <=n2 ….<=nk-1 <n
В PG добавляется продукции описывающие строение принимаемых автоматом при переходе из состояния
qi в состояние qj след обр эта строка может быть получена путем конкатенации строк которые принимает автомат припереходе из состояния i В состояние n , когда из стека извлекается А (1) при переходе из n1 в n2 когда из стека извлекается знак А (2) и так далее и при переходе из состояния nk-1 в состояние j когда из стека извлекается знак А(к) при всевозможных значениях n1, n2,……nk-1
q1 A a -> q2 A(1)
и если автоматимеет команду qi A a _> q j e то в PG добавляется продукция Аij -> a
г) аксиомой грамматики обьявим IG=A1n или если их нсколько IG->A(s)1n
A(s)1n – обозначает множество строк которые принимает автомат рпи извлечении из стека некоторого знака стекового алфавита в результате чего он переходит из начального состояния (1) в заключительное состояния (n)
4 очевидно , что построенная грамматика является КС и порождает тот же язык , что принимается магазинным автоматом (видно из построения )
Вопрос 28. Дерево грамматического разбора. Семантическое дерево. Синтаксический анализ и компиляция.
Синтаксический анализ — это процесс распознавания строки на принадлежность языку заданному граматикой. Состоит из построения древа грамматического разбора и семантического дерева.
Дерево трамматического разбора: (при семантическом анализе проверяются дополнительные условия, которые накладываются на строки языка) Лексемой наз. терменальный знак языка (++,>,=,идентификатор,константа)
Дерево грамматического разбора(синтаксическое дерево) — это: 1. форма представления вывода заданной строки в грамматике. 2. определяет последовательность применения продукций, в результате которых может быть полцчена заданная строка. 3. задает структуру строки в виде последоательностей понятий, ее состовляющих.
Семантическое дерево — это: 1. форма представления строки языка, определяемая последовательностью продукций, необходимых для ее вывода. 2. определяет порядок интерпретации терменальных знаков.
Вопрос 29. Методы синтаксического анализа. Грамматический разбор сверху-вниз и снизу-вверх.
В магазине в начале работы автомата находится аксиома грамматики, а система комманд реализует продукции грамматики. Терменальные знаки в магазине и во входной очереди удаляются.
Вопрос 30. Теорема о LL(k) — грамматиках
Произвольная приведенная Кс грамматика явл. LL(k) грамматикой, если для любой пары продукций вида А->альфа*бетта А->альфа*гамма имеющие одинаковые части, справедливо утверждение: Hk(A->бетта)пересечение headk(A->гамма)=0со звездочкой,где альфа, бетта,гамма принадлежат пересечению V и W,А принадлежит W. (*)
Замечание: для однозначности определения конца строки,рассмотренная
грамматика пополняется.
Док-во: Очевидно, что функция head определяет мн-во строк, длинной не более k, которые могут находится во входной очереди автомата, когда применима продукция, явл. аргументом множества head (это видно из определения head мн-ва). Следовательно, если различные продукции с одинаковой левой частью имеют пересекающиеся head мн-ва, то рассматриваемая грамматика неоднозначна и существует подстрока во входной очереди, для которой нельзя решить, какую продукцию применять. В связи с тем, что можно отложить принятие решения о выборе продукций, имеющих общий префикс в правой части(альфа), до распознования строки, порождаемой этим префиксом (А->альфа), то выражение * справедливо, если грамматика явл. LL(k) грамматикой.
Вопрос 31. Грамматический разбор «снизу-вверх» .LR(k)-грамматики.
Вообще, дерево грамматического разбора (синтаксическое дерево ) -это:
1)форма представления вывода заданной строки в грамматике
2)Определяет последовательность применения продукций , в результате которых может быть получена заданная строка
3)Задает структуру строки в виде последовательностей понятий , ее составляющих.
Грамматический разбор «снизу-вверх» осуществляется следующим образом: в начале работы магазин пуст . из входной очереди читаются знаки , которые направляются в стек. Система команд автомата реализует редукциооную грамматику альфа->A ,где альфа-строка из символов терминального и нетерминального алфавитов , А-знак нетерминального алфавита. Анализ завершается успешно, если в стеке остается лишь аксиома грамматики.
Например: I->c# C->bA | aB A->a | aC B->b | bC
A S D
________________________________
#abba e нач. состояние
#abb a сдвиг
#ab ba сдвиг
#a bba сдвиг
# abba сдвиг
# Abba приведение
# Cba приведение
# Ba приведение
# C приведение
e #C сдвиг
e I приведение
Для решения проблемы Эффективности синтаксического анализа необходимо ограничить класс грамматик , которые подлежат реализации , грамматиками допускающим реализацию синтаксического анализа детерминированным автоматом. Класс языков, распознаваемых детерминированным автоматом состоит изыков , порождаемых LL(k) и LR(k) грамматиками.
Вопрос 32. Лемма (3.3) о правостороннем (левостороннем )выводе.
Любая строка языка , порождаемого КС-грамматикой может быть получена в результате левостороннего (правостороннего) выода.Определение: Левосторонним выводом для грамматики G=<V,W,P,I> называется такой вывод ,когда в сентенциальной форме, получаемой из аксиомы путем применения продукций , заменяется самый левый (правый) нетерминальный знак .
Пример : I->aAbB A->bA | a B->aB | b берем аксиому и выполняем левосторонний вывод : I->aAbB->abAbB->ababB->ababb Правосторонний вывод: I->aAbB->aAbb->ababb Возможен также чередующийся вывод.
