Должен ли я использовать лексер при использовании библиотеки комбинаторов парсеров, таких как Parsec?

При написании парсера в библиотеке комбинаторов парсеров, таких как Haskell Parsec, у вас обычно есть 2 варианта:

Напишите лексер, чтобы разбить ваш вход String на токены, затем выполните синтаксический анализ на [Token]
Непосредственно писать комбинаторы парсеров на String

Первый метод часто имеет смысл, учитывая, что многие входы анализа могут пониматься как токены, разделенные пробелами.

В других местах я видел, как люди рекомендуют против токенизации (или сканирования или лексинга, как их называют), причем простота цитируется в качестве основной причины.

Каковы общие компромиссы между лексикой и не делать этого?

Ответ 1

Самое важное отличие состоит в том, что lexing будет транслировать ваш входной домен.

A nice результат этого заключается в том, что

Вам больше не нужно думать о пробелах. В прямом (не лексическом) синтаксическом анализаторе вы должны посыпать парсеры space во всех местах, где разрешено свободное пространство, что легко забыть, и он загромождает ваш код, если в любом случае пробелы должны отделять все ваши токены.
Вы можете думать о своем вводе по частям, что легко для людей.

Однако, если вы выполняете лексирование, вы получаете проблемы, которые

Вы больше не можете использовать общие парсеры на String - например. для разбора числа с помощью библиотеки Функция parseFloat :: Parsec String s Float (работающая на потоке ввода String), вы должны сделать что-то вроде takeNextToken :: TokenParser String и execute анализатора parseFloat на нем, проверяя результат анализа (обычно Either ErrorMessage a). Это беспорядочно писать и ограничивать возможности.
Вы настроили все сообщения об ошибках. Если ваш синтаксический анализатор на токенах терпит неудачу на 20-м токене, где во входной строке это? Вам придется вручную отображать местоположения ошибок обратно во входную строку, что является утомительным (в Parsec это означает, что все значения SourcePos) корректируются.
Отчеты об ошибках, как правило, хуже. Запуск string "hello" *> space *> float на неправильном входе, таком как "hello4", точно скажет вам, что ожидаемое пропущенное пробел отсутствует после hello, в то время как лексер просто заявит, что нашел "invalid token".
Многие вещи, которые можно было бы ожидать от атомных единиц и быть разделены лексером, на самом деле довольно "слишком сложны" для определения lexer. Возьмем, к примеру, строковые литералы - вдруг "hello world" уже не два токена "hello и world" (но только, конечно, если кавычки не экранированы, например \")), в то время как это очень естественно для синтаксического анализатора, это означает сложные правила и специальные случаи для лексера.
Вы не можете повторно использовать парсеры на токенах так же хорошо. Если вы определяете, как разбирать двойной из String, экспортировать его и остальную часть мира можно использовать; они не могут запускать ваш (специализированный) токенизатор в первую очередь.
Вы застряли с ним. Когда вы разрабатываете язык для синтаксического анализа, использование lexer может привести вас к принятию ранних решений, исправлению того, что вы, возможно, захотите изменить впоследствии. Например, представьте, что вы определили язык, содержащий некоторый токен Float. В какой-то момент вы хотите ввести отрицательные литералы (-3.4 и - 3.4) - это может быть невозможно из-за интерпретации лексера в качестве разделителя токенов. Используя подход, основанный только на парсере, вы можете оставаться более гибким, делая изменения на вашем языке проще. Это не удивительно, так как парсер является более сложным инструментом, который по своей сути кодирует правила.

Подводя итог, я бы рекомендовал писать парсер без лексинга для большинства случаев.

В конце концов, лексер - это просто "паршивый" * парсер, если вам нужен синтаксический анализатор, в любом случае, объедините их в один.

_{* Из теории вычислений мы знаем, что все регулярные языки также являются контекстно-свободными языками; lexers обычно являются регулярными, парсерами контекстно-зависимыми или даже контекстно-зависимыми (монадические парсеры, такие как Parsec, могут выражать контекст-чувствительность).}