#java #pattern-matching #bnf
Вопрос:
Я использую https://github.com/sylvainhalle/Bullwinkle/, анализатор BNF. Но он может распознать шаблон BNF только для одного целого предложения, как найти совпадения BNF в абзаце? Я пытаюсь распознать определенные команды в человеческой речи. Для примера BNF:
<S>: <lightcmd>;
<lightcmd>: <do> <obj> | <do> <a> <obj>;
<do>: turn on | turn off;
<a>: a | an | the;
<obj>: light;
Я могу разобрать правильную команду, произнося «включите свет», но я не могу разобрать ее по «пожалуйста, включите свет».
Комментарии:
1. Вам нужно более четко объяснить, что вы делаете. Но я думаю, что вы используете неправильный инструмент для задачи, которую пытаетесь выполнить. Синтаксический анализ и сопоставление шаблонов-это разные проблемы.
2. Хорошо, я думаю, что мне следует попробовать инструмент регулярных выражений, чтобы сделать это. Но является ли регулярное выражение подмножеством BNF?
3. С определенной точки зрения, да … но это не делает синтаксические анализаторы подходящим инструментом для сопоставления шаблонов. Возможно, если бы вы объяснили, что вы на самом деле пытаетесь сделать, мы могли бы дать вам несколько советов.
4. Пожалуйста, посмотрите мою правку.
Ответ №1:
Когда вы пытаетесь разобрать «пожалуйста, включите свет» против этой грамматики, анализатор попытается разобрать все высказывание … потому что это то, что делают парсеры. Но то, что вы хотите, — это соответствовать части высказывания.
Теперь вы могли бы справиться с этим примерно следующим образом:
<S>: <words> <lightcmd> <words>;
<lightcmd>: <do> <obj> | <do> <a> <obj>;
<do>: turn on | turn off;
<a>: a | an | the;
<obj>: light;
<words>: <word> | <words> <word>
<word>: // one or more letters
но вы начинаете сталкиваться с проблемами двусмысленности.
Я думаю, что лучшей идеей было бы попытаться проанализировать подпоследовательности потока слов. Поэтому, если пользователь говорит
please turn on a light and make a cup of tea
вы пытаетесь проанализировать, начиная с «пожалуйста». Затем, когда это не удается, вы пытаетесь начать с «поворота». Затем, когда вы достигнете «света», вы игнорируете остальные слова.
Я не знаю, можно ли так использовать Буллвинкл. Если нет, поищите альтернативные генераторы синтаксических анализаторов.
Однако следует также отметить, что такая простая грамматика также может быть написана как регулярное выражение, в котором слова рассматриваются как базовые символы. Для этого вам понадобится только простой механизм регулярных выражений. (Если эта грамматика типична, вам нужна только группировка и чередование. Это должно занять всего пару часов работы, чтобы реализовать это с нуля.)
Комментарии:
1. Спасибо за ваше объяснение. Хотя я понятия не имею, как написать произвольный сопоставитель <word> из-за плохой документации Bullwinkle, и на самом деле я имею дело с потоком китайских слов (что-то вроде произвольного сопоставления Юникода?). Как вы сказали, я мог бы попытаться проанализировать подпоследовательности, например [начало-конец] в {[0,0], … , [0,н], [1,1], … , [1,n], …, [n,n]}, это O(n^2) * O(синтаксический анализ), интересно, не слишком ли это сложно, чем сопоставление шаблонов?
2. Ну, это зависит от контекста. Но, например, это O(1) , чтобы найти первый экземпляр «поворота» в последовательности слов.
3. Хорошо, получив список шаблонов с первым словом (не уверен, что Bullwinkle предоставляет эту функцию), отфильтруйте вхождения первых слов (O(1)?), Сложность затем можно уменьшить до O(1) * O(n) * O(синтаксический анализ).