27.Класс ll(1) грамматик и их свойства. Критерий принадлежности языка к классу ll(1).
G
называется простой LL(1) гр-ой, если для
любого
все
его альтернативные цепочки начинаются
различными терминалами, т.е.
LL(k)для
выполняется условие
Если
в грамматике есть левая рекурсия, то
это не LL(k)-грамматика. Критерий
принадлежности языка класу LL(1). КС-гр-ка
G является гр-ой класса LL(1) т.т.т.к.
выполнены условия: для любого нетерминала
A, имеющего 2 альтернативных вывода α и
β
Первая
буква L в названии связана с тем, что
входная цепочка читается слева направо,
вторая L означает, что строится левый
вывод входной цепочки, 1 – что на каждом
шаге для принятия решения используется
один символнепрочитанной части входной
цепочки.
Язык для которого существует порождающая его LL(1)-грамматика, называют LL(1)-языком. Доказано, что проблема определения того, порождает ли грамматика LL-язык, является алгоритмически неразрешимой. Неоднозначная грамматика не является LL(1)-грамматикой.
28.Однопроходный синтаксический анализатор и его алгоритм работы. Управляющая таблица.
Однопроходный синтаксический анализатор использует предсказыв. алгоритм, этот алгоритм детерминированный, состоит из
(w,u,x) – входная лента
|
магазин – |X|<-- управл. таблица π – выходная лента
|α|
|$|
При чтении входной цепочки, находящейся на входной ленте, головка может заглядывать вперед на k очередных символов (эту цепочку называют аванцепочкой).
Управляющая таблица использует только 2 входа: символ, который находится во входном потоке и символ с вершины стека. Выходная лента содержит цепочку π, состоящую из номеров правил.
Управл. таблица руководит работой алгоритма. Алгоритм анализирует входную цепочку. На каждом такте сначала определяются аванцепочка u и верхний символ магазина X. Затем для определения того, что нужно делать рассматривается элемент M(X,u) управляющей таблицы.
Пусть
u=
.
1)
->
если M(X,u)=
.
Здесь верхний символ магазина X заменяется
цепочкой
и к выходу добавляется номер правила
i. Входная головка не сдвигается.
M-управляющая таблица.
2)
выброс
->
,если
M(a,u)=выброс и
.
Когда внешний символ магазина совпадает
с текущим входным символом (1-м символом
цепочки), он выбрасывается из магазина
и входная головка сдвигается на 1 символ
вправо.
3) допуск. Если алгоритм достигает конфигурации (e,$,π) работа прекращается и входная цепочка π называется разбором первоначальной входной цепочки. M($,e) всегда = допуск.
4)если алгоритм достигает конфигурации (x,Xα, π) и M(X,u)=ошибка, то разбор прекращается и выдается сообщение об ошибке.
Г({S,A},{a,b},P,S).
P: 1)S->aAS
2)S->b
3)A->a
4)A->bSA
w=abbab
(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)
Дерево разбора см. в тетради!
30.Алгоритм построения управляющей таблицы для LL(1) грамматики. Функция FIRST_k и FOLLOW_k.
{возвращает
множество всевозможных терминальных
цепочек длины не более k, которые могут
появиться в процессе вывода из цепочки
α}.
Пусть β некоторая цепочка. Пусть она встречается в процессе вывода грамматики, тогда
Рассмотрим
алгоритм построения таблицы для LL(1)
грамматики:M – управляющая таблица.
Входы: символы из магазинного алфавита
по горизонтали, терминальные символы
и e по вертикали.
1)a)
если есть продукция P:A→α и номер продукции
i, то ячейка с координатами (A,a) заполняется
(i,α), при этом a - это те терминал. символы,
которые выводятся из α:
и
.
b)
если же
,
то надо заполнять парой (i, α) ячейку
(A,b), где b – те термин. символы, которые
могут встретиться после A, т.е.
2)M(a,a)= выброс.
3)M($,e)=допуск.
4)в остальных случаях ошибка.
Пример.
G0: E->F+T|T
T->T*F|F
F->(E)|a
Есть левая рекурсия! Надо устранить))) , чтобы сделать LL(1).
E->TE`
E`->+TE`
E`->e
T->FT`
T`->*FT`
T`->e
F->(E)
F->a
{+,e}
{*,e}
{(,a}
{),e}
{+,e}
Т.е. это грамматика LL(1).
Ячейки, в которых должна стоять ошибка, оставлены пустыми.