Scala Parser Combinator, неоднозначная грамматика и синтаксический анализ
Я пытаюсь заставить синтаксический анализатор возвращать все возможные результаты синтаксического анализа (лес синтаксического анализа) из неоднозначной грамматики и выбирать из леса синтаксического анализа, сравнивая их с пользовательским контекстом / историей и базой знаний. По соображениям производительности это, вероятно, следует сделать с помощью синтаксического анализатора пакета и параметра предела поиска / верхней границы, чтобы ограничить число рекурсивных вызовов при применении правил производства, чтобы избежать бесконечных циклов.
Будучи новичком как в Scala, так и в его Parser Combinators, я не могу понять, как это сделать или вообще можно ли это сделать. Может ли кто-нибудь помочь, пожалуйста? Очень признателен.
С наилучшими пожеланиями, Томас Хуан
1 ответ
Вы не можете сделать это с помощью встроенных в Scala комбинаторов синтаксического анализа. Комбинаторы Packrat ограничены только однозначными грамматиками. Если вы пытаетесь справиться с неоднозначностью, вы теряете способность запоминать, и сложность разбора становится равной O(k^n) даже для однозначных следов. Так что не делай этого.
То, что вам нужно, - это структура синтаксического анализатора, которая правильно обрабатывает неоднозначность. Насколько я знаю, единственной такой платформой для Scala являются мои GLL-комбинаторы. Синтаксис почти идентичен синтаксическим комбинаторам Scala (главное отличие состоит в том, что функции с более высокой арностью работают правильно), но вывод Stream[A], где A тип результата. Таким образом, вы получаете разбор леса. Обратите внимание, что на самом деле результат не является SPPF (совместно используемым упакованным лесом анализа), поэтому, если вы получите экспоненциальное число результатов, поток будет иметь пропорциональный размер. Это было сделано для обеспечения максимальной гибкости в типе результата.
GLL комбинаторы - это O(n^3) в худшем случае, даже для патологически неоднозначных грамматик. В среднем случае, когда трасса разбора однозначна, комбинаторы GLL имеют значение O(n). Постоянные накладные расходы в настоящее время немного чрезмерны, но оптимизация - это постоянный проект. Мы используем комбинаторы GLL в производстве в Precog, поэтому вы можете ожидать, что библиотека будет хорошо поддерживаться в будущем.