Сопоставление регулярных выражений может быть простым и быстрым Расс Кокс - отличное введение в создание распознавателей с конечными автоматами. Он показывает, как перейти от регулярного выражения к недетерминированным конечным автоматам к детерминированным конечным автоматам. Его эталонная реализация использует направленный граф (аналогично связанному списку, но каждый узел может иметь более одной ссылки «вне» и может ссылаться на любой другой узел, включая себя) по сравнению со связанным списком. Есть и другие способы моделирования конечного автомата, включая:
Вы создаете лексер / сканер, комбинируя несколько распознавателей. Например, представьте язык только для назначения со следующими токенами, определенными регулярными выражениями:
- идентификатор: [a-zA-Z] +
- назначение: =
- число: [0-9] +
- ключевое слово: и
Когда вы сканируете ввод слева направо, перемещайтесь по переходам в машине каждого токена на основе текущего символа. Если для символа нет действительных переходов, выберите последний компьютер в состоянии принятия. Все символы, отсканированные до этого состояния, являются частью токена. Сканирование начинается снова с символа после последнего принятого символа. Если для нового токена нет действительных переходов, ввод неверен, и лексер должен сообщить об ошибке. Если в принимающем состоянии находится более одного компьютера, правило приоритета должно решить, какой токен используется.
Примечание: эти шаги описывают лексер, который всегда возвращает максимально возможное совпадение. Вы также можете создать лексер, который возвращает токен, как только один из его компьютеров находится в состоянии принятия.
Результаты на входах образца:
- a = 10: (идентификатор a) (присвоение =) (номер 10)
- a = 10: неверно - пробелы в наших определениях токенов не принимаются
- 25 = xyz: (номер 25) (присвоение) (идентификатор xyz)
- 25and42: (число 25) (ключевое слово и) (число 42) - предполагается, что ключевое слово имеет приоритет над идентификатором
- b = 1 + 2: неверно - '+' не принимается в наших определениях токенов
- andx = 8: (идентификатор andx) (присваивание) (номер 8) - самое длинное совпадение дает нам (идентификатор andx) против (ключевое слово and) (идентификатор x)
Обратите внимание, что лексический анализ просто возвращает токены. Он не знает, правильно ли используются токены. «25 = xyz» может не иметь никакого смысла, но мы должны подождать до фазы анализа, чтобы знать наверняка.
В качестве дополнительного ресурса Дик Грун предлагает первое издание Методы синтаксического анализа - практическое руководство в виде Postscript и Pdf.