Почему грамматика может генерировать строку, но не может быть распознана тем же парсером рекурсивного спуска?

Question

Например, у нас есть грамматика S-> aSa | аа, ясно, что эта грамматика может генерировать все строки четной длины. Если мы разработаем синтаксический анализатор с рекурсивным спуском для этой грамматики, почему входы типа "aa", "aaaa", "aaaaaaaa" могут быть распознаны, а "aaaaaa" не может быть распознан?

Вот моя мысль:

Для "aa" попробуйте S-> aSa, "a" соответствует, однако "S" не соответствует, обратный ход. попробуй S-> aa， спички.

Для "aaaa" попробуйте S-> aSa, совпадения 'a', попробуйте S-> aSa, у нас есть aaSaa, S не совпадает, попробуйте S-> aa, у нас есть aaaa, совпадения.

Для "aaaaaa", попробуйте S-> aSa, совпадения 'a', попробуйте S-> aSa, у нас есть aaSaa, попробуйте S-> aSa, у нас есть aaaSaaa, не совпадает, попробуйте S-> aa, у нас есть "aaaaaa",

я не знаю, что с частью 'aaaaaa'.

почему аааааа нельзя узнать?

Answer 1

Потому что в простом парсере с рекурсивным спуском возврат не разрешен.

Парсеры рекурсивного спуска читают токены слева направо, читая каждый токен один раз.

Конечно, вы можете узнать это с помощью рекурсивного анализатора спуска; но тогда у парсера уже нет линейного времени.