4.3 Напишите синтаксический анализатор рекурсивного спуска, соответствующий грамматике со следующими порождающими правилами (Е - начальный символ):

E->TG

G->+TG

T->FU

U->xFU

F->(E) identifier

4.4 Контекстно-свободная грамматика называется q-грамматикой тогда (и только тогда), когда она обладает следующими свойствами:

1.Правая часть каждого правила либо начинается с терминала, либо пустая.

2.Для каждого нетерминала, появляющегося в левой части более чем одного правила, множества направляющих символов, соответствующих правым частям альтернативных правил, являются непересекающимися.

Докажите, что

а) любая q-грамматика есть LL(1);

б) любая s-грамматика есть q-грамматика;

в) любую LL(1)-грамматику можно преобразовать в q-грамматику.

4.5 Приведите LL(1)-грамматики для каждого из следующих языков: 1. {0na12nn>0}.

2.{aa находится в {0,1}* и не содержит две последовательные 1}. 3.{aa состоит из равного числа нулей и единиц}.

4.6 Преобразуйте грамматику со следующими правилами в LL(1)-форму (E - начальный символ):

E->E+T F->(E) E->T F->x

T->TxF F->y T->F

4.7. Обладает ли грамматика со следующими правилами признаком LL(1) или нет? Обоснуйте свой ответ.

4.8. Докажите, что все LL( I)-грамматики являются однозначными.

4.9. Постройте LL(1)-таблицу разбора для языка, определяемого посредством LL(l)-rpaммматики с правилами:

PROGRAM->begin d semi X end X->d semi X X->s Y У->е

Y->semi s Y

4.10. Постройте ЬЬ(1)-таблицу разбора для языка, определяемого грамматикой из упр. 4.6.