Может кто-то просветить меня, почему парсер рекурсивного спуска с возвратом, который пробует продукцию и (в этом порядке), не распознает язык, образованный грамматикой .
Похоже, он разбирает только слова из языка .
Я сгенерировал такой синтаксический анализатор, используя этот ABNF Parser Generator с рабочим правилом, S = "a" S "a" / "aa"
и синтаксический анализатор, например, не распознает слово aaaaaa
.
Я ожидаю, что он будет использовать производство до тех пор, пока конкатенация конечных узлов дерева разбора слева не начнется с 7 a
, а затем поднимется вверх по дереву разбора, выбрав вместо этого производственную пока дерево не будет выглядеть как это:
S
/ | \
a S a
/ | \
a S a
/ \
a a
context-free
formal-grammars
compilers
parsers
meribold
источник
источник
aaaaaa
.aaaaaa
должна анализировать и не делает. Ноaaaa
разбирает ли. Вы, очевидно, правы относительно способностей 2. Это должно быть ошибочно. разбирает толькоaa
сS = "aa" / "a" [S] "a"
. Можете ли вы отследить, что делает парсер?Ответы:
Это не очень хороший ответ, но деревья разбора не соответствуют обычным комментариям.
Ваша грамматика должен проанализировать строку a a a a a a .S→ Sа | aaaaaa
Но дерево разбора имеет следующую форму:
или, если вы предпочитаете эту презентацию, с терминалами на разных линиях
Я проверил, что генератор синтаксического анализатора ABNF, кажется, не работает, но я не знаю, как отследить, что он делает.
Похоже, это действительно распознает множество что не соответствует грамматике.{a2n | n≥1}
Немного удивительно иметь такой сложный сайт вокруг разбитого парсера, который, кроме того, использует совершенно неинтересную технику разбора.
После дальнейшего взгляда на это:
Я думаю, что нашел один источник проблемы. Квадратные скобки означают необязательно .
Так что ваша грамматика должна быть написана либо
S = "a" S "a" / "aa"
илиS = "a" [S] "a"
. Тогда, кажется, работает правильно.Но система, по-видимому, теряется, если иметь два одинаковых правила в разных формах. Я не уверен почему.
Я не нашел страницу, объясняющую эти синтаксические проблемы для определения грамматики.
Я все еще считаю, что глючит.
источник
S ::= 'a'<S>'a' | 'a''a'
aaaaaa
при использованииS = "a" S "a" / "aa"
, но вы, кажется, правы в скобках.S = "a" S "a" / "aa"
... я проверил слишком быстро, и нажал на генерацию вместо разбора.s1()
true
s()
s2()
Подумайте о
aaaaaa
повторном разборе слова . В какой-то момент дерево разбора будет выглядеть так:s()
true
S
Я склонен считать это проблемой с моей реализацией, а не с рекурсивными анализаторами обратного спуска вообще.
источник
Это особенность, а не ошибка
Внимательно посмотрите, когда и где происходит возврат:
Важным моментом здесь является то, что парсер возвращается после позиции, где был найден последний соответствующий символ. Вот почему он «прыгает» с дерева 11 с l = aaaaaaaa на 12-е дерево с l = aaaa , используя S -> aa на l [7].
источник