Лабораторная работа № 6 Моделирование фу. Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик

Название	Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик
Дата	11.12.2022
Размер	0.58 Mb.
Формат файла
Имя файла	Лабораторная работа № 6 Моделирование фу.doc
Тип	Лабораторная работа #838399
страница	2 из 5

1 2 3 4 5

Теорема 6.1. Необходимое и достаточное условие LL(1)-грамматики

Для того чтобы грамматика G(V_N, V_T, P, S) была LL(1)-грамматикой необ- ходимо и достаточно, чтобы для каждого символа АV_N, у которого в грамма- тике существует более одного правила вида А₁ | ₂ |…| _n, выполнялось тре- бование:
FIRST(1, _iFOLLOW(1, A))  FIRST(1, _jFOLLOW(1, A)) = ,

 ij, 0<in, 0<jn.
Т.е. если для символа А отсутствует правило вида А, то все множества FIRST(1, ₁), FIRST(1, ₂),…, FIRST(1, _n) должны попарно не пересекаться, ес- ли же присутствует правило А, то они не должны также пересекаться с мно- жеством FOLLOW(1, A).
Для построения распознавателей для LL(1)-грамматик необходимо по- строить множества FIRST(1, x) и FOLLOW(1, A). Причем, если строка х будет начинаться с терминального символа а, то FIRST(1, x)=a, и если она будет на- чинаться с нетерминального символа А, то FIRST(1, x)=FIRST(1, A). Следова- тельно, достаточно рассмотреть алгоритмы построения множеств FIRST(1, A) и FOLLOW(1, A) для каждого нетерминального символа А.

Алгоритм 6.1. Построение множества FIRST(1, A)

Для выполнения алгоритма необходимо предварительно преобразовать исходную грамматику G в грамматику G, не содержащую -правил (см. лабо- раторную работу № 4). Алгоритм построения множества FIRST(1, A) использу- ет грамматику G.

Шаг 1. Первоначально внести во множество первых символов для каждо- го нетерминального символа А все символы, стоящие в начале правых частей правил для этого нетерминала, т.е.

 АV_NFIRST₀(1, A) = {X|AX P, X(V_TV_N), (V_TV_N)^*}.

Шаг 2. Для всех АV_Nположить:

FIRST_i₊₁(1, A) = FIRST_i(1, A)  FIRST_i(1, B),  В(FIRST(1, A)V_N).

Шаг 3. Если существует АV_N, такой что FIRST_i₊₁(1, A)  FIRST_i(1, A), то присвоить i=i+1 и вернуться к шагу 2, иначе перейти к шагу 4.

Шаг 4. Исключить из построенных множеств все нетерминальные симво- лы, т.е.

 AV_NFIRST(1, A) = FIRST_i(1, A) _\ _N.

Алгоритм 6.2. Построение множества FOLLOW(1, A)

Алгоритм основан на использовании правил вывода грамматики G.

Шаг 1. Первоначально внести во множество последующих символов для каждого нетерминального символа А все символы, которые в правых частях правил вывода встречаются непосредственно за символом А, т.е.

 AV_NFOLLOW₀(1, A) = {X|  B AX  P, B V_N, X (V_TV_N),

, (V_TV_N)^*}.

Шаг 2. Внести пустую строку во множество FOLLOW(1, S), т.е.

FOLLOW(1, S) = FOLLOW(1, S){}.

Шаг 3. Для всех АV_Nвычислить:

FOLLOW_i(1,A)=FOLLOW_i(1,A)FIRST(1,B),B(FOLLOW_i(1,A)V_N).

Шаг 4. Для всех АV_Nположить:

FOLLOW_i(1, A)=FOLLOW_i(1, A)FOLLOW_i(1, B),

B(FOLLOW_i(1, A)V_N), если  правило B.

Шаг 5. Для всех АV_Nопределить:

FOLLOW_i₊₁(1, A) = FOLLOW_i(1, A)FOLLOW_i(1, B),

для всех нетерминальных символов BV_N, имеющих правило вида

BA, (V_TV_N)^*.

Шаг 6. Если существует AV_Nтакой, что FOLLOW_i₊₁(1,A)FOLLOW_i(1,A), то положить i:=i+1 и вернуться к шагу 3, иначе перейти к шагу 7.

Шаг 7. Исключить из построенных множеств все нетерминальные симво- лы, т.е.  AV_NFOLLOW(1, A) = FOLLOW_i(1, A)_\ _N.

1 2 3 4 5