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

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

i:=2; Шаг 3. Новый нетерминал появился только в FOLLOW2(E) 

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

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

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

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

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

добавили FIRST(R) = {+, – } – нет измен.

Шаг 4. Проверка на пустые правила – новый нетерминал только для E

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

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

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

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

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

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

Шаг 5.

Поскольку новых нетерминалов относительно построенного ранее FOLLOW¢¢1 не появилось – множество FOLLOW3 совпадает с FOLLOW¢¢2

FOLLOW3(S) = {),l}

FOLLOW3(R) = {),l}

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

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

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

Множество FOLLOW3 отличается от FOLLOW2 только терминальными символами. Очевидно, что после выполнения ещё одной итерации согласно алгоритму получим FOLLOW4 = FOLLOW3. При выполнении 7 шага исключаются все нетерминальные символы. В итоге построенные множества сведём в одну таблицу для удобства пользования:

AÎVN

FIRST(A)

FOLLOW(A)

S

{ (, a, b }

{ ), l}

R

{+, – }

{ ), l}

T

{ (, a, b }

{+, –, ), l}

F

{*, / }

{+, –, ), l}

E

{ (, a, b }

{*,/, +, –, ), l}

Теперь рассмотрим для нашего примера оба варианта распознавания цепочек – с помощью таблицы М и без неё.

Начнём с построения таблицы М. Строки таблицы озаглавлены символами VÈ{l}, столбцы – символами VTÈ{l}. Построение таблицы было описано раньше; оно выполняется на основании множеств FIRST и FOLLOW и правил грамматики.

Например, для M(S,’a’): должно быть ‘a’ÎFIRST(1,b); где (S®b)ÎR(i), тогда M(S,’a’)=(b,i); при этом i=1, b = TR. Или для M(S,’)’): ‘)’ÏFIRST(1,TR); ‘)’ÎFOLLOW(1,S), но для единственного правила вывода для S (S®TR)ÎR(1) lÏFIRST(1,TR) Þ M(S,’)’)=’ошибка’. Для M(R,’)’): ‘)’ÏFIRST(1,b), где (R®b)ÎR(i) (из R может выводиться только первый терминальный + или – или l), ‘)’ÎFOLLOW(1,R), для (R®l)ÎR(4), lÎFIRST(1,b) Þ M(R,’)’)=(l,4). Остальные клетки таблицы заполняются аналогично. Ячейки таблицы, которые соответствуют ситуации «ошибка», оставлены пустыми.

a

b

(

)

+

–

*

/

l

S

TR,1

TR,1

TR,1

R

l,4

+TR,2

–TR,3

l,4

T

EF,5

EF,5

EF,5

F

l,8

l,8

l,8

*EF,6

/EF,7

l,8

E

a,10

b,11

(S),9

a

выброс

b

выброс

(

выброс

)

выброс

+

выброс

–

выброс

*

выброс

/

выброс

l

допуск

Рассмотрим те же цепочки: a1= ¢a+b¢ и a2= ¢a/(a–b)¢.

Поскольку в данном автомате только одно состояние q, не будем его писать. Для построения вывода в дополнительный стек записываем номера правил. Таким образом, конфигурацию автомата на каждом шаге будем записывать в виде трёх компонент – оставшаяся непрочитанной цепочка, содержимое стека и список использованных правил.

Сначала выполним разбор с помощью таблицы, анализируя текущий символ цепочки ‘a’ и верхний символ стека ‘x’ и используя значение M(x,a). {a+b,S,[l]}Þ{a+b,TR,[1]}Þ{a+b,EFR,[1,5]}Þ{a+b,aFR,[1,5,10]} Þ (выброс) Þ {+b,FR,[1,5,10]} Þ {+b,FR,[1,5,10]} Þ {+b,R,[1,5,10,8]} Þ {+b,+TR,[1,5,10,8,2]} Þ {b,TR,[1,5,10,8,2]} Þ {b,EFR,[1,5,10,8,2,5]} Þ {b,bFR,[1,5,10,8,2,5,11]} Þ {l,FR,[1,5,10,8,2,5,11]} Þ {l,R,[1,5,10,8,2,5,11,8]} Þ {l,l,[1,5,10,8,2,5,11,8,4]}.

Теперь выполним разбор цепочек по второму варианту.

1

{a+b, S, l}

aÎFIRST(TR)Þ выбираем S ® TR (1)

2

{a+b, TR, [1]}

aÎFIRST(EF) Þ выбираем T ® EF (5)

3

{a+b, EFR, [1,5]}

aÎFIRST(a) Þ выбираем E ® a (10)

4

{a+b, aFR, [1,5,10]}

«выброс» – убираем «a»

5

{+b, FR, [1,5,10]}

+ÎFOLLOW(F) Þ выбираем F ® l (8)

6

{+b, R, [1,5,10,8]}

+ÎFIRST(+TR) Þ выбираем R ® +TR (2)

7

{+b, +TR, [1,5,10,8,2]}

«выброс» – убираем «+»

8

{b, TR, [1,5,10,8,2]}

bÎFIRST(EF) Þ выбираем T ® EF (5)

9

{b, EFR, [1,5,10,8,2,5]}

bÎFIRST(b) Þ выбираем E ® b (11)

10

{b, bFR, [1,5,10,8,2,5,11]}

«выброс» – убираем «b»

11

{l, FR, [1,5,10,8,2,5,11,8]}

lÎFOLLOW(F) Þ выбираем F ® l (8)

12

{l, R, [1,5,10,8,2,5,11,8,4]}

lÎFOLLOW(R) Þ выбираем R ® l (4)

13

{l, l, [1,5,10,8,2,5,11,8,4]}

цепочка разобрана, стек пуст.
Скачать файл