Нисходящий преобразователь (распознаватель)

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

Пусть p = 1,2,3,… k – левый разбор цепочки W Î L(G). Зная p, можно построить дерево разбора. Начинают с корня, помеченного начальным символом.

Пусть 1-е правило имеет вид S = x₁,…,x_k. Нужно присоединить k потомков к вершине S. Если x_i – первый слева – нетерминал, то 2-е правило будет иметь вид x_i = y₁…y_e. По этому принципу строим все дерево.

Простая СУ – схема: Т=íN, S, D, R, Sý отображает разбор в левом или правом выводе.

Правила из R, которые имеют вид А:=a, b, представим в виде

A:= a, ia^’, где i – номер правила.

a^’:= b\T (в цепочке b удалим все терминальные символы).

T

T

F

*

E

T

T

+

F

i

E

(E)

F

F

i

i

E 2T 3TF 4F 5E 6 1ET 2T 4F 4F 6

Если контекстно свободная грамматика G является LL-грамматикой, то с помощью метода итерационного спуска можно построить синтаксический анализатор языка L(G), который явно не использует стек, однако алгоритм его функционирования включает ряд рекурсивных процедур, которые обычно реализуют с помощью стека.

В простейшей форме метод рекурсивного спуска предоставляет удобную возможность построения лексического анализатора (распознавателя символов) языка, порожденного LL(1)-грамматикой G=(N, S, P, S). Такой лексический анализатор каждому символу из множества N S ставит в соответствие единственную процедуру, с помощью которой для любой строки языка можно однозначно определить, выводима она из этого символа или нет.

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

А также недетерминированный нисходящий распознаватель М1. Тогда его называют левым анализатором. То есть он моделирует левый вывод в грамматике G по правилу:

d (q, e, A) = (q, a, i) A:= a. (i – номер правила, записывается в выходную цепочку).

Анализатор каждый раз развертывает нетерминал, распознанный наверху магазина, в соответствии с некоторым правилом из Р, а также одновременно выдает номер этого правила.

Если наверху магазина находится терминальный символ, то М1 по правилу:

d (q, а, а) = (q1, е, е) проверяет, совпадает ли он с соответствующим символом во входной цепочке.

М_L {(q₀,q₂), (*,+,(,),i), (N T $), (1,…,6), (d, q₀, $, q₁)};

(*,+,(,),i) – входной алфавит;

(N T $) – алфавит магазинных символов;

(1,…,6) – номера правил на выходе;

q₀ – начальный символ автомата;

$ - начальный символ магазина;

Q*E*Г -> Q*Г^**D^*.

1. (q₀, e, E) = (q₀, E+T, 1);

2. (q₀, e, E) = (q₀, T, 2);

3. (q₀, e, T) = (q₀, T*F, 3);

4. (q₀, e, T) = (q₀, F, 4);

5. (q₀, e, F) = (q₀, (E), 5);

6. (q₀, e, F) = (q₀, i, 6);

7. (q₀, a, a) = (q₀, e, e);

8. (q₀, e, $) = (q₀, e, p) p - левый разбор цепочки.

(q₀, i*(i+i), E, e) |¾ (q₀, i*(i+i), T, 2) |¾

(q₀, i*(i+i), T*F, 23) |¾ (q₀, i*(i+i), F*F, 234) |¾

(q₀, i*(i+i), i*F, 2346) |¾ (q₀, *(i+i), *F, 2346) |¾

(q₀, (i+i), F, 2346) |¾ (q₀, (i+i), (E), 23465) |¾

(q₀, i+i), E), 23465) |¾ (q₀, i+i), E+T), 234651) |¾

(q₀, i+i), T+T), 2346512) |¾ (q₀, i+i), F+T), 23465124)|¾

(q₀, i+i), i+T), 234651246) |¾ (q₀, i), T), 234651246) |¾

(q₀, i), F), 2346512464) |¾ (q₀, i), i), 23465124646) |¾

(q₀, e, e, 23465124646) |¾ (q₁, e, e, 23465124646)

Левый анализатор – недетерминированная процедура. Чтобы ею пользоваться, необходимо уметь моделировать ее детерминированно. Существует класс грамматик (L,L), для которых левый разбор можно делать детерминированным. Для этого анализатору необходимо предоставить возможность, которая при считывании входной (исследуемой) цепочки позволяла бы заглядывать на k символов вперед, и очередной шаг делался бы после анализа полученной информации.

L, L – означает, что читается слева направо, и выдается левый разбор.

L, R - означает, что читается слева направо, и выдается правый разбор.

Левые и правые разборы используются в зависимости от той или иной грамматики.

Моделирование МП –преобразователя. Нисходящий анализ с возвратом