#parsing #exception #ocaml #options #recursive-descent
#синтаксический анализ #исключение #ocaml #рекурсивный спуск
Вопрос:
Я пишу простой анализатор рекурсивного спуска на OCaml. Обычно (насколько я могу судить из онлайн-руководств и книг) исключения используются для указания сбоев синтаксического анализа, например:
match tok with
TokPlus -> ...
| _ -> raise SyntaxError
Однако я подумываю об использовании вместо этого типа опции, т.Е.:
match tok with
TokPlus -> Some(...)
| _ -> None
Основная причина, по которой я хочу это сделать, заключается в том, что использование типов опций позволяет мне оптимизировать некоторые из моих комбинаторов для хвостовой рекурсии.
Есть ли какие-либо недостатки при использовании опций вместо исключений? Будет ли это решение укусить меня в ногу, когда я начну разбирать более сложные структуры?
Комментарии:
1. В конце концов, я вернулся к использованию исключений и использовал опции для оптимизации нескольких случаев, когда были бы глубоко вложенные рекурсии (в основном повторяющиеся комбинаторы). Оказалось, что было несколько мест, где мне пришлось бы вручную сопоставлять параметры и распространять ошибки; в конце концов, исключения имели гораздо больше смысла. Так что, если кто-то еще думает об этом, просто продолжайте использовать исключения!
Ответ №1:
Нет, но вам, вероятно, придется добавить (много) фиктивных правил, чтобы распространить ошибку обратно на корневую версию грамматики.
Суть исключений в том, что вам не нужно добавлять обработчики исключений в каждую процедуру; вы получаете неявное распространение.
Есть ли конкретная причина, по которой вы хотите оптимизировать хвостовую рекурсию? Большинство анализаторов на самом деле не создают очень глубокие стеки вызовов (несколько сотен уровней для действительно сложных вещей). И я сомневаюсь, что экономия времени значительна по сравнению со всей другой работой, выполняемой частью, не являющейся синтаксическим анализатором.
Комментарии:
1. Хм… Я беспокоился о том, что стек вызовов становится слишком глубоким, хотя, наверное, я действительно не уверен, насколько вложенными будут вызовы; основным комбинатором, который я пытался оптимизировать, был repeat , который повторяется один раз для каждого повторяющегося элемента. Я знаю, что при использовании опций необходимо выполнить больше работы, но пока мне удалось скрыть большую часть сложности в комбинаторах, поэтому мои правила верхнего уровня по-прежнему выглядят довольно чистыми.
2. Мой худший в истории синтаксический анализ стека вызовов произошел при анализе списка данных инициализатора массива C. Инициализируемый массив C представлял собой ПЗУ. Список инициализаторов содержал байты в шестнадцатеричном формате для заполнения ПЗУ; было около миллиона записей, поэтому стек должен был иметь глубину в миллион записей. Анализируется нормально на современном x86.
3. Маловероятно, что ваш компилятор C использовал анализатор рекурсивного спуска. Вероятно, на самом деле использовался анализатор yacc (LALR, управляемый таблицами). Кроме того, инициализатор массива C не создается из глубоко вложенных компонентов. Просто некоторые наблюдения.
Ответ №2:
Я считаю, что исключения оптимизируют общий случай — путь кода для успешного анализа проще. Обычно при синтаксическом анализе это все или ничего — либо все анализируется нормально, и вы возвращаете конечный результат, либо что-то ломается — и вам все равно, где это ломается, потому что вы все равно не собираетесь это обрабатывать, кроме как печатать значимое сообщение, но этот шаг тоже можно пропустить 🙂 Так выглядит идеальное соответствие для исключений.
Комментарии:
1. Согласен; Я долго мучился из-за того, что не использовал исключения, потому что это действительно естественный способ написания такого кода. Интересно, совершаю ли я грех преждевременной оптимизации.
Ответ №3:
Самое замечательное в синтаксическом анализе рекурсивного спуска заключается в том, что вы можете писать код любым удобным для вас способом (в разумных пределах). Я не вижу проблемы с рекурсивным написанием хвоста с исключениями или без исключений, если только вы не предполагаете, что перехватываете исключения во всех ваших промежуточных функциях. Скорее всего, у вас будет один (или несколько) обработчиков исключений в верхней части вашей грамматики, и в этом случае весь приведенный ниже код может быть легко рекурсивным.
Итак, я согласен с игреком в том, что стиль исключения вполне естественен для синтаксического анализа, и я не думаю, что использование исключений обязательно исключает хвостовой рекурсивный стиль.
Комментарии:
1. В определенных случаях вам нужно перехватить исключение внутри функции, и в результате код не является хвостовым рекурсивным, потому что рекурсивный вызов находится в контексте try / catch . В частности, моему повторному комбинатору необходимо перехватить сбой синтаксического анализа (чтобы знать, что он достиг конца повторяющихся элементов). Хотя есть обходной путь, чтобы сделать его хвостовым рекурсивным, это не очень элегантно.
2. Ну, это звучит так, как будто вы используете исключения для управления правильным синтаксическим анализом. Если ваш язык является разумным, вы должны иметь возможность управлять синтаксическим анализом с помощью предпросмотра токенов и резервировать исключения для случаев ошибок. Вы можете попробовать параметризовать свой комбинатор повторений с помощью набора «следовать». Это то, что вы бы делали (по сути), если бы писали без обобщенных комбинаторов. Я думаю, что это все еще довольно элегантно (личное мнение).