2. Если j>1, то возьмем k (1£ k <j) как наименьшее из чисел, для которых существует правило $ (A ® BC)ÎP, BÎTi,k, CÎTi+k,j–k (таких правил может быть несколько). Пусть правило A®BC имеет номер m. Тогда нужно выдать этот номер m, а затем вызвать сначала R(i,k,B), потом R(i+k,j–k,C).
Для получения цепочки вывода нужно вызвать R(1,n,S).
На основании полученной последовательности номеров правил строится левосторонний вывод для заданной грамматики G и входной цепочки a. Þ Данный алгоритм позволяет решить задачу разбора.
Вернёмся к нашему примеру. Поскольку для построения вывода нужно будет выдавать номера правил, удобнее переписать все правила грамматики G по отдельности, перенумеровав их:
Пример: Запишем грамматику G в виде:
|
(1) S ® AA (2) S ® AS (3) S ® b |
(4) A ® SA (5) A ® AS (6) A ® a |
Для получения всей последовательности номеров правил вывода нужно вызвать R(1,n,S), т.е. в нашем случае R(1,5,S).
1) R(1,5,S): i=1, j=5. Поскольку j>1, нужно взять такое минимальное k, что существует правило $ (S ® BC)ÎP, BÎT1,k, CÎT1+k,5–k. Раз k должно быть минимальным, начинаем проверку с наименьшего из возможных: k=1, т.е. должно $ (S ® BC)ÎP, BÎT1,1=’A’, CÎT2,4=’A,S’. Такое правило есть: S ® AA (либо S ® AS), его номер 1 (либо 2). Условимся брать первое по порядку подходящее правило. Тогда нужно выдать его номер 1, а затем вызвать сначала R(1,1,A), потом R(2,4,A).
2) R(1,1,A): i=1, j=1. $ (A®a1=’a’)ÎP, это правило с №6.
3) R(2,4,A): i=2, j=4. Найдем минимальное k, такое что $ (A ® BC)ÎP, BÎT2,k, CÎT2+k,4–k. Проверим k=1, т.е. должно $ (A ® BC)ÎP, BÎT2,1=’S’, CÎT3,3=’A,S’. Такое правило есть: A ® SA, его номер 4. Тогда нужно выдать этот номер 4, а затем вызвать сначала R(2,1,S), потом R(3,3,A).
4) R(2,1,S): i=2, j=1. $ (S®a2=’b’)ÎP, это правило с №3.
5) R(3,3,A): i=3, j=3. Найдем минимальное k, такое что $ (A ® BC)ÎP, BÎT3,k, CÎT3+k,3–k. Возможно только k=1 или 2. Проверим k=1, т.е. должно $ (A ® BC)ÎP, BÎT3,1=’A’, CÎT4,2=’A,S’. Такое правило есть: A ® AS, его номер 5. Тогда нужно выдать этот номер 5, а затем вызвать сначала R(3,1,A), потом R(4,2,S).
6) R(3,1,A): i=3, j=1. $ (A®a3=’a’)ÎP, это правило с №6.
7) R(4,2,S): i=4, j=2. Найдем минимальное k, такое что $ (S ® BC)ÎP, BÎT4,k, CÎT4+k,2–k. Единственно возможно k=1, т.е. должно $ (S ® BC)ÎP, BÎT4,1=’A’, CÎT5,1=’S’. Такое правило есть: S ® AS, его номер 2. Тогда нужно выдать этот номер 2, а затем вызвать сначала R(4,1,A), потом R(5,1,S).
8) R(4,1,A): i=4, j=1. $ (A®a4=’a’)ÎP, это правило с №6.
9) R(5,1,S): i=5, j=1. $ (S®a5=’b’)ÎP, это правило с №3.
Процесс закончился. Получили последовательность использованных правил: 1,6,4,3,5,6,2,6,3. Построим вывод: S Þ(1)AA Þ(6)aA Þ(4)aSA Þ(3) ÞabA Þ(5)abAS Þ(6)abaS Þ(2)abaAS Þ(6)abaaS Þ(3)abaab.
Поскольку рассмотренная грамматика не является однозначной, можно было выбирать другие номера правил и, соответственно, цепочка вывода могла получиться иной.
Алгоритм Эрли
Для заданной грамматики G(VT,VN,P,S) и цепочки символов a=a1a2…an, aÎVT*, ½a½=n алгоритм строит последовательность «списков ситуаций» I0, I1, …, In, которая организована несколько сложнее, чем простая таблица. Каждая ситуация, входящая в список Ij для входной цепочки a, представляет собой структуру специального вида. На основании полученного списка ситуаций можно построить всю цепочку вывода и получить номера применяемых правил.
В нашем курсе данный алгоритм подробно рассматриваться не будет.
Алгоритм Эрли также является универсальным и имеет полиномиальную сложность, как и предыдущий рассмотренный алгоритм. Для произвольной КС-грамматики он имеет такие же оценки. Для однозначной КС-грамматики время его работы имеет квадратичную зависимость, а для некоторых более узких классов его характеристики ещё улучшаются. В целом он обладает лучшими характеристиками среди всех универсальных алгоритмов, хотя и более сложен в реализации.
3.4.3 Распознаватели
КС-языков без возвратов –
основные принципы
Рассмотренные выше распознаватели КС-языков универсальны, но имеют неудовлетворительные характеристики; в то же время для языков программирования нужнее эффективность работы, чем универсальность. Как правило, компилятор имеет дело с языком, принадлежащим к какому-то более узкому классу. Например, грамматика синтаксических конструкций языков программирования должна быть однозначной, значит, она относится к классу детерминированных КС-языков. Для такого языка удается построить распознаватель, имеющий определённые ограничения, но обладающий лучшими характеристиками, чем универсальный.
Проблема преобразования КС-грамматик алгоритмически неразрешима, т.е. процесс приведения грамматики к заданному виду не формализован и требует участия человека. Если какая-то грамматика не принадлежит к требуемому классу, то возможно, что её удастся привести к нему путём преобразований.
Существуют два принципиально различающихся класса распознавателей – нисходящие, порождающие цепочки левостороннего вывода и строящие дерево сверху вниз, и восходящие, порождающие цепочки правостороннего вывода и строящие дерево снизу вверх. Считывание входной цепочки обычно осуществляется слева направо.
Нисходящие распознаватели основаны на алгоритме с подбором альтернатив. В них используются методы, позволяющие однозначно выбрать ту или иную альтернативу на каждом шаге работы МПА.
Восходящие распознаватели основаны на алгоритме «сдвиг-свёртка». В них используются методы, позволяющие однозначно выбрать между выполнением переноса или свёртки на каждом шаге работы расширенного МПА, а в случае свёртки однозначно выбрать необходимое правило.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.