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

Самая важная разница в том, что при лексировании переводится ваш входной домен.

Хорошим результатом этого является то, что

• Вам больше не нужно думать о пробелах. В прямом (без лексирования) синтаксическом анализаторе вам нужно добавить 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".

• Многие вещи, которые, как можно было бы ожидать, будут атомарными единицами и будут разделены лексером, на самом деле "слишком сложно" определить для лексера. Возьмем, к примеру, строковые литералы - вдруг "hello world" больше не являются двумя токенами "hello и world" (но только, конечно, если кавычки не экранированы, как \") - хотя это очень естественно для парсера, это означает сложные правила и особые случаи для лексера.

• Вы не можете повторно использовать синтаксические анализаторы токенов. Если вы определяете, как разобрать двойник из String, экспортируйте его, и остальной мир сможет его использовать; они не могут сначала запустить ваш (специализированный) токенизатор.

• Вы застряли в этом. Когда вы разрабатываете язык для синтаксического анализа, использование лексера может привести вас к принятию ранних решений, исправляя то, что вы, возможно, захотите изменить впоследствии. Например, представьте, что вы определили язык, содержащий некоторый токен Float. В какой-то момент вы захотите ввести отрицательные литералы (-3.4 и - 3.4) - это может быть невозможно из-за того, что лексер интерпретирует пробелы как разделители токенов. Используя подход, основанный только на синтаксическом анализаторе, вы можете оставаться более гибкими, упростив внесение изменений в свой язык. В этом нет ничего удивительного, поскольку синтаксический анализатор - более сложный инструмент, который по своей сути кодирует правила.

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

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

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