Преобразование нескольких регулярных выражений в DFA при реализации lex

Question

Я учусь писать генератор лексического анализатора (клон lex) на основе регулярного выражения для алгоритма прямого перевода DFA, описанного в «Книге Дракона».

Теперь я могу успешно преобразовать регулярное выражениев DFA, но я застрял, когда есть несколько правил, например:

abc { printf("abc"); }
a* { printf("a*); }

Я могу преобразовать abc и a* в два графика DFA, но как объединить эти два графика DFA толькоодин

Answer 1

Я действительно делал это упражнение несколько лет назад - я создал интегрированный лексер и LALR-парсер в c ++, используя книгу в качестве руководства. Книга на самом деле рассказывает вам, как преобразовать регулярные выражения непосредственно в NFA, а затем вы конвертируете NFA в DFA, используя алгоритм, который я не совсем помню сейчас. Для поддержки нескольких правил вам просто нужно создать NFA для каждого. Затем вы создаете новое начальное состояние и создаете эпсилон-переход из начального состояния в начальное состояние каждого из NFA, созданных для каждого правила. По крайней мере, это то, что я могу вспомнить, не просматривая мой код.