Разработка компиляторов
Алгоритм построения конечного автомата
Теперь обсудим алгоритм построения анализатора. Во-первых, пополним грамматику. Обозначим T множество состояний, E - множество переходов.
T = {closure ([S'->.S])}; E = {}; do { for (каждого состояния I из T) { for (каждой ситуации [A->w.Xv] из I) { J = goto (I, X); T+={J}; /* ко множеству состояний добавляется новое состояние */ E+=(I->J); /* ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X */ } } } while (E или T изменились);
Поскольку для символа $ операция goto (I, $) не определена, мы выполняем действие accept .
