Можно ли превратить парсер Earley в нечеткий парсер, похожий на алгоритм Levenshtein Automata Algo для DFA?

10

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

EnjoysMath
источник
1
Ну, КПК закрыты от многих операций с NFA, так что это должно быть возможно в принципе. Адаптация Earley, кажется, является упражнением с зазором, поскольку нам разрешено использовать счетчики в предметах. Я что-то пропустил?
Рафаэль
@ Рафаэль Да, это общая идея. Мой ответ длиннее, так как сложно оценить, что пользователи знают или не знают.
Бабу
Пожалуйста, приведите ссылку / эскиз определения для "Levenshtein Automata". знаете, кто может быть квалифицирован, но на кого вы ссылаетесь?
vzn

Ответы:

8

Ответ - да. Однако я бы не стал делать это с парсером Earley, потому что есть более простые с такими же возможностями.

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

Есть два способа (по крайней мере) понимания этих парсеров:

  • как динамическое программирование интерпретации раскрывающегося автомата, соответствующего грамматике на входной строке;

  • как конструкция пересечения грамматики с автоматом конечных состояний.

При синтаксическом анализе одной строки рассматриваемый конечный автомат является линейным автоматом, который распознает только строку должна быть проанализирована, по одному символу за раз (число состояний | w | + 1 ). Если вы примените перекрестную конструкцию FA A и CF garmmar G (Bar Hillel, Perlis, Shamir 1961), вы получите новую CF грамматику, которая является новой грамматикой Fвес|вес|+1AгF которая генерирует , Интересный момент, который обычно упускают из виду, заключается в том, что F сохраняет деревья разбора, используемые GL(A)L(г)Fг, вплоть до переименования нетерминалов (из-за перекрестного продукта).

Таким образом, если FA генерирует только вашу входную строку, грамматикаA будет генерировать только эту строку (если она находится в L ( G ) , в противном случае она генерирует пустой язык ). Кроме того, он генерирует его со всеми деревьями разбора, которые G может использовать для его генерации.FL(г)г

Эта грамматика - это то, что обычно называют разделяемым лесом синтаксического анализа , и все общие алгоритмы синтаксического анализа CF представляют собой более или менее оптимизированную версию построения кросс-продукта, будь то CYK, Earley, обобщенный LR или LL, или другие. Так что все, что я говорю, относится и к ним.F

Но, как вы видите, это обобщает анализ всего регулярного набора, если кто-то заинтересован в этом.

весвес

гF

При желании это можно использовать для сохранения только струн с минимальным расстоянием.

Однако это можно немного улучшить, поскольку композиция с конечными автоматами ассоциативна.

Если вы всегда используете один и тот же конечный датчик состояния, как в вашем вопросе, правильный путь - это составить грамматику гвесΣ*

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

Babou
источник
думаю, что это полезно, но, возможно, «слишком много читается» в вопросе, поэтому сказать что-то вроде «это именно ваш вопрос» не может быть действительно точным. Вы взяли довольно расплывчатый вопрос, не строго формализованный, и (пытались?) формализовать его самостоятельно. возможно, существует более одного способа формализовать первоначальную несколько расплывчатую идею. думаю, что было бы полезно сначала тщательно определить, что делают конструкции DFA Левенштейна (есть некоторые известные / исследованные, но о каких мы говорим?), а затем объяснить, как эта концепция может быть обобщена для КЛЛ.
vzn
1
Я фактически даю разные формализации, которые дополняют друг друга. Есть тонкости, в которые я не попал, например, точное использование весов в процессе, которое зависит от того, какой именно результат вы хотите получить. Моя цель не просто дать ответ, который мало интересует мое собственное мнение, но дать более широкое понимание проблемы. Выбор используемого расстояния редактирования не имеет значения, он работает для всего, что может быть выражено с помощью весового датчика конечного состояния.
Бабу