Недетерминированный конечный автомат (разбор сверху-вниз)

КС-грамматики

Нетерминальный символ А порождает произвольную цепочку α терминальных и нетерминальных символов, в т.ч. α=λ

A→α

Можно преобразовывать КС-грамматики так, чтобы не было цепочек A→λ или оставлять одно правило S→ λ.

Правило подстановок идентично праволинейным грамматикам.

Бесполезные нетерминалы – те, которые не могут породить терминальную цепочку.

Процесс порождения в кс-грамматике отличается от автоматной грамматики. Здесь он может быть представлен в виде дерева порождения.

Дерево порождения: S→ABC

Поддерево – вершина и все ее потомки, но без дуги.

Куст – вершина, соединенная с ее потомками.

Листья – вершины, у которых нет потомков.

Ветвь – дуга, соединяющая вершину и ее потомка. (?)

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

Обход слева направо по висячим вершинам дерева – цепочка, полученная при порождении.

Одно дерево – один (из всех возможных) вариант порождения.

Все варианты задает только грамматика, т.к. их чаще всего бесконечное количество.

Метод построения дерева:

Левое каноническое порождение – порождение применяем к самой левой нетерминальной вершине (к самому левому нетерминальному символу в поперечном разрезе).

Правое каноническое порождение - порождение применяем к самой правой нетерминальной вершине (к самому правому нетерминальному символу в поперечном разрезе).

При этом вид полученного дерева будет один и тот же.

Пример кс-грамматики:

S→S+T|T

T→T*F|F

F→(S)|a

| - или

S=>T=>F=>a

S=>S+T=>T+T=>T*F+T=>F*F+T=>a*F+T=>a*(S)+T=>…=>a*(a+a)+a //левое каноническое порождение

Неоднозначная кс-грамматика –если хоть одна порождаемая ею цепочка может быть порождена не менее чем двумя различными деревьями порождения.

Это требует доказательства.

Предыдущий пример – однозначная.

Пример (неоднозначная):

S→S+S|S*S|(S)|a

a+a*a –может быть порождена и той и другой грамматиками, но деревья отличаются

S=>S+T=>S+T*F=>T+T*F=>F+F*F=>a+a*a.

Язык – однозначный, если существует хотя бы одна однозначная грамматика, его порождающая.

Если не существует ни одной однозначной грамматики, порождающей язык, то такой язык – неоднозначный.

Т.е. для однозначного языка могут существовать неоднозначные грамматики.

Устанавливаем, принадлежит ли цепочка данному языку (может ли цепочка быть порождена данной грамматикой).

Это называется процессом распознавания.

Распознавание для КС-языка – попытка построить дерево порождения для данной цепочки.

2 канонических случая грамматического разбора:

· LL-анализ (L – входная цепочка просматривается слева-направо, L – мы пытаемся построить дерево в соответствии с левым каноническим порождением).

Анализ сверху-вниз.

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

· LR-анализатор (L - входная цепочка просматривается слева-направо, R - мы пытаемся построить дерево в соответствии с правым каноническим порождением)

Правое каноническое порождение соответствует еще не построенной части дерева порождения.

Анализ снизу-вверх.

Магазинный автомат– частный вид машины Тьюринга, развитие конечного автомата. Входная цепочка просматривается слева-направо, но на некоторых элементах может приостанавливаться (т.е. сдвиг не на каждом шаге).

По сравнению с конечным автоматом, там есть «магазин» (стек) – вспомогательная лента, которая работает по принципу магазина.

Магазинный автомат, который генерирует LL-разбор по заданной грамматике:

На каждом шаге. Работа магазинного автомата зависит от трех параметров: входного символа (a), номера состояния (q), верхнего символа в стеке (B). В результате:

(a,q,B) →(a’,q’,B’).

Определим правила движения в магазинном автомате:

Записывать в магазин будем не только терминальные, но и нетерминальные символы (хотя с ленты считываться будут только терминальные).

1. аЄ ∑ (a,q,a)→( λ,q,λ)

2. A→α (λ,q,A)→( λ,q, α^-1)

В начале работы автомата головка установлена против самого левого символа во входной ленте, а в магазин записан начальный нетерминал. Автомат работает пока можно применить хотя бы одно из правил. В конце может быть два варианта: входная цепочка прочитана, магазин пуст. Остальные варианты не допускаются. Для этого автомата не нужны разные состояния.

(?)Нужно доказать, что построенный так автомат допускает только те цепочки, которые порождаются кс-грамматикой, по которой мы и строили автомат.

Если начинается с терминала и символы одинаковые, то нам удалось сопоставить определенное количество символов цепочки с тем деревом, которое неявно строит автомат.

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

Пример магазинного автомата с LR-анализом:

Для этого нам необходимо ввести вспомогательный символ (как символ-ограничитель конца в автоматных грамматиках)

1. аЄ ∑ (a,q, λ)→( λ,q,a) – перенос (из входной цепочки в магазин)

2. A→α (λ,q, α^-1)→( λ,q,A) – свертка (сворачивание)

