2015-06-28
356
1 Проверим нетерминалы на достижимость и продуктивность:
а) нетерминал S достижим (начальный символ грамматики); A достижим (в соответствии с правилом (1));
б) S продуктивен (в соответствии с правилом (2)); A продуктивен (в соответствии с правилом (1)).
2.Построение МП –распознаватель(ранее доказано, что задана q –грамматика):
– входной алфавит V={a,b,c,–|};
– множество магазинных символов {S,A,a,#};
– начальное содержимое магазина S,#;
– управляющая таблица имеет вид(см. рис. на след. стр.).
3.Проверка работы МП –распознавателя.
Выведем с использованием правил грамматики контрольную цепочку для проверки МП –распознавателя:
1 3 1 3 1 4
S à aA à acSa à acaAa à acacSaa à acacaAaa à acacaaa
Примечание: Поле для состояний осталось незаполненным, т.к. заполнять его не имеет смысла (состояние только одно).
Результаты работы МП –распознавателя при разборе цепочки acacaaa представим в виде таблицы:
| Необраб. цепочка | Обр. симв. | Верхн симв магаз. | Содерж. магазина | Действие с магаз. | Действ. с вход. симв. |
| acacaaa--| | a | S | S# | Зам.A | П |
| cacaaa--| | c | A | A# | Зам.Sa | П |
| acaaa--| | a | S | Sa# | Зам.A | П |
| caaa--| | c | A | Aa# | Зам.Sa | П |
| aaa--| | a | S | Saa# | Зам.A | П |
| aa--| | a | A | Aaa# | Выт.A | Д |
| aa--| | a | a | aa# | Выт.a | П |
| a--| | a | a | a# | Выт.a | П |
| --| | --| | # | # | Доп. | -- |
Контрольная цепочка будет допущена построенным МП –распознавателем.
|
|
|
7.5 Задачи к главе 7
Используя процедуры эквивалентных преобразований, упростить заданные КС –грамматики и построить для распознания порождаемых ими языков МП –распознаватели (левая часть первого правила в множестве Р – начальный символ грамматики).
1 P = { S à abC 2 P = { Z à baSb 3 P = { A à dQ
S à bcC S à aA A à S
S à dC A à qAa Q à Qde
C à bB B à q Q à d
A à cA A à a S à A
B à d }. S à e }. A à e}.
4 P = { A à aB 5 P = { F à fdS 6 P = { D à Dbc
B à Z F à Z D à aS
Z à ab Z à a S à bc
Z à bA Z à F S à A }.
D à d }. Z à fbS
S à d }.
7 P = { A à bB 8 P= { S àaQ 9 P = { S àdA
A à D S à cAb S àaB
B à cBa Q à bB A àAda
B à a B à a A à d
D à abC }. B à b B à S
B à c }. A à e}.
10 P = { N à A 11 P = { S à cC 12 P = { S à A
N à aB S à aA S à B
B à aNb A à aAc A à Abc
A à bc A à bbA A à b
A à bA A à ccA B à D }.
C à abc }. C à e }.
13 P = { N à bAc 14 P = { Z à qNa 15 P = { Z à aQ
N à bcQ Z à A Q à B
Q àcb N à Q Q à Qzc
A à A Q à ca Q à z
B à A Q à d B à DB }.
Q à e}. Q à fq }.
16 P = { N à qaZ 17 P = { A à bB 18 P = { Q à aaC
N à qbZ A à cC Q à abC
N à A C à abc Q à acC
A à d C à B S à aQ
A à N Q à acb S à ca
A à qcZ C à e}. C à Q }.
Z à qaq }.
С п и с о к л и т е р а т у р ы
1 Ахо А.,Ульман Дж. Теория синтаксического анализа, перевода и компиляции.– М: Мир, 1978.– Т.1,2.
|
|
|
2 Горбатов В.А. Основы дискретной математики.– М.: Высш. школа, 1986.– 324 с.
3 Кемени Дж.,Снелл Дж.,Томпсон Дж. Введение в конечную математику.– М.: Мир, 1965.– 486 с.
4 Кузнецов О.П.,Адельсон–Вельский Г.М. Дискретная математика для инженера.– М.: Энергоатомиздат, 1988.– 480 с.
5 Льюис Ф. и др. Теоретические основы проектирования компиляторов.– М.: Мир, 1979. – 586 с.
6 Новиков Ф.А. Дискретная математика для программистов.– СПб.: Питер, 2000. –304 с.:ил.
