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

Пример 3.2

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

P={ S ® C^, С ® Ab | Ba, A ® a | Ca, B ® b | Cb} лексический анализатор будет таким:

#include <stdio.h>

int scan_G(){

enum state {H, A, B, C, S, ER}; /* множество состояний */

state CS; /* CS - текущее состояние */

FILE *fp; /*указатель на файл,в котором находится анализируемая цепочка */

int c;

CS=H;

fp = fopen ("data","r");

c = fgetc (fp);

do {switch (CS) {

case H: if (c == 'a') {c = fgetc(fp); CS = A;}

else if (c == 'b'){c = fgetc(fp); CS = B;}

else CS = ER;

break;

case A: if (c == 'b') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case B: if (c == 'a') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case C: if (c =='a') {c = fgetc(fp); CS = A;}

else if (c == 'b') {c = fgetc(fp); CS = B;}

else if (c == '^') CS = S;

else CS = ER;

break; }

} while (CS != S && CS != ER);

if (CS == ER) return -1; else return 0;

}

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

Например, для грамматики

G = ({a,b, ^}, {S,A,B}, P, S), где P={ S ® A^, A ® a | Bb, B ® b | Bb}

разбор будет недетерминированным (так как у нетерминалов A и B есть одинаковые правые части - Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

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

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

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

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

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

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

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

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

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

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

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

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

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