Использование типов опций вместо исключений для парсера рекурсивного спуска?

Question

Я пишу простой анализатор рекурсивного спуска в OCaml. Как правило (насколько я могу судить по учебным пособиям в Интернете и в книгах), исключения указывают на ошибки анализа, например:

match tok with
   TokPlus -> ...
 | _ -> raise SyntaxError

Однако я подумываю использовать вместо этого тип параметра, т. Е .:

match tok with
   TokPlus -> Some(...)
 | _ -> None

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

Есть ли недостатки в использовании опций вместо исключений? Будет ли это решение кусать меня за ногу, когда я начну разбирать более сложные структуры?

Answer 1

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

Смысл исключений в том, что вам не нужно добавлять обработчики исключений в каждую подпрограмму; Вы получаете неявное распространение.

Есть ли конкретная причина, по которой вы хотите оптимизировать хвостовую рекурсию? Большинство парсеров на самом деле не производят очень глубокие стеки вызовов (несколько сотен уровней для действительно сложных вещей). И я сомневаюсь, что экономия времени значительна по сравнению со всей другой работой, выполняемой непарсерской частью.

Answer 2

Я полагаю, что исключения оптимизируют общий случай - путь к коду для успешного разбора проще. Обычно при синтаксическом анализе это все или ничего - либо все анализируется нормально, и вы возвращаете конечный результат, либо что-то ломается - и вам все равно, где он ломается, потому что вы все равно не собираетесь его обрабатывать, кроме как напечатать осмысленное сообщение, но одно можете пропустить этот шаг тоже :) Так что выглядит как идеальный матч для исключений.

Answer 3

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

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