double arrow

Восходящий разбор

Алгоритм нисходящего разбора

Леворекурсивные грамматики неприменимы для нисходящего разбора.

Используются 2 стека (магазина), счетчик, в котором хранится текущая позиция указателя.

Пусть задана не леворекурсивная грамматика G{N, S, P, Z}. Правила из Р занумерованы для каждого нетерминала А Î N. Упорядочим его альтернативы:

А = a1 | a2 | a3.

A1 = a1.

A2 = a2.

A3 = a3.

Конфигурацию алгоритма будем характеризовать четверкой: (S, i, L1, L2), где S – состояние алгоритма.

i – счетчик положения входного указателя.

L1 – стек, содержащий историю используемых альтернатив и терминальных символов, которые прошли удачное сравнение.

L2 – вершина слева хранит левовыводимую цепочку, ту ее часть, которая получилась к данному моменту в результате развертки нетерминала.

(q, i, $a, Ab) |¾ (q, i, $a, aib). Если существует Ai = ai (А имеет i альтернатив).

(q, i, $g, aaib) |¾ (q, i+1, $gAia, aib). Если Ai = аai и произошло сравнение, то а (терминал входной цепочки) = а (терминал в растущем дереве).

Примечание: i и индекс у ai – это две разные вещи!

(q, n+1, $p, e) |¾ (t, n+1, $, e);

h(Ai) = i h(p) – номера используемых правил;

h(a) = e.

неудачное сравнение: (q, i, $gAia, b) |¾ (q, i, $gAia, b) |¾

теперь возврат по дереву |¾ (q, i-1, $g, Aiab).

Пример:

E1:= T+E.

E2:= T.

T1:= F*T.

T2:= F.

F1:= (E).

F2:= a.

(q, 1, $, E1) |¾ (q, 1, $E1, T+E) |¾ (q, 1, $E1T1,F*T+E) |¾ (q, 1, $E1T1F2,a*T+E) |¾

(q, 2, $E1T1F2a,*T+E) |¾ (b, 2, $E1T1F2a,*T+E) |¾ (b, 1, $E1T1,F*T+E) |¾

(q, 1, $E1T2,F+E)|¾ (q, 1, $E1T2F2,a+E)|¾ (q, 3, $E1T2a+, E) |¾ (q, 3, $E1T2a+E1, T+E) |¾

(q, 3, $E1T2a+E1T1,F*T+E).

а+а#

E:=E+T|T

|→ |→ |→

|→ |→ - a здесь нужна для возможности вернуться, в случае неудачи мы загружаем в стек терминальный символ |→ - неудачное сравнение, возврат по дереву

|→ |→ |→ |→

|→ |→ |→ - удачное сравнение, перемещаем указатель:;

|→ |→ |→ далее мы повторим то же самое, но указатель уже передвинется, сравнение будет удачно, но дерево останется,, и мы вернёмся назад и возьмём вторую альтернативу |→ |→ |→ - пояснения по поводу последней Т2 в последних скобках: машина выбрала первую альтернативу и, столкнувшись с неудачей вернулась и выбрала бы

Т2|→ |→

 

сравниваем удачно

Гомоморфизм.

Должно быть понятно, что каким бы методом («сверху вниз» или «снизу вверх») мы ни воспользовались для синтаксического разбора стро­ки, где G — контекстно свободная грамматика, результат дол­жен быть один (это утверждение справедливо при условии допустимости использования обоих методов), так как эти методы отличаются лишь спо­собами построения деревьев.

Если метод синтаксического разбора «сверху вниз» рекомендует построение указанных деревьев на­чиная с корня, то метод «снизу вверх» рекомендует строить их наоборот, начиная с листьев и кончая корнем дерева. Введенные входные строки в последнем случае анализируются слева направо; получаемые в процессе подстроки сравниваются с правыми частями продукции грамматики, а при совпадении заменяются или приводятся к нетерминальному символу, стоящему в левой части таких продукций. В результате такой замены может быть получена сентенциальная форма грамматики, а затем вся процедура повторяется до тех пор, пока полученная сентенциальная форма не примет вид S, где символом S помечен корень дерева вывода. В результате будет получена последовательность схем вывода и соответствующих им приведе­ний, позволяющая построить дерево вывода от листьев до корня. Каждо­му элементу этой последовательности, очевидно, соответствует один ро­дительский узел дерева вывода.

Рассмотрим грамматику G1, имеющую следующие продукции:

G1 - одноз­начная грамматика, и, следовательно, любой строке соответст­вует единственное дерево вывода.

Например, дерево вывода для строки приведено на рис. 2, д.

а) б) в)

г) д)

Рис. 2. Дерево вывода для строки

Далее каждому дереву вывода соответ­ствует единственная правосторонняя схема вывода, т. е. такая схема вывода, в которой всегда выводится самый правый нетерминальный символ. Так, дереву вывода, рассмотренному в вышеприведенном примере, соответству­ет правосторонняя схема вывода:

.

Рассматриваемый метод синтаксического разбора «снизу вверх», позволит построить такую схему вывода справа налево. Пример построения дерева вывода для строки bbaa$ показан на рис.1. Подстроку, которая приводится, называют основой правосторонней сен­тенциальной формы, или правосторонней простой фразой. Процесс построе­ния дерева вывода для нашего примера иллюстрируется табл.1.

Таблица1

Правосторонняя сентенциальная форма Основа Замещающий символ
bbaa$ а (левый символ) А
bbАа$ а А
bbАА$ bАА А
bА$ С
С$ С$ S

Итак, восходящий разбор связан с отображением входной цепочки в последовательность обращенных правых выводов.

Пусть G(N, S, P, S) – грамматика, правила которой занумерованы 1, 2 … р.

Пусть a - некоторая цепочка в этой грамматике, где a Î (NÈS*).

Тогда правый разбор цепочки a - обращенная последовательность правил, примененных при правом выводе.

1) E:= E+T;

2) E:=T;

3) T:=T*F;

4) T:=F;

5) F:=(E);

6) F:=i.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: