3.4.4 Контрольные вопросы
1. Какие существуют модели поведения распознавателей КС-языков?
2. В чём различие по трудоёмкости распознавателя с возвратами и распознавателя с параллельным выполнением копий алгоритма?
3. Каковы ограничения на правила грамматики для применения алгоритма нисходящего разбора с возвратами? Какова их причина?
4. Какого типа грамматики допускают разбор цепочек с помощью алгоритма нисходящего разбора с возвратами?
5. Каковы начальная и заключительная конфигурации алгоритма распознавателя с подбором альтернатив?
6. В какой конфигурации должен оказаться алгоритм распознавателя с подбором альтернатив, чтобы был сделан вывод о недопустимости рассмотренной им цепочки?
7. Какие решения должны приниматься на каждом шаге работы распознавателя с подбором альтернатив?
8. Какого типа грамматики допускают разбор цепочек с помощью алгоритма «сдвиг-свёртка»?
9. Каковы ограничения на правила грамматики для применения алгоритма «сдвиг-свёртка»? Какова их причина?
10. Каковы начальная и заключительная конфигурации алгоритма распознавателя «сдвиг-свёртка»?
11. В какой конфигурации должен оказаться алгоритм распознавателя «сдвиг-свёртка», чтобы был сделан вывод о недопустимости рассмотренной им цепочки?
12. Какие решения должны приниматься на каждом шаге работы распознавателя «сдвиг-свёртка»?
13. Почему в алгоритме восходящего разбора «сдвиг-свёртка» используется расширенный МПА?
14. Какой вид правил грамматики требуется для табличного распознавателя Кока-Янгера-Касами?
15. Какова трудоёмкость алгоритма табличного распознавателя?
3.5 Специальные классы КС-языков и грамматик
3.5.1 Нисходящие распознаватели без возвратов
Основная возможность улучшения алгоритма нисходящего разбора состоит в том, чтобы на каждом шаге работы однозначно выбирать одну из всего множества возможных альтернатив. В таком случае возвратов на предыдущие шаги не требуется, и количество выполняемых шагов алгоритма будет иметь линейную зависимость от длины входной цепочки. Если алгоритм не заканчивается успешно, то входная цепочка не принимается, повторных итераций не производится.
3.5.1.1 Метод рекурсивного спуска
Самым простым способом является выбор одной из множества альтернатив на основании текущего входного символа. Необходимо найти альтернативу, где этот символ присутствует в начале цепочки, находящейся в правой части правила грамматики – на этом принципе основан метод рекурсивного спуска.
Алгоритм разбора по методу рекурсивного спуска
Для каждого нетерминального символа исходной грамматики на основании правил строится процедура разбора, на вход которой подаётся цепочка символов a и положение считывающей головки в этой цепочке i. Если для символа AÎVN в грамматике задано несколько правил, то при разборе выбирается то правило, в котором первый (терминальный) символ правой части совпадает с текущим входным символом: ai=a, (A®ab)ÎP, aÎVT, bÎ(VNÈVT)*. Если такого правила нет, цепочка не принимается. Если оно есть или для символа A в грамматике существует единственное правило A®b, то фиксируется номер правила. Если ai=a в найденном правиле, то считывающая головка передвигается – увеличивается номер i, а для каждого нетерминального символа из цепочки b рекурсивно вызывается процедура его разбора.
Для начала разбора входной цепочки необходимо вызвать процедуру разбора для символа S с параметром i=1. Если в итоге разбора входной цепочки считывающая головка остановится на символе с номером n+1, то разбор закончен, цепочка принята, а выданная последовательность номеров правил представляет собой цепочку вывода.
Данный метод накладывает жёсткие ограничения на правила задающей язык грамматики. Для каждого нетерминального символа A грамматики G разрешаются только два вида правил:
1) (A®b)ÎP, bÎ(VNÈVT)*, и это единственное правило для A;
2) A®a1b1½a2b2½…½anbn, "i aiÎVT, bÎ(VNÈVT)*, и ai¹aj, если i¹j, т.е. все ai различны.
Таким образом, для каждого нетерминала либо должно существовать единственное правило вывода, либо – если их несколько – все правые части правил вывода должны начинаться с разных терминальных символов. Таким условиям удовлетворяет незначительное количество реальных грамматик. Возможно, что грамматика может быть приведена к требуемому виду путём некоторых преобразований.
Проблема приведения произвольной грамматики к указанному виду алгоритмически неразрешима. Возможно только привести некоторые рекомендации, которые могут способствовать приведению грамматики к заданному виду (но не гарантируют этого).
1. Исключение пустых правил.
2. Исключение левой рекурсии.
3. Добавление новых нетерминальных символов. Например, если существует правило A®aa1½aa2½…½aan½b1b1½b2b2½…½bmbm, то заменяем его на два: A®aA¢½b1b1½b2b2½…½bmbm, A¢® a1½a2½…½an.
4. Замена
нетерминальных символов в правилах на цепочки их выводов. Например, если есть
правила A®B1½B2½…½Bn½b1b1½b2b2½…½bmbm,
B1®a11½a12½…½a1k,
…
Bn®an1½an2½…½ank, то
заменяем первое правило на
A®a11½a12½…½a1k½…½an1½an2½…½ank½b1b1½b2b2½…½bmbm
Алгоритм рекурсивного спуска эффективен и прост в реализации, но имеет очень ограниченную применимость.
Рассмотрим пример.
Дана грамматика G({a,b,c},{A,B,C,S},P,S), где правила P имеют вид:
S®aA (1)|bB (2)
A ® a (3)| bA (4)| cC (5)
B ® b (6)| aB (7)| cC (8)
C ® AaBb (9)
Правила грамматики удовлетворяют требованиям метода рекурсивного спуска. Построим для каждого нетерминала процедуру разбора. Будем использовать псевдокод.
Процедура Rule(num);
Записать в вывод номер правила num;
Процедура Proc_S(str,k); {входная строка и номер текущего символа}
Выбор str[k] из:
a: Rule(1);
вернуть Proc_A(str,k+1);
b: Rule(2);
вернуть Proc_B(str,k+1);
иначе вернуть 0;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.