3. (_|_,q,_|_S) →( λ,q₁, λ) – завершающее условие. Обозначающее, что S явился корнем дерева (цепочка дочитана до конца, состояние q₁, магазин пуст).

Недетерминированный конечный автомат (разбор сверху-вниз)

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

A→α₁| α₂| …| α_k

Алгоритм должен сделать это предсказание, анализируя очередные входные символы цепочки. Правда, не все грамматики обладают этим свойством.

«Левая рекурсия».

Пример,

S→S+T|T

T→T*F|F

F→(S)|a

красные – леворекурсивные правила.

Могут возникнуть зацикливания.

Чтобы этого избежать, необходимо сделать преобразование:

Рекурсивный спуск

Для каждого нетерминала пишется своя процедура. Спуск идет по дереву порождения. Метод неплох для простых грамматик, но для сложных он слишком громоздок. При любом изменении грамматики, необходимо переписывать эти программы, т.к. они тонко привязаны к порождающим правилам самой грамматики. Еще один плюс - наглядность при написании процедур. Нет необходимости пользоваться стеком.

1. Избавление от левой рекурсии

2. Если для одного и того же нетерминала есть несколько правых частей, то эти правые части должны начинаться с разных терминалов. А если с нетерминалов, то должна остаться в правой части только одна альтернатива.

Избавление от левой рекурсии:

Запись правых частей с использованием транзитивного замыкания. Рассмотрим на примере, описанном выше.

Возможные цепочки после применения первого правила: T, T+T, T+T+T, …

С помощью регулярного выражения можно получать те же цепочки:

Готовая грамматика: S→T{+T}* T→F{*F}* F→(S)|a

+T - метасимволы

Будем считать, что здесь тоже есть некоторый заключительный символ. Тогда добавляем еще одно порождающее правило:

Получилось 4 нетерминала, поэтому напишем 4 программы рекурсивного спуска.

Пусть есть несколько глобальных переменных:

C – входная цепочка символов,

i – номер текущего символа

До начала работы i указывает на начало анализируемой конструкции.

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

Каждая программа возвращает истину, если распознано удачно, ложь в противном случае.

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

Function S0:Boolean;

Begin

If (S)

then begin i:=i+1; S0:=C[i]=’ ’ end

else S0:=false;

End;

Function S:Boolean;

P:Boolean;

Begin

P:=T;

While p and C[i+1]=’+’ do

Begin

I:=i+2; p:=T; end;

S:=p;

End;

Function T:Boolean;

P:Boolean;

Begin

P:=F;

While p and C[i+1]=’*’ do

Begin

I:=i+2; p:=F; end;

T:=p;

End;

Function F:Boolean;

Begin

If C[i]=’(’

then begin i:=i+1; if S and C[i+1]=’)’

then begin i:=i+1; F:=true end

else F:=false

end

else F:=C[i]=’a’;

End;

Ручной прогон:

Пример, в котором ошибка во входной цепочке:

Если нетерминальных символов m, то правил порождения не больше m. И для продвижения на 1 символ нужно сделать максимум m шагов. Тогда трудоемкость O(n*m).

Для анализатора в форме Грейбах – O(2n)

Нормальная форма Грейбах

В любом порождающем правиле правая часть начинается с терминального символа.

S→S+T|T

T→T*F|F

F→(S)|a

Принцип: Удалить левую рекурсию.

A→A_β|γ

A→γB

B→βB|λ

При строгом рассмотрении λ не должна быть в НФГ, но часто такое допускается. Тогда это называется обобщенной НФГ.

A→Bγ

B→β1|β2|…

A→ β1γ; A→ β2γ; … продолжаем пока можем

Если осталась левая рекурсия, то получим зацикливание.

Однако кроме прямой левой рекурсии существует и косвенная левая рекурсия.

A→B β

B→Aγ

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

Отношение называется first.

A first B (А – нетерминальный символ, В – любой символ)

Бинарное отношение задается бинарной матрицей.

А отн1 В; В отн2 С => А отн1Хотн2 С

Находим транзитивное замыкание отношения. Единицы на главной диагонали косвенную и прямую левую рекурсию.

· Строим отношение first

· Транзитивное замыкание отношения

· Если есть косвенная левая рекурсия, сводим ее к прямой

· Избавление от прямой левой рекурсии

· Избавляемся от нуль-порождений, если они есть

нуль-порождение:B→λ

· Подстановками делаем замену до тех пор, пока любая правая часть не начинается с терминального символа

Пример:

LL(1) анализ

LL(1) анализ – анализ сверху-вниз , «1» означает на сколько символов анализатор заглядывает вперед. Т.о. этот анализатор – самый слабый, но для практики походит.

Принцип работы:

Начале в стеке нетерминал S0. Если в стеке символ терминальный, то удаляем его, продвигаемся по цепочке. Если верхний символ стека нетерминальный, то из таблицы применяем порождающее правило для соответствующих левой и правой частей.

Принцип построения таблицы: строки – верхний нетерминальный символ стека, столбцы – терминальные символы.

В большинстве случаев анализатора LL(1) вполне достаточно.

Трудоемкость: n*k.

Не нашли, что искали? Воспользуйтесь поиском по сайту: