Нисходящий и восходящий распознаватели

1. §1.6. Нисходящий и восходящий распознаватели

1.6.1. Нисходящий распознаватель

2.

Определение. Нетерминал U КС-грамматики
называется рекурсивным (циклическим),
если существует вывод
U =>* U .
Если = e, то U – леворекурсивный.
Если = e, то U – праворекурсивный.
Грамматика, имеющая хотя бы один
леворекурсивный нетерминал называется
леворекурсивной.
Аналогично определяется праворекурсивная
грамматика.

3.

Определение. Нетерминал U КС-грамматики
называется рекурсивным (циклическим),
если существует вывод
1) A -> ! B !
2) B -> B + T
U =>* U .
3) B -> T
Если = e, то U – леворекурсивный.
4) T -> T * M
Если = e, то U – праворекурсивный.
5) T -> M
6) M -> И
Грамматика, имеющая хотя бы один
7) М -> (В)
леворекурсивный нетерминал называется
леворекурсивной.
Аналогично определяется праворекурсивная
грамматика.
Грамматика G1 – леворекурсивная,
леворекурсивные символы В, Т.

4. 1.6.1.1 Неформальное описание нисходящего анализа

Пусть задана КС-грамматика G и некоторая
входная цепочка .
Занумеруем альтернативы нетерминалов.
Введем указатель на текущий символ цепочки ,
вначале он показывает на первый символ.
Нисходящий анализатор пытается построить
дерево вывода таким образом.
В корень дерева помещаем S – начальный символ
грамматики. Это первая активная вершина.
Затем рекурсивно выполняются следующие шаги.

5. Шаг 1.

Если активная вершина помечена
нетерминалом A, то выбираем его
первую альтернативу.
Добавляем к вершине A потомков,
соответствующих символам правой части
правила, например,
X1X2…Xk.
Делаем X1 активной вершиной. Если k = 0, то
сделать активной вершину справа от A.

6. Шаг 2.

Если активная вершина помечена терминалом,
например, a, то сравним его с текущим
символом цепочки .
Если они совпадают, сделать
активной соседнюю с a вершину и продвинуть
указатель на одну позицию вправо. К шагу 1.
Если же не совпадают, то сделать возврат к
последней вершине, к которой применялось
правило, и вернуть указатель на позицию
назад. Испытать следующую альтернативу
для этой вершины.

7.

Если альтернатив уже не окажется, то
надо вернуться в дереве выше, к
вершине, породившей данную и т.д.

8. Завершение алгоритма

Процесс закончится, когда
- либо будет построено дерево вывода с
концевыми вершинами цепочки
( L(G)),
- либо произойдет возврат в корень дерева,
и у начального символа S уже будут
перебраны все альтернативы
( L(G)).

9. Завершение алгоритма

Процесс закончится, когда
- либо будет построено дерево вывода с
концевыми вершинами цепочки
( L(G)),
- либо произойдет возврат в корень дерева,
и у начального символа S уже будут
перебраны все альтернативы
( L(G)).
Замечание.
Зацикливание для леворекурсивной
грамматики!

10. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
A
=!a*b!

11. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
A
!
=!a*b!
B
!

12. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
A
!
=
=!a*b!
B
!

13. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
A
!
B
!
T
+
B
=
=!a*b!

14. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
!
B
!
T
+
B
M
=!a*b!

15. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
!
B
!
T
+
B
M
=!a*b!

16. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
!
B
!
T
+
B
M
≠
=!a*b!

17. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
!
B
!
T
+
B
M
Последуют возвраты:
≠ • К М – взять 2-ую альтернативу
М -> (В)
=!a*b!

18. Пример

A
G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
!
B
!
T
+
B
Последуют возвраты:
• К М – взять 2-ую альтернативу
М -> (В)
M
=
(
В
=!a*b!
)

19. Пример

A
G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
!
B
!
T
+
B
Последуют возвраты:
• К М – взять 2-ую альтернативу
М -> (В)
M
=
В
(
≠
=!a*b!
)

20. Пример

A
G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
!
B
!
T
+
B
Последуют возвраты:
• К М – взять 2-ую альтернативу
М -> (В)
M
=
– не подойдет
В
(
≠
=!a*b!
)
и вернемся к Т

21. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
М
!
B
!
T
+
B
*
Последуют возвраты:
• К М – взять 2-ую альтернативу
Т
М -> (В)
– не подойдет
=!a*b!
и вернемся к Т

22. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
=
A
М
!
B
!
T
+
B
*
Последуют возвраты:
• К М – взять 2-ую альтернативу
Т
М -> (В)
– не подойдет
=!a*b!
и вернемся к Т
2) Но 2-я альтернатива для Т
Т -> М * Т
тоже не подойдет и вернемся к В

23. Пример

G1:
1) A ->! B !
2) B -> T + B
3) B -> T
4) T -> M
5) T -> M * Т
6) M -> И
7) M -> (B)
Верный вывод
A
A
М
!
B
!
T
+
B
*
Т
B
!
!
T
М
Т
*
=
М
=!a*b!
!a*b!

24. 1.6.1.2 Алгоритм нисходящего распознавателя

Алгоритм использует два стека L1 и L2 и
указатель входной цепочки .
Алгоритм. Нисходящий разбор с
возвратами.
Вход. Не леворекурсивная КС-грамматика,
входная цепочка = a1a2…an (n>=0). Правила
перенумерованы 1,…, p.
Выход. Один левый вывод, если он
существует, “ошибка” в противном случае.

25. Вводные пояснения

Для каждого нетерминального символа A
упорядочим его альтернативы
произвольным образом.
Обозначим через Ai – i-ую альтернативу
нетерминала A и назовем Ai индексом
альтернативы.
Обозначим через I множество индексов
альтернатив нетерминалов.

26.

Введем конфигурацию алгоритма
(s, i, , ) ,
где s – состояние алгоритма, s {q, b, t }:
q – состояние нормальной работы,
b – состояние возврата,
t - заключительное состояние
(нормальное завершение);
i – текущее значение указателя входной
цепочки ;
- содержимое стека L1;
- содержимое стека L2.

27.

Будем считать, что стеки расположены
навстречу друг другу
L1
1
2
…
k
1 2
…
n
Стек L1 будет содержать историю проделанных
подстановок, а именно, индексы альтернатив и
прочитанные символы ai, т.е.
(I U T)*.
Стек L2 будет содержать текущую цепочку
вывода, так что
1 – активная вершина, (T U N)*.
Начальная конфигурация (q, 1, e, S),
заключительная (t, n+1, , e).
L2

28.

Работа распознавателя – это переход
от одной конфигурации к другой.
Значок |- будем читать, как «переходим
к».
Возможны следующие типы шагов:

29. Шаги алгоритма.

(1) Разрастание дерева
(q, i, , A ) |- (q, i, A1, 1 ),
т.е. к активной вершине – нетерминалу A применяется первая альтернатива
A -> 1:
в L1 формируется индекс альтернативы
A1,
в L2 вместо A заносится правая часть
правила 1.

30. Шаг 2

(2) Успешное сравнение входного символа с
порожденным
(q, i, , a ) |- (q, i+1, a, ), если a = ai, i n,
т.е. порожденный символ a (активная
вершина) совпал с текущим символом
входной цепочки ai:
терминальный символ a переносится из
стека L2 в стек L1,
и указатель входной цепочки продвигается
на один символ вправо.

31. Шаг 3

(3) Успешное завершение
(q, n + 1, , e ) |- ( t, n + 1, , e),
т.е. цепочка вся прочитана и стек L2 пуст.
Получен левый вывод цепочки .
Его значение получается по функции h( ):
h( i ) = e, если i T,
h( i ) = p, если i = Ak – индекс альтернативы,
а p номер соответствующего правила A -> k.
Таким образом, анализируя стек L1,
терминальные символы вычеркиваем, а
индексы нетерминалов заменяем на номера
правил.

32. Шаг 3’ (иначе шагу (3))

В
(3’) Неуспешное завершение
Т + В
(q, i, , ) |- (b, i, , )
Если i = n+1, а e, то цепочка вся
М * Т
М
прочитана, но стек L2 не пуст (в дереве
a * b
вывода есть “нераскрытые” вершины)
или = e, а i n+1( цепочка прочитана не вся,
В
а в дереве вывода уже нет вершин).
Т
Переход в состояние возврата.
М
a+ b

33. Шаг 4 (иначе шагу 2)

(4) Неудачное сравнение входного
символа с порожденным
(q, i, , a ) |- (b, i, , a ), если ai a.
Активная вершина – терминал a – не
совпала с текущим символом ai
цепочки .
Переход в состояние возврата.

34. Шаг 5

(5)Возврат по терминалу
(b, i, a, ) |- (b, i – 1, , a )
В вершине стека L1 находится
терминальный символ a.
Cимвол a из стека L1 при возврате
переносится в стек L2, а указатель входной
цепочки возвращается на один символ
назад.

