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

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

Алгоритм:

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

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

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

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

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

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

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

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

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

2.

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

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

3.

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

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

4.

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

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

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

6.

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

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

7. а).

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

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

б).

Пример:

правило

На вход ab

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

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

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

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

Анализатор с возвратом работает для всех грамматик, которые не являются леворекурсивными.

LL(1) анализатор можно построить для значительного более узкого числа грамматик.

- левая рекурсия.

Вывод из предыдущего примера:

Табл:

Символы

правила

- если на входе «а», то применим 1-е правило, если на входе «b», то применяем 2-е правило.

T(A,a)=i

T-таблица

- строки помечены терминалами;

- столбцы помечены нетерминалами;

(f,x,б,e)

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

Если T(A,a)=i Если T(A,a)=Ø, то неудача

:

2.

- взаимное уничтожение;

3. -успех.

Неудача будет, если в таблице пустая клетка, т.е. нет i.

Не каждая грамматика является LL(1) грамматикой, иногда грамматику можно преобразовать в LL(1).

Грамматика ML для правила LL(1).

По правилу:

Z→</>/<=/>=/=/<>

Таблица с альтернативными правилами:

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США