Грамматика S -> a S a | a генерирует все строки четной длины из a. Мы можем разработать синтаксический анализатор рекурсивного спуска с возвратом для этой грамматики. Если мы сначала выберем расширение путем производства S -> aa, то мы распознаем только строку aa. Таким образом, любой разумный синтаксический анализатор рекурсивного спуска сначала попробует S -> aSa.
Покажите, что этот синтаксический анализатор рекурсивного спуска распознает входные данные aa, aaaa и aaaaaaaaa, но не aaaaaa.
Синтаксический анализатор попытается сначала вызвать match(a);S();match(a);, а не match(a);match(a);, как описано в задаче. И обратите внимание, что когда вы пытаетесь рекурсивно вызвать S() внутри блока match(a);S();match(a);, вы вызвали match(a) только один раз, символ 'a' в конце не используется.
Я перефразирую себя из другого ответа.
На самом деле это свойство стратегии одноэлементного сопоставления, обычное в наивных реализациях парсеров рекурсивного спуска с возвратом.
Цитируя этот ответ доктора Адриана Джонстона:
Хитрость здесь заключается в том, чтобы понять, что многие парсеры с возвратом используют то, что мы называем стратегией одноэлементного сопоставления, в которой, как только функция синтаксического анализа для правила находит совпадение, она возвращается. В общем, функции синтаксического анализа должны возвращать набор предполагаемых совпадений. Просто попробуйте проработать его, и вы увидите, что синтаксический анализатор одноэлементных совпадений пропускает некоторые из возможных производных.
Кроме того, изображения, доступные в этом ответе, помогут вам визуализировать то, что происходит в приведенном вами примере.
