Могут ли альтернативные правила накладываться на их начальные токены в PEG? - PullRequest
Новая
       43

Могут ли альтернативные правила накладываться на их начальные токены в PEG?

0 голосов
/ 27 сентября 2019

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

Я пытаюсь создать парсер, который будет обрабатывать несколько вариантов синтаксиса.Но я предполагаю, что есть двусмысленность, потому что в простейшем случае каждый вариант допускает один и тот же ввод.Поскольку я сопоставлял их с одним и тем же синтаксическим деревом, я надеялся, что это не будет иметь значения.Конечно, это так.

Я использую Peg.js и пытаюсь построить грамматику, которая для простоты будет принимать входные данные, такие как abc/cd/e, x/yz или простоfoo, но также принимает abc.cd.e, x.yz и, конечно, еще foo.Я предполагаю, что проблема в том, что оба моих варианта принимают foo.

Вот что я пытался сделать: 

Expression = SlashTerm / DotTerm 
SlashTerm = Name ('/' SlashTerm)?
DotTerm = Name ('.' DotTerm)?
Name = [a-z0-9_\-]i+

И это распознает foo/bar, но не foo.bar.Если я переключаюсь на Expression = DotTerm / SlashTerm, конечно, он распознает foo.bar, а не foo/bar.

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

Expression = DotTerm / SlashTerm 
SlashTerm = Name ('/' SlashTerm)?
DotTerm = Name '.' DotNode
DotNode = Name ('.' DotNode)?
Name = [a-z0-9_\-]i+

Хотя добавление дополнительного правила не вызывает проблем, мне не нравится, что для этого необходимо переключиться с Expression = SlashTerm / DotTerm на Expression = DotTerm / SlashTerm.Я думал, что любой должен работать, так как нет никакой двусмысленности.Возможно, я неправильно понимаю операцию выбора, но у меня сложилось впечатление, что при использовании Expression = SlashTerm / DotTerm, когда он попытался проанализировать foo.bar, он прошел бы через foo, нажал на ., не нашел совпадения и вернулся к вершине.SlashTerm, который не соответствует, так что он переместится в DotTerm, где найдет совпадение.Так как это не работает, мое понимание неверно, и я надеюсь, что кто-то может объяснить, почему.

Я также хотел бы услышать о лучших способах сделать это.

Моя настоящая грамматика, конечно, намного сложнее;SlashTerm гораздо сложнее.Но эквивалент DotTerm действительно так прост.Эквивалентный синтаксис DotTerm (с которым я, очевидно, легко справлюсь без полноценного синтаксического анализатора) сейчас является единственным поддерживаемым синтаксисом, но я пытаюсь расширить его до гораздо более надежного языка.Я хотел бы не разветвлять код, основываясь на выборе синтаксиса, и хочу, чтобы его можно было легко исключить позже.Включение нескольких правил в мою грамматику кажется самым простым способом сделать это.Но если есть другой простой способ сделать это, я хотел бы услышать это.

1 Ответ

1 голос
/ 27 сентября 2019

Но SlashTerm соответствует .Он не соответствует всему вводу, но он успешно соответствует части ввода.Следовательно, SlashTerm / DotTerm также успешно совпадает.И PEG не возвращает назад к успешно подобранному компоненту.Чтобы PEG смог вернуться назад, сопоставляемый компонент должен завершиться неудачей.

Таким образом, одно из решений состоит в том, чтобы настаивать на том, чтобы альтернативы соответствовали первому разделителю, если его нет: 

Expression = SlashTerm / DotTerm / Name 
SlashTerm = Name ('/' Name)+
DotTerm = Name ('.' Name)+
Name = [a-z0-9_\-]i+

.case, ни SlashTerm, ни DotTerm не будут соответствовать одному слову, поэтому оператор выбора должен перейти к третьему варианту.Точно так же foo.bar не может соответствовать SlashTerm, поэтому он потерпит неудачу, и оператор выбора вернется ко второй альтернативе, как и ожидалось.

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

Expression = SlashTerm / DotTerm / Name
SlashTerm = Name '/' SlashRest
DotTerm = Name '.' DotRest
SlashRest = Name ('/' SlashRest)?
DotRest = Name ('.' DotRest)?
Name = [a-z0-9_\-]i+
...