Информатика и выч. техника \ Теория языков программирования и методы трансляции

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 17

Шаг 4. Для " AÎVN и для всех нетерминальных символов BÎ(FOLLOW¢i(1,A) ÇVN), для которых существует правило $(B ® l)ÎR: FOLLOW¢¢i(1,A) = FOLLOW¢i(1,A) È FOLLOW¢i(1,B).

Шаг 5. Для " AÎVN и " BÎVN, если $(B ® aA)ÎR, aÎ(VTÈVN)*: FOLLOWi+1(1,A) = FOLLOW¢¢i(1,A) È FOLLOW¢¢i(1,B).

Шаг 6. Если $ AÎVN: FOLLOWi+1(1,A) ¹ FOLLOWi(1,A) (т.е. на последнем шаге были изменения во множестве FOLLOWi(1,A)), то i:=i+1 и вернуться на шаг 3, иначе перейти на следующий шаг.

Шаг 7. Для " AÎVN: FOLLOW(1,A) = FOLLOWi(1,A)\VN – исключаем из построенных множеств все нетерминальные символы.

Пример. Рассмотрим нелеворекурсивную грамматику для построения арифметических выражений: G ({+,–,/,*,a,b,(,)}, {S,R,T,F,E}, P, S), где P:

S ® T½TR

R ® +T½–T½+TR½–TR

T ® E½EF

F ® *E½/E½*EF½/EF

E ® (S)½a½b

Очевидно, что эта грамматика не является LL(1)-грамматикой – например, для символов R и F имеется по два правила, начинающихся с одного и того же терминального символа. Но можно получить из данной грамматики эквивалентную ей LL(1)-грамматику. Если преобразовать её к грамматике G¢, добавив пустые правила, то получим P¢:

S ® TR (1)

R ® +TR (2)½–TR (3)½l (4)

T ® EF (5)

F ® *EF (6)½/EF (7)½l (8)

E ® (S) (9)½a (10)½b (11)

Полученная грамматика является LL(1)-грамматикой. Проверим это, построив для неё множества FIRST и FOLLOW. При этом для построения множества FIRST нужна грамматика без пустых правил, поэтому будем брать за основу правила P грамматики G, а для множества FOLLOW – правила P¢ грамматики G¢.

Множество FIRST («1» не будем писать для краткости):

Сначала i:=0;

i:=1:

i:=2:

FIRST0(S) = {T}

FIRST1(S) = {T,E}

FIRST2(S) = {T,E, (,a,b}

FIRST0(R) = {+,–}

FIRST1(R) = {+,–}

FIRST2(R) = {+,–}

FIRST0(T) = {E}

FIRST1(T) = {E, (,a,b}

FIRST2(T) = {E, (,a,b}

FIRST0(F) = {*, /}

FIRST1(F) = {*, /}

FIRST2(F) = {*, /}

FIRST0(E) = {(, a, b}

FIRST1(E) = {(,a,b}

FIRST2(E) = {(,a,b}

Поскольку на последнем шаге новых нетерминалов ни в одно множество не добавилось, последующие изменения невозможны. Формально мы должны выполнить ещё одну итерацию, получив в итоге FIRST3(F) = FIRST2(F). После удаления из построенных множеств нетерминальных символов получим:

FIRST(S) = { (, a, b };       FIRST(R) = {+, – };

FIRST(T) = { (, a, b };       FIRST(F) = {*, / };

FIRST(E) = { (, a, b }

Теперь построим множество FOLLOW (используем правила  P¢):

Сначала i:=0; шаг 1

Шаг 2

Шаг 3

FOLLOW0(S) = {)}

FOLLOW0(S) = {),l}

FOLLOW¢0(S) = {),l}

FOLLOW0(R) = {Æ}

FOLLOW0(R) = {Æ}

FOLLOW¢0(R) = {Æ}

FOLLOW0(T) = {R}

FOLLOW0(T) = {R}

FOLLOW¢0(T) = {R,+,–}

FOLLOW0(F) = {Æ}

FOLLOW0(F) = {Æ}

FOLLOW¢0(F) = {Æ}

FOLLOW0(E) = {F}

FOLLOW0(E) = {F}

FOLLOW¢0(E) = {F,*,/}

Шаг 4. В построенных множествах содержатся только нетерминалы R и F. Хотя для них и существуют пустые правила в P, но в силу того, что множества FOLLOW для R и F пустые, ничего нового не добавится и FOLLOW0¢¢= FOLLOW0¢ для всех нетерминалов.

Шаг 5. Проанализируем правила для " AÎVN на наличие  (B ® aA)ÎR

FOLLOW1(S) = {),l}

Т.к. нет правил вида (B ® aS)– нет добавлений

FOLLOW1(R) = {),l}

Т.к. $ (S ® aR)ÎR, добавили FOLLOW¢¢0(S)

FOLLOW1(T) = {R,+,–}

Т.к. нет (B ® aT)ÎR – нет добавлений

FOLLOW1(F) = {R,+,–}

Т.к. $ (T ® aF)ÎR, добавили FOLLOW¢¢0(T)

FOLLOW1(E) = {F,*,/ }

Т.к. нет (B ® aE)ÎR – нет добавлений

i:=1; Шаг 3. Для " AÎVN " BÎFOLLOW1(A) нужно добавить FIRST(B)

FOLLOW¢1(S) = {),l}

Нет нетерминалов BÎFOLLOW1(S)

FOLLOW¢1(R) = {),l}

Нет нетерминалов BÎFOLLOW1(R)

FOLLOW¢1(T) = {R,+,–,}

Нужно добавить FIRST(R) – нет изменений

FOLLOW¢1(F) = {R,+,–}

Нужно добавить FIRST(R) – нет изменений

FOLLOW¢1(E) = {F,*,/ }

Нужно добавить FIRST(F) – нет изменений

Шаг 4. Для " AÎVN и " BÎFOLLOW¢1(A) проверим на наличие B ® l

FOLLOW¢¢1(S) = {),l}

Нет нетерминалов BÎFOLLOW1(S)

FOLLOW¢¢1(R) = {),l}

Нет нетерминалов BÎFOLLOW1(R)

FOLLOW¢¢1(T) = {R,+,–, ), l}

$ (R ® l)ÎR Þ добавили FOLLOW¢1(R)

FOLLOW¢¢1(F) = {R,+,–, ), l}

$ (R ® l)ÎR Þ добавили FOLLOW¢1(R)

FOLLOW¢¢1(E) = {F,*,/, R,+,–}

$ (F ® l)ÎR Þ добавили FOLLOW¢1(F)

Шаг 5. Проанализируем правила для " AÎVN на наличие (B ® aA)ÎR

FOLLOW2(S) = {),l}

нет (B ® aS)ÎR

FOLLOW2(R) = {),l}

$ (S ® aR)ÎR Þ FOLLOW¢¢1(S) было

FOLLOW2(T) = {R,+,–, ), l}

нет (B ® aT)ÎR

FOLLOW2(F) = {R,+,–, ), l}

$ (T ® aF)ÎR, но нет изменений

FOLLOW2(E) = {F,*,/, R,+,–}

Т.к. нет (B ® aE)ÎR – нет добавлений
Скачать файл