CONSCOMP (Материалы к контрольным работам), страница 10

могут появиться нетерминальные символы, из которых выводится

e. Если a может быть самым правым символом некоторой

сентенциальной формы, то $ принадлежит follow(a).

Для построения first(x) для всех символов грамматики x

применим следующий алгоритм.

Алгоритм 3.2. Построение множеств first для символов

грамматики.

Шаг 1. Если x - терминал, то first(x) - это {x}; если x -

нетерминал, полагаем first(x)={}.

Шаг 2. Если имеется правило вывода x->e, то добавить e к

first(x).

Шаг 3. Пока ни к какому множеству first(x) нельзя уже будет

добавить новые элементы или e:

если x - нетерминал и имеется правило вывода x-

>y1y2...yk, то включить a в first(x), если для

некоторого i a<-first(yi) и e принадлежит всем

first(y1),...,first(yi-1), т.е. y1...yi-1=>*e. Если e

принадлежит first(yj) для всех j=1,2,...,k, то добавить

e к first(x). Например, все, что принадлежит first(y1)

принадлежит также и first(x). Если из y1 не выводится

e, то ничего больше не добавляем к first(x), но если

y1=>*e, то добавляем first(y2), и т.д.

Теперь first для любой строки x1x2...xn можно вычислить

следующим образом.

Шаг 1. Полагаем first(x1x2...xn)={}.

Шаг 2. Добавим к first(x1x2...xn) все не e символы из

first(x1). Добавим также не e символы из first(x2), если

e<-first(x1),не e символы из first(x3), если e

принадлежит как first(x1), так и first(x2), и т.д.

Наконец, добавим e к first(x1x2...xn), если e<-first(xi)

для всех i.

Для вычисления follow(a) для нетерминала a применим алгоритм

3.3.

Алгоритм 3.3. Построение follow(x) для всех x - нетерминалов

грамматики.

Шаг 1. Положить follow(x)={}.

Шаг 2. Поместить $ в follow(s), где s - начальный символ и $

- правый концевой маркер.

Шаг 3. Если eсть правило вывода a->ubv, то все из first(v),

за исключением e, добавить к follow(b).

Шаг 4. Пока ничего нельзя будет добавить ни к какому

множеству follow(x): eсли есть правило вывода a->ub или

a->ubv, где first(v) содержит e (т.е. v=>*e), то все из

follow(a) добавить к follow(b).

Пример 3.2. Рaссмотрим снова грамматику (*). Для нее

first(e) =first(t)=first(f)={(,id}

first(e')={+,e}

first(t')={*,e}

follow(e)=follow(e')={),$}

follow(t)=follow(t')={+,),$}

follow(f)={+,*,),$}

Например, id и левая скобка добавляются к first(f) на шаге 3

при i=1, поскольку first(id)={id} и first('(')={'('} в

соответствии с шагом 1. На шаге 3 при i=1, в соответствии с

правилом вывода t->ft' к first(t) добавляются также id и левая

скобка. На шаге 2 в first(e') включается e.

На шаге 1 для вычисления множеств follow в follow(e)

включаем $. На шаге 2, используя правило вывода f->(e), к

follow(e) добавляется также правая скобка. На шаге 3,

примененном к правилу e->te', в follow(e') включаются $ и

правая скобка. Поскольку e'=>*e, они также попадают в

follow(t). В соответствии с правилом вывода e->te', на шаге 2

в follow(t) включается все из first(e'), отличное от e.

3.2.3. Конструирование таблиц предсказывающего анализатора

Для конструирования таблиц предсказывающего анализатора по

грамматике g может быть использован алгоритм, основанный на

следующей идее. Предположим, что a->u - правило вывода

грамматики и a<-firts(u). Тогда анализатор делает развертку a

по u, если входным символом является a. Трудность возникает,

когда u=e или u=>*e. В этом случае нужно развернуть a в u,

если текущий входной символ принадлежит follow(a) или если

достигнут $ и $<-follow(a).

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

Для каждого правила вывода a->u грамматики выполнить шаги 1 и 2

Шаг 1. Для каждого терминала a из first(u) добавить a->u к

m[a,a].

Шаг 2. Если e<-first(u), добавить a->u к m[a,b] для каждого

терминала b из follow(a). Если e<-first(u) и $<-

follow(a), добавить a->u к m[a,$].

Шаг 3. Положить все неопределенные входы равными error.

Пример 3.3. Применим алгоритм 3.4 к грамматике (*). Поскольку

first(te')=first(t)={(,id}, в соответствии с правилом вывода

e->te' входы m[e,(] и m[e,id] становятся равными e->te'.

В соответствии с правилом вывода e'->+te' вход m[e',+] равен

e'->+te'. В соответствии с правилом вывода e'->e входы m[e',)]

и m[e',$] равны e'->e, поскольку follow(e')={),$}.

Таблица анализа, построенная алгоритмом 3.4, приведена на

рис. 3.4.

3.2.4. ll(1)-грамматики

Алгоритм 3.4 для построения таблицы анализа m может быть

применен к любой грамматике. Однако для некоторых грамматик m

может иметь неоднозначно определенные входы. Например, если

грамматика леворекурсивна или неоднозначна, m будет иметь по

крайней мере один неоднозначно определенный вход.

Грамматики, для которых таблицы анализа не имеют

неоднозначно определенных входов, называются ll(1). Первое l

означает сканирование входа слева-направо, второе l означает,

что строится левый вывод, 1 - что на каждом шаге для принятия

решения используется один символ непросмотренной цепочки.

Можно показать, что алгоритм 3.4 для каждой ll(1)-грамматики g

строит таблицы, по которым распознаются все цепочки из l(g) и

только они.

ll(1)-грамматики имеют несколько отличительных свойств.

Неоднозначная или леворекурсивная грамматика не может быть

ll(1). Можно также показать, что грамматика g является ll(1)

тогда и только тогда, когда для двух правил вида a->u|v

выполняется следующее:

1) ни для какого терминала a одновременно из u и v не

выводятся строки, начинающиеся с a;

2) только из одной из строк u или v может выводиться пустая

строка;

3) если v=>*e, то из u не выводится никакая строка,

начинающаяся с терминала из follow(a).

Эквивалентным является следующее определение:

КС-грамматика называется ll(1)-грамматикой, если из

существования двух левых выводов

(1) s =>* w a u => w v u =>* wx,

(2) s =>* w a u => w z u =>* wy,

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

означает, что для данной цепочки wau и первого символа,

выводящегося из au (или $), существует не более одного

правила, которое может быть применено к a, чтобы получить

вывод какой-нибудь терминальной цепочки, начинающейся с w и

продолжающейся этим первым символом.

Язык, для которого можно построить ll(1)-грамматику,

называют ll(1)-языком.

Если таблица анализа имеет неоднозначно определенные входы,

то грамматика не является ll(1). Примером может служить

следующая грамматика:

st -> if ex then st

| if ex then st else st

| cont

ex -> ...

Эта грамматика неоднозначна, что иллюстрируется рис. 3.7.

Поскольку грамматика неоднозначна, она не является ll(1).

Проблема, порождает ли грамматика ll-язык, алгоритмически

неразрешима.

st st

/|\ /| \