Похожие презентации:
Нисходящий и восходящий распознаватели
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. Пример
AG1:
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. Пример
AG1:
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. Пример
AG1:
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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.
sL1
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), stri = 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. Определение грамматик по Хомскому.