35. Шаг 6

(6) Возврат по нетерминалу (испытание
новой альтернативы)
Выполняется попытка применить новую
альтернативу к нетерминалу, находящемуся
в вершине стека L1.
Если текущая конфигурация
(b, i, Aj, j ),
то возможны случаи:

36. Шаг 6а

(b, i, Aj, j ),
Шаг 6а
(6a)
|- (q, i, Aj + 1, j + 1 ),
т.е. у нетерминала A ещё есть другая
альтернатива
A -> j + 1
Выполняем замену альтернативы A -> j на
альтернативу A -> j + 1 :
для этого в стеке L1 заменяем индекс Aj на
Aj+1,
а в стеке L2 правую часть j на j+1;
Переходим в нормальное состояние q.

37. Шаг 6б

(6б) следующая конфигурация невозможна,
если i = 1, A S (начальный символ) и у
нетерминала S только j альтернатив.
Перебраны все альтернативы всех
нетерминалов, т.е. все левовыводимые
цепочки,
вернулись в корень дерева,
но вывода для цепочки не нашлось.
Следовательно, L(G).
Выход “ошибка”.

38. Шаг 6в

(b, i, Aj, j ),
Шаг 6в
(6в) |- (b, i, , A )
в остальных случаях, т.е. когда A S.
Все альтернативы у нетерминала A
перебраны, выполняется возврат этого
нетерминала:
в стеке L2 правая часть правила A -> j
заменяется на левую часть A,
индекс альтернативы Aj из стека L1
удаляется.
В дереве вывода это соответствует возврату
на более высокий уровень, который породил
этот нетерминал A.
Остаемся в состоянии возврата.

39.

Возврат далее будет повторяться по
5) или 6) в зависимости от символа
в вершине стека L1 (терминал
или нетерминал).

40. Замечание.

Обратим внимание на следующее.
В состоянии нормальной деятельности
(q) всегда анализируется символ в
вершине стека L2,
а в состоянии возврата (b) – в вершине
стека L1.

41. Пример.

Рассмотрим грамматику ~G1
Правила
Номера альтернатив
1) В -> Т + В
1
2) В -> T
2
3) T -> M
1
4) T -> M * T
2
5) M ->a
1
6) M ->b
2
Рассмотрим вывод цепочки a+b

42.

s
L1
q
L2
e B
Шаги
a+b
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

43.

s
L1
q
q
L2
e B
B1 T + B
a+b
a+b
Шаги
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

44.

s
L1
q
q
q
L2
e B
B1 T + B
B1T1 M + B
a+b
a+b
a+b
Шаги
1
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

45.

s
L1
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
a+b
a+b
a+b
a+b
Шаги
1
1
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

46.

s
L1
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
a+b
a+b
a+b
a+b
+b
Шаги
1
1
1
2
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

47.

s
L1
q
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
B1T1M1a+ B
a+b
a+b
a+b
a+b
+b
b
Шаги
1
1
1
2
2
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

48.

s
L1
q
q
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
B1T1M1a+ B
B1T1M1a+B1 T + B
a+b
a+b
a+b
a+b
+b
b
b
Шаги
1
1
1
2
2
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

49.

s
L1
q
q
q
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
B1T1M1a+ B
B1T1M1a+B1 T + B
B1T1M1a+B1T1 M + B
a+b
a+b
a+b
a+b
+b
b
b
b
Шаги
1
1
1
2
2
1
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

50.

s
L1
q
q
q
q
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
B1T1M1a+ B
B1T1M1a+B1 T + B
B1T1M1a+B1T1 M + B
B1T1M1a+B1T1M1 a + B
a+b
a+b
a+b
a+b
+b
b
b
b
b
Шаги
1
1
1
2
2
1
1
1
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

51.

s
L1
q
q
q
q
q
q
q
q
q
L2
e B
B1 T + B
B1T1 M + B
B1T1M1 a + B
B1T1M1a + B
B1T1M1a+ B
B1T1M1a+B1 T + B
B1T1M1a+B1T1 M + B
B1T1M1a+B1T1M1 a + B
Шаги
a+b
a+b
a+b
a+b
+b
b
b
b
b
1
1
1
2
2
1
1
1
4,т.к.a b
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2

52.

s
L1
b
1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
B1T1M1a+B1T1M1
1
2
1
2
1
2
L2
a+B
b
Шаги

53.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
q
1
2
1
2
1
2
L1
B1T1M1a+B1T1M1
B1T1M1a+B1T1M2
L2
a+B
b+B
b
b
Шаги
6а

54.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
L2
a+B
b+B
+B
b
b
Шаги
6а
2

55.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
L2
a+B
b+B
+B
+B
b
b
Шаги
6а
2
3’, т.к. L2 e

56.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
L2
a+B
b+B
+B
+B
b
b
Шаги
6а
2
3’, т.к. L2 e
5

57.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
L2
a+B
b+B
+B
+B
b+B
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5

58.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
L2
a+B
b+B
+B
+B
b+B
М+B
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
Т.к у М больше нет
альтернатив!

59.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
L2
a+B
b+B
+B
+B
b+B
М+B
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в

60.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
Т.к у Т ещё есть
альтернатива!

61.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
q
B1T1M1a+B1T2M1
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1

62.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
q
B1T1M1a+B1T2M1
Шаги
b
b
b
b
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
b
b

63.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
q
B1T1M1a+B1T2M1
b
B1T1M1a+B1T2M1
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
a*Т + B
b
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b

64.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
q
B1T1M1a+B1T2M1
b
B1T1M1a+B1T2M1
q
B1T1M1a+B1T2M2
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
a*Т + B
b*Т + B
b
b
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
6а
Т.к у М ещё есть
альтернатива!

65.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
1
2
1
2
1
2
L1
b
B1T1M1a+B1T1M1
q
B1T1M1a+B1T1M2
q B1T1M1a+B1T1M2b
b B1T1M1a+B1T1M2b
b
B1T1M1a+B1T1M2
b
B1T1M1a+B1T1
q
B1T1M1a+B1T2
q
B1T1M1a+B1T2M1
b
B1T1M1a+B1T2M1
q
B1T1M1a+B1T2M2
q B1T1M1a+B1T2M2 b
Шаги
b
b
b
b
b
b
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
6а
2
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
a*Т + B
b*Т + B
*Т + B
b
b

66.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
q
q
b
b
b
q
q
b
q
q
b
1
2
1
2
1
2
L1
B1T1M1a+B1T1M1
B1T1M1a+B1T1M2
B1T1M1a+B1T1M2b
B1T1M1a+B1T1M2b
B1T1M1a+B1T1M2
B1T1M1a+B1T1
B1T1M1a+B1T2
B1T1M1a+B1T2M1
B1T1M1a+B1T2M1
B1T1M1a+B1T2M2
B1T1M1a+B1T2M2 b
B1T1M1a+B1T2M2 b
L2
a+B
b+B
+B
+B
b+B
М+B
М*T + B
a*Т + B
a*Т + B
b*Т + B
*Т + B
*Т + B
b
b
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
6а
2
3’,т.к. L2 e

67.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
q
q
b
b
b
q
q
b
q
q
b
b
1
2
1
2
1
2
L1
L2
B1T1M1a+B1T1M1 a + B
B1T1M1a+B1T1M2 b + B
B1T1M1a+B1T1M2b + B
B1T1M1a+B1T1M2b + B
B1T1M1a+B1T1M2 b + B
B1T1M1a+B1T1 М + B
B1T1M1a+B1T2 М*T + B
B1T1M1a+B1T2M1 a*Т + B
B1T1M1a+B1T2M1 a*Т + B
B1T1M1a+B1T2M2 b*Т + B
B1T1M1a+B1T2M2 b *Т + B
B1T1M1a+B1T2M2 b *Т + B
B1T1M1a+B1T2M2 b*Т + B
b
b
b
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
6а
2
3’,т.к. L2 e
5

68.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
q
q
b
b
b
q
q
b
q
q
b
b
1
2
1
2
1
2
L1
L2
B1T1M1a+B1T1M1 a + B
B1T1M1a+B1T1M2 b + B
B1T1M1a+B1T1M2b + B
B1T1M1a+B1T1M2b + B
B1T1M1a+B1T1M2 b + B
B1T1M1a+B1T1 М + B
B1T1M1a+B1T2 М*T + B
B1T1M1a+B1T2M1 a*Т + B
B1T1M1a+B1T2M1 a*Т + B
B1T1M1a+B1T2M2 b*Т + B
B1T1M1a+B1T2M2 b *Т + B
B1T1M1a+B1T2M2 b *Т + B
B1T1M1a+B1T2M2 b*Т + B
b
b
b
b
b
b
b
b
b
Шаги
6а
2
3’, т.к. L2 e
5
6в
6а
1
4,т.к. a b
6а
Т.к у М больше нет
2
альтернатив!
3’,т.к. L2 e
5
6в

69.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
1
2
1
2
1
2
L1
B1T1M1a+B1T2
L2
M*Т + В
b
Шаги

70.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
L2
M*Т + В
T+B
b
b
Шаги
6в
Т.к у Т больше нет
альтернатив!

71.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
L2
M*Т + В
T+B
b
b
Шаги
6в

72.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
q
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
L2
M*Т + В
T+B
Т
b
b
b
Шаги
6в
6а
Т.к у В есть
альтернативы!

73.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
q
q
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
L2
M*Т + В
T+B
Т
М
b
b
b
b
Шаги
6в
6а
1

74.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
q
q
q
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
B1T1M1a+B2T1M1
L2
M*Т + В
T+B
Т
М
a
b
b
b
b
b
Шаги
6в
6а
1
1

75.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2
s
b
b
q
q
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
L2
M*Т + В
T+B
Т
М
b
b
b
b
q
b
B1T1M1a+B2T1M1
B1T1M1a+B2T1М1
a
a
b
b
Шаги
6в
6а
1
1
4,a b

76.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2
s
b
b
q
q
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
L2
M*Т + В
T+B
Т
М
b
b
b
b
q
b
q
B1T1M1a+B2T1M1
B1T1M1a+B2T1М1
B1T1M1a+B2T1М2
a
a
b
b
b
b
Шаги
6в
6а
1
1
4,a b
6а

77.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
s
b
b
q
q
1
2
1
2
1
2
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
q
B1T1M1a+B2T1M1
b
B1T1M1a+B2T1М1
q
B1T1M1a+B2T1М2
q B1T1M1a+B2T1M2b
L2
M*Т + В
T+B
Т
М
b
b
b
b
Шаги
6в
6а
1
1
a
a
b
b
b
b
4,a b
6а
2

78.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2
s
b
b
q
q
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
L2
M*Т + В
T+B
Т
М
b
b
b
b
Шаги
6в
6а
1
1
q
b
q
B1T1M1a+B2T1M1
B1T1M1a+B2T1М1
B1T1M1a+B2T1М2
a
a
b
b
b
b
4,a b
6а
2
q B1T1M1a+B2T1M2b
t B1T1M1a+B2T1M2b
3

79.

1) В -> Т + В
2) В -> T
3) T -> M
4) T -> M * T
5) M ->a
6) M ->b
1
2
1
2
1
2
b
b
b
b
b
В b
b
4,a b
6а
2
М
Т
3
a
М
L1
B1T1M1a+B1T2
B1T1M1a+B1
B1T1M1a+B2
B1T1M1a+B2T1
L2
M*Т + В
T+B
Т
В
М
q
b
q
B1T1M1a+B2T1M1
B1T1M1a+B2T1М1
B1T1M1a+B2T1М2
a
aТ
b
q B1T1M1a+B2T1M2b
t B1T1M1a+B2T1M2b
Вывод: 1 3 5 2 3 6
Шаги
6в
6а
1
1
s
b
b
q
q
+
b

80. Блок-схема алгоритма

G: (P, T, N, S), str
i = j = k = 0; S => L2[k++], state = q
Вывод
h(L1)
2
state =
успех:
str L(G)
t
b
+
L2[k –
q
T?
L2[k –
Нормальное
завершение
+
Шаг 5
L1[j –
Шаг 2
-
2
+
2
Шаг 6а
state = q
+
i=n+1?
У L1[j – есть ещё
альтернативы?
L2=e?
-
-
(*)
L1[j – =S
&& i = 0?
2
(*)
+
2
Шаг 3'
state = b
L2=e?
2
(**)
В
неудача:
str L(G)
Шаг 6б
Т
В
L2=e
В
+
*
Т
М
М
a*b
Аварийное
завершение
М
?
a*b
Шаг 3
state = t
-
(**)
+
Шаг 6в
2
+
Шаг
T?
Шаг 4
state = b
=str[i]?
Т
? L2
L2 e
2

81. Вопросы для повторения

1. Этапы трансляции.
2. Определение грамматики.
3. Что такое БНФ?
4. Что такое прямое порождение?
5. Что такое вывод?
6. Что такое язык, порождаемый грамматикой?
7. 2 способа задания вывода цепочки.
8. Что такое основа?
9. Что такое разбор?
10. Как разбор связан с выводом?
11. Что такое распознаватель?
12. 2 стратегии синтаксического анализа.
13. Определение не укорачивающей грамматики.
14. Определение грамматик по Хомскому.