这不是学校相关的问题，但在“编译原理（Compilers: Principles, Techniques, and Tools）”中的一个练习中提到：
文法如下：
S ::= aSa | aa
生成所有偶数个a的字符串，除了空字符串。
a）构造一个具有回溯功能的递归下降解析器来处理该文法，尝试使用替代的aSa而不是aa。表明对于2、4或8个a的情况，S的程序成功了，但在6个a的情况下失败了。 b）你的解析器识别哪种语言？
我被难住了。如果4个a被认为是S，并且在S之间有两个a被认出，则应该认出6个a。我尝试在C中实现解析器，但它也将所有偶数个a识别出来，包括6个a。这个练习想要表达什么意思？
/* A C implementation of Exercise 4.13 in the Dragon Book */
/* The grammar:
S ::= aSa | aa
*/
/* Construct a recursive-descent parser with backtracking for this grammar
that tries the alternative aSa before aa. Show that the procedure for S
succeeds on 2, 4, or 8 a's, but fails on 6 a's.
*/
#include <string.h>
#include <stdio.h>
int S(const char *str, int start, int end);
int aSa(const char *str, int start, int end);
int aa(const char *str, int start, int end);
/* returns 1 if a match, 0 otherwise */
int S(const char *str, int start, int end)
{
if(aSa(str, start, end))
return 1;
else
if(aa(str, start, end))
return 1;
return 0;
}
/* returns 1 if a match, 0 otherwise */
int aSa(const char *str, int start, int end)
{
int len = end - start;
if (len < 3)
return 0;
if(str[0] != 'a')
return 0;
if (!S(str, start+1, end-1))
return 0;
if(str[len-1] != 'a')
return 0;
return 1;
}
/* returns 1 if a match, 0 otherwise */
int aa(const char *str, int start, int end)
{
int len = end - start;
if(len != 2)
return 0;
if(str[0] == str[1] && str[0] == 'a')
return 1;
return 0;
}
int main()
{
char str[20];
printf("Enter a string: \n");
scanf("%s", str);
int match = S(str, 0, strlen(str));
if(match)
printf("The string %s matches\n", str);
else
printf("The string %s does not match\n", str);
return 0;
}
end-1传递给S对于“递归下降解析器”来说是作弊。 - aschepleraSa中，你检查的是(str[0] != 'a')，但是应该是(str[start] != 'a')，对吗？ - hkBst