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