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

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

Оба варианта дали один результат – последовательность правил.

Запишем цепочку вывода по полученной последовательности номеров правил: S Þ(1)TR Þ(5)EFR Þ(10)aFR Þ(8)aR Þ(2)a+TR Þ(5)a+EFR Þ(11) a+bFR Þ(8)a+bR Þ(4)a+b. Разбор цепочки выполнен за 13 шагов.

Теперь рассмотрим разбор цепочки a2= ¢a/(a–b)¢.

1

{a/(a-b), S, l}

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

2

{a/(a–b), TR, [1]}

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

3

{a/(a–b), EFR, [1,5]}

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

4

{a/(a–b), aFR, [1,5,10]}

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

5

{/(a–b), FR, [1,5,10]}

/ÎFIRST(/EF) Þ выбираем F ® /EF (7)

6

{/(a–b), /EFR, [1,5,10,7]}

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

7

{(a–b), EFR, [1,5,10,7]}

(ÎFIRST((S)) Þ выбираем E ® (S) (9)

8

{(a–b), (S)FR, [1,5,10,7,9]}

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

9

{a–b), S)FR, [1,5,10,7,9]}

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

10

{a–b), TR)FR, [1,5,10,7,9,1]}

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

11

{a–b), EFR)FR, [1,5,10,7,9,1,5]}

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

12

{a–b), aFR)FR, [1,5,10,7,9,1,5,10]}

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

13

{–b), FR)FR, [1,5,10,7,9,1,5,10]}

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

14

{–b), R)FR, [1,5,10,7,9,1,5,10,8]}

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

15

{–b),–TR)FR,[1,5,10,7,9,1,5,10,8,3]}

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

16

{b),TR)FR,[1,5,10,7,9,1,5,10,8,3]}

bÎFIRST(EF) Þ T ® EF (5)

17

{b),EFR)FR,[1,5,10,7,9,1,5,10,8,3,5]}

bÎFIRST(b) Þ E ® b (11)

18

{b),bFR)FR,[1,5,10,7,9,1,5,10,8,3,5,11]}

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

19

{),FR)FR,[1,5,10,7,9,1,5,10,8,3,5,11]}

)ÎFOLLOW(F)Þ F ® l (8)

20

{),R)FR,[1,5,10,7,9,1,5,10,8,3,5,11,8]}

)ÎFOLLOW(R) Þ R ® l (4)

21

{),)FR,[1,5,10,7,9,1,5,10,8,3,5,11,8,4]}

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

22

{l,FR,[1,5,10,7,9,1,5,10,8,3,5,11,8,4]}

lÎFOLLOW(F) Þ F ® l (8)

23

{l,R,[1,5,10,7,9,1,5,10,8,3,5,11,8,4,8]}

lÎFOLLOW(R) Þ R ® l (4)

24

{l,l,[1,5,10,7,9,1,5,10,8,3,5,11,8,4,8,4]}

цепочка разобрана, стек пуст.

Получена цепочка вывода :S Þ(1)TR Þ(5)EFR Þ(10)aFR Þ(7)a/EFR Þ(9) a/(S)FR Þ(1) a/(TR)FR Þ(5) a/(EFR)FR Þ(10) a/(aFR)FR Þ(8) a/(aR)FRÞ(3)
a/(a–TR)FR Þ(5) a/(a–EFR)FR Þ(11) a/(a–bFR)FR Þ(8) a/(a–bR)FR Þ(4)
a/(a–b)FR Þ(8) a/(a–b)R Þ(4) a/(a–b) .

Попробуем рассмотреть неправильную цепочку, например, (+a)*b.

1

{(+a)*b, S, l}

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

2

{(+a)*b, TR, [1]}

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

3

{(+a)*b, EFR, [1,5]}

(ÎFIRST((S)) Þ выбираем E ® (S) (9)

4

{(+a)*b, (S)FR, [1,5,9]}

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

5

{+a)*b, S)FR, [1,5,9]}

Нет правил вида S ® b½+ÎFIRST(b) и +ÏFOLLOW(F) Þ цепочка не принята

Заметим, что в случае использования таблицы (вариант разбора 1) остановка произошла бы в той же конфигурации, т.к. M(S,’+’)=’ошибка’.

Из рассмотренных примеров видно, что алгоритму разбора на основе LL(1)-грамматик требуется значительно меньше шагов на принятие решения относительно входной цепочки.

Алгоритм является эффективным, только строгие ограничения на правила грамматики сужают возможности его применения.

3.5.2  Восходящие распознаватели без возвратов

Основная возможность улучшения алгоритма восходящего разбора также состоит в том, чтобы на каждом шаге работы однозначно принимать решение, что выполнять, сдвиг или свёртку, а также какие цепочку и правило выбирать для свёртки. В таком случае возвратов не выполняется, и количество проделанных шагов алгоритма имеет линейную зависимость от длины входной цепочки. Если алгоритм не заканчивается успешно, то входная цепочка не принимается, повторных итераций не производится.

3.5.2.1  LR(k)-грамматики

При моделировании восходящих распознавателей без возвратов может использоваться аналогичный подход, который был положен в основу определения LL(k)-грамматик.

КС-грамматика обладает свойством LR(k), k³0, если на каждом шаге вывода для принятия однозначного решения по вопросу о выполняемом действии в алгоритме «сдвиг-свёртка» расширенному МПА достаточно знать содержимое верхней части стека и рассмотреть первые k символов от текущего положения считывающей головки автомата во входной цепочке символов.

Грамматика называется LR(k)-грамматикой, если она обладает свойством LR(k).

Обозначение грамматики LR(k) имеет смысл, аналогичный рассмотренной ранее аббревиатуре LL(k). Отличие состоит в символе R, который обозначает, что в результате работы распознавателя получается правосторонний вывод. Остальные символы имеют тот же смысл, что и в обозначении LL(k)-грамматики.

В совокупности все LR(k)-грамматики для различных k³0 образуют класс LR-грамматик. Поскольку алгоритм восходящего распознавателя моделирует работу расширенного МПА, возможность k=0 не является абсурдом, т.к. в таком случае все равно автомат в процессе работы рассматривает цепочки символов на вершине стека и, следовательно, результат его работы зависит от входной цепочки (т.к. в стеке находится именно она).

Скачать файл