Недетерминированный разбор

При выполнении разбора по регулярной грамматике может оказаться, что несколько разных нетерминалов имеют правила вывода с одинаковыми правыми частями, и поэтому неясно, к какому из них делать свертку (см. п.3.3). В терминах диаграммы состояний это означает, что из одного состояния выходит несколько дуг, ведущих в разные состояния, но помеченных одним и тем же символом. Такой грамматике будет соответствовать недетерминированный конечный автомат.

Недетерминированный конечный автомат(НКА) – это пятерка

(K, V, F, H, S), где

K - конечное множество состояний;

V - конечное множество допустимых входных символов;

F - отображение множества K ´ V в множество подмножеств K;

H Ì K - конечное множество начальных состояний;

S Ì K - конечное множество заключительных состояний.

F(A,t) = {B₁,B₂,...,B_n} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний B_i, i = 1, 2, ... ,n.

Таким образом, недетерминизм автомата заключается в следующем:

1) находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в общем случае в одно из нескольких возможных состояний;

2) автомат может делать переходы по ε .

Пример 3.4

Для грамматики G = ({a,b, ^}, {S,A,B}, P, S), где

P={ S ® A^, A ® a | Bb, B ® b | Bb}

разбор будет недетерминированным (так как у нетерминалов A и B есть одинаковые правые части Bb). Данной грамматике будет соответствовать полностью определенный недетерминированный конечный автомат, граф переходов которого представлен на рис. 3.9. : M = ({H, A, B, ER, S}, {a, b, ^}, F, H, {S}), где

F: F(H, a)=A, F(H, b)=B, F(H, ^)=ER, F(A, ^)=S, F(A, a)=ER, F(A, b)=ER, F(B, b)={A, B},F(B, a)=ER, F(B, ^)=ER, F(ER, a)=ER, F(ER, b)=ER,

F(ER, ^)=ER.

Рис. 3.9. Граф переходов полностью определенного

недетерминированного конечного автомата

В случае недетерминированного разбора входной цепочки символов можно предложить алгоритм, который будет перебирать все возможные варианты сверток (переходов) один за другим; если цепочка принадлежит языку, то будет найден путь, ведущий к успеху; если будут просмотрены все варианты, и каждый из них будет завершаться неудачей, то цепочка языку не принадлежит. Однако такой алгоритм практически неприемлем, поскольку при переборе вариантов мы, скорее всего, снова окажемся перед проблемой выбора и, следовательно, будем иметь "дерево отложенных вариантов".

Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат (ДКА), который на каждом такте работы имеет возможность перейти не более чем в одно состояние, а также не может делать переходы по ε.

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

Это означает, что для любого НКА всегда можно построить детерминированный КА, определяющий тот же язык. Моделировать работу ДКА значительно проще, чем работу произвольного конечного автомата, поэтому при построении компиляторов используемый произвольный КА обычно стремятся преобразовать в ДКА.