Синтаксическое дерево.

Это графическое изображение всех выводов в данной цепочке символов, в данной грамматике.

Вершиной синтаксического дерева является начальный символ грамматики.

P

A S P

Id

:= E ; S ; P

a P .

T A S ; S

M If WH

C

30

Листья – терминальные символы.

Если вершина дерева является нетерминалом, то ее дочерними вершинами будут элементы правой части правила, используемого при выводе данной цепочки.

Синтаксический анализ.

.б(вершина)

. .

(набор листьев)

Существуют нисходящий и восходящий анализы.

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

Восходящий анализ - заключается в том, что здесь построение начинается с листьев. В соответствии с правилами грамматики осуществляется свертка до тех пор, пока они все не соединятся с вершиной.

Нисходящий синтаксический анализатор с возвратом.

Алгоритм:

Содержит 4 переменные:

S – {f,b} f-вперед; b-назад;

Х – исходный текст программы;

L – входной магазин (стек) (расположена синтенциальная формула, выведена из начального символа к текущему шагу);

- выходной магазин (использованное для вывода правила грамматики).

На вход подается входная строка Х и грамматика

(f,x,б,e) б-начальный символ грамматики;

1. Развертка.

-вершина, в ней нетерминал (вершина входного магазина находится слевав);

2.

а-поместили в выходной магазин

- в вершине магазина находится терминал и он совпадает с 1-м символом входной строки.

3.

- входная строка пуста и входной магазин пуст

- содержит левосторонний вывод входной цепочки.

4.

- переходим в состояние возврата, с этого момента начинается возврат.

5. Возврат по входной строке.

- у выходного магазина вершина справа – терминал.

6.

- выходной магазин пустой, входной содержит 1-ый символ грамматики;

- входная строка не принадлежит языку или программа записана с ошибкой, вывод построить нельзя.

7. а).

-номер какого-то правила, либо может быть терминал.

Если такого правила нет, то:

б).

Пример:

правило

На вход ab

-начальное состояние

- если уберем все терминалы, то оставшиеся правила дают вывод:

- левосторонний вывод.