2015-02-18
1140
Для того чтобы грамматика G (VN, VT, P, S) была LL (1) - грамматикой необходимо и достаточно, чтобы для каждого символа А Î VN, у которого в грамматике существует более одного правила вида А ®a1 | a2 |…| a n, выполнялось требование:
FIRST (1, a iFOLLOW (1, A)) Ç FIRST (1, a jFOLLOW (1, A)) = Æ,
" i ¹ j,0< i £ n, 0< j £ n.
Т.е. если для символа А отсутствует правило вида А ®e, то все множества FIRST (1, a1), FIRST (1, a2),…, FIRST (1, a n) должны попарно не пересекаться, если же присутствует правило А ®e, то они не должны также пересекаться с множеством 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) для каждого нетерминального символа А.
3.4.2.3 Построение множества FIRST (1, A)
Для выполнения алгоритма необходимо предварительно преобразовать исходную грамматику G в грамматику G ¢, не содержащую e-правил (см. лабораторную работу № 4). Алгоритм построения множества FIRST (1, A) использует грамматику G ¢.
Шаг 1. Первоначально внести во множество первых символов для каждого нетерминального символа А все символы, стоящие в начале правых частей правил для этого нетерминала, т.е.
" А Î VN FIRST 0(1, A) = { X | A ® X a Î P, X Î(VT È VN),aÎ(VT È VN)*}.
Шаг 2.Для всех А Î VN положить:
FIRSTi +1(1, A) = FIRSTi (1, A) È FIRSTi (1, B), " В Î(FIRST (1, A)Ç VN).
Шаг 3. Если существует А Î VN, такой что FIRSTi +1(1, A) ¹ FIRSTi (1, A), то присвоить i = i +1 и вернуться к шагу 2, иначе перейти к шагу 4.
Шаг 4.Исключить из построенных множеств все нетерминальные символы, т.е.
" A Î VN FIRST (1, A) = FIRSTi (1, A) \ N .
3.4.2.4 Построение множества FOLLOW (1, A)
Алгоритм основан на использовании правил вывода грамматики G.
Шаг 1.Первоначально внести во множество последующих символов для каждого нетерминального символа А все символы, которые в правых частях правил вывода встречаются непосредственно за символом А, т.е.
" A Î VN FOLLOW 0(1, A) = { X | $ B ® a AX b Î P, B Î VN, X Î (VT È VN),
a, b Î(VT È VN)*}.
Шаг 2.Внести пустую строку во множество FOLLOW (1, S), т.е.
FOLLOW (1, S) = FOLLOW (1, S)È{ e }.
Шаг 3.Для всех А Î VN вычислить:
FOLLOW ¢ i (1, A)= FOLLOWi (1, A)È FIRST (1, B)," B Î(FOLLOWi (1, A)Ç VN).
Шаг 4.Для всех А Î VN положить:
FOLLOW²i (1, A)= FOLLOW¢i (1, A)È FOLLOW¢i (1, B),
" B Î(FOLLOW¢i (1, A)Ç VN), если $ правило B ®e.
Шаг 5.Для всех А Î VN определить:
FOLLOWi +1(1, A) = FOLLOW²i (1, A)È FOLLOW²i (1, B),
для всех нетерминальных символов BÎVN, имеющих правило вида
B ® aA, a Î(VT È VN)*.
Шаг 6.Если существует A Î VN такой, что FOLLOWi +1(1, A)¹ FOLLOWi (1, A), то положить i:= i +1 и вернуться к шагу 3, иначе перейти к шагу 7.
Шаг 7.Исключить из построенных множеств все нетерминальные символы, т.е. " A Î VN FOLLOW (1, A) = FOLLOWi (1, A)\ N .
3.4.2.5 Алгоритм «сдвиг-свертка» для LL (1)-грамматик
Шаг 1. Помещаем в стек начальный символ грамматики S, а во входной буфер исходную цепочку символов.
Шаг 2.До тех пор пока в стеке и во входном буфере останется только пустая строка e либо будет обнаружена ошибка в алгоритме разбора, выполняем одно из следующих действий:
- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® х при условии, что а Î FIRST (1, x), т.е. извлекаем из стека символ А и заносим в стек строку х, не меняя содержимого входного буфера;
- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® e при условии, что а Î FOLLOW (1, A), т.е. извлекаем из стека символ А и заносим в стек строку e, не меняя содержимого входного буфера;
- если на верхушке стека находится терминальный символ а, совпадающий с очередным символом входной строки, то выполняем операцию «выброс», т.е. удаляем из стека и входного буфера данный терминальный символ;
- если содержимое стека и входного буфера пусто, то исходная строка прочитана полностью, и разбор завершен удачно;
- если ни одно из данных условий не выполнено, то цепочка не принадлежит заданному языку, и алгоритм завершает свою работу с ошибкой.
Пример Дана грамматика G ({ S, T, R }, {+, -, (,), a, b }, P, S), с правилами P: 1) S ® TR; 2) R ®e | + TR | - TR; 3) T ®(S) | a | b. Построить распознаватель для строки (a +(b - a)) языка грамматики G.
Этап 1. Преобразуем грамматику G в грамматику G ¢, не содержащую e -правил:
N 0 = { R };
N 1 = { R }, т.к. N 0 = N 1, то во множество P¢ войдут правила:
1) S ® TR | T;2) R® +TR | +T | -TR | -T; 3) T ®(S) | a | b.
Этап 2. Построение множеств FIRST (1, A) для каждого нетерминала А представлено в таблице 3.3.
Таблица 3.3 – Построение множеств FIRST (1, A)
| FIRSTi (1, A) | FIRST (1, A) | |||
| S | T | T, (, a, b | T, (, a, b | (, a, b |
| R | +, - | +, - | +, - | +, - |
| T | (, a, b | (, a, b | (, a, b | (, a, b |
Этап 3. Построение множеств FOLLOW (1, A) для каждого нетерминала А представлено в таблице 3.4.
Таблица 3.4 – Построение множеств FOLLOW (1, A)
| Шаг | Нетерминалы | FOLLOWi (1, A) | FOLLOWi’ (1, A) | FOLLOWi’’ (1, A) |
| S | ) | ), e | ), e | |
| R | Æ | Æ | Æ | |
| T | R | R, +, - | R, +, - | |
| S | ), e | ), e | ), e | |
| R | ), e | ), e | ), e | |
| T | R, +, - | R, +, - | R, +, -,), e | |
| S | ), e | ), e | ), e | |
| R | ), e | ), e | ), e | |
| T | R, +, -,), e | R, +, -,), e | R, +, -,), e | |
| FOLLOW (1, S) | ), e | |||
| FOLLOW (1, R) | ), e | |||
| FOLLOW (1, T) | +, -,), e |
Этап 4. Множества FIRST (1, A) и FOLLOW (1, A) для каждого нетерминала А сведены в таблицу 3.5.
Таблица 3.5 – Множества FIRST (1, A) и FOLLOW (1, A)
| A | FIRST (1, A) | FOLLOW (1, A) |
| S | (, a, b | ), e |
| R | +, - | ), e |
| T | (, a, b | +, -,), e |
Грамматика G является LL (1) - грамматикой, т.к. для каждого нетерминала А, имеющего альтернативные выводы, множества FIRST (1, A) попарно не пересекаются, а для нетерминала R они также не пересекаются со множеством FOLLOW (1, R).
Шаг 5. Разбор строки (a +(b - a)) для грамматики G показан в таблице 3.6.
Таблица 3.6 - Разбор строки (a +(b - a)) для грамматики G
| Стек | Входной буфер | Действие |
| S | (a +(b - a)) | свертка S ® TR, т.к. (Î FIRST (1, TR) |
| TR | (a +(b - a)) | свертка T ®(S), т.к. (Î FIRST (1, (S)) |
| (S) R | (a +(b -a)) | выброс |
| S) R | a +(b - a)) | свертка S ® TR, т.к. a Î FIRST (1, TR) |
| TR) R | a +(b - a)) | свертка T ® a, т.к. a Î FIRST (1, a) |
| aR) R | a +(b - a)) | выброс |
| R) R | +(b - a)) | свертка R ®+ TR, т.к. +Î FIRST (1, TR) |
| + TR) R | +(b - a)) | выброс |
| TR) R | (b - a)) | свертка T ®(S), т.к. (Î FIRST (1, (S)) |
| (S) R) R | (b - a)) | выброс |
| S) R) R | b - a)) | свертка S ® TR, т.к. b Î FIRST (1, TR) |
| TR) R) R | b - a)) | свертка T ® b, т.к. b Î FIRST (1, b) |
| bR) R) R | b - a)) | выброс |
| R) R) R | - a)) | свертка R ®- TR, т.к. -Î FIRST (1, - TR) |
| - TR) R) R | - a)) | выброс |
| TR) R) R | a)) | свертка T ® a, т.к. a Î FIRST (1, a) |
| aR) R) R | a)) | выброс |
| R) R) R | )) | свертка R ®e, т.к.) Î FOLLOW (1, R) |
| ) R) R | )) | выброс |
| R) R | ) | свертка R ®e, т.к.) Î FOLLOW (1, R) |
| ) R | ) | выброс |
| R | e | свертка R ®e, т.к. eÎ FOLLOW (1, R) |
| e | e | строка принята полностью |
Шаг 6. Получили следующую цепочку вывода:
S Þ TR Þ(S) R Þ(TR) R Þ(aR) R Þ(a + TR) R Þ(a +(S) R) R Þ(a +(TR) R) R Þ
Þ(a +(bR) R) R Þ(a +(b - TR) R) R Þ(a +(b - aR) R) R Þ(a +(b - a) R) R Þ(a +(b - a)) R
Þ(a +(b - a)).
 |
Рисунок 3.3 – Дерево вывода для цепочки (a +(b - a)) в грамматике G
