Лексический анализ — извлечение токенов из DFA, созданных напрямую

Описание (f)lex — фактически любое лексическое описание — представляет собой набор регулярных выражений. Однако все практические алгоритмы соответствуют одному регулярному выражению. Это не проблема, потому что мы можем просто построить одно регулярное выражение, состоящее из чередования всех возможных токенов. Таким образом, первые четыре шаблона в вашем примере будут объединены в

(if|then|else|[a-zA-z][a-zA-Z0-9]*)

Прямой алгоритм regex->DFA, приведенный в книге Dragon, работает с расширенным регулярным выражением, построенным путем добавления одного маркера конца ввода в конце регулярного выражения. Состояния, которые включают положение этого расширенного маркера, являются принимающими состояниями.

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

Состояния в алгоритме regex->DFA соответствуют наборам позиций в исходном регулярном выражении. (Если вы написали алгоритм, вы знаете, что такое позиция, но ради того, чтобы другие люди читали дальше, позиция — это, грубо говоря, смещение в регулярном выражении символьного литерала (или подстановочного знака), которое только что совпало. Не все смещения в регулярном выражении являются позициями в этом смысле; например, круглые скобки и операторы не соответствуют ни одному совпадающему символу. И весь литерал класса символов является одной позицией. Но часто легче думать о позициях, как если бы они были просто смещения байтов в самом регулярном выражении.)

Это полезно, потому что мы можем сразу увидеть по названию состояния, в котором в регулярном выражении достигнуто сканирование. А поскольку каждый шаблон в комбинированном регулярном выражении имеет различный диапазон позиций, мы знаем, в каком правиле мы находимся. Если шаблон сработал, номер правила говорит нам, какое действие выбрать. Если состояние принятия находится в более чем одном правиле, мы просто выбираем правило с наименьшей позицией, потому что это алгоритм (f)lex для выбора между двумя самыми длинными совпадениями одинаковой длины: выберите первое в определении сканера.

Но, как мы отмечали ранее, единственное принимающее состояние — это состояние, соответствующее маркеру конца ввода в конце расширенного шаблона, которого нет ни в одном из исходных шаблонов. Поэтому, если мы хотим идентифицировать фактический шаблон, нам нужно дополнить каждое отдельное правило его собственным конечным маркером, а не использовать один конечный маркер для всех правил. Кроме того, маркер конца не может быть ограничен только соответствием (вымышленному) символу в конце ввода, потому что нас интересует самый длинный совпадающий префикс, а не полное совпадение. Таким образом, мы должны рассматривать конечный маркер как соответствующий любому отдельному символу, включая вымышленный символ конца ввода. (Это делает его более подстановочным знаком, чем ., поскольку . соответствует только реальным символам, а не вымышленным символам конца ввода, а также - в реальной реализации (f)lex - только реальным символам, которые не являются символами новой строки. , Но в принципе это своего рода подстановочный знак, за исключением того, что он не поглощает символ, которому соответствует.)

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

(if#|then#|else#|[a-zA-z][a-zA-Z0-9]*#)

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