编 译 原 理 实 验 报 告 姓名：关海超 学号：200807010209 专业：计算机科学与技术 班级：08—02 班 

递归下降分析法的实现 实验要求 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是 LL(1)文法。它的基 本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数（或子程序）的 功能是识别由该非终结符所表示的语法成分。由于描述语言的文法通常是递归定义的，因此 相应的这组函数（或子程序）必然一相互递归的方式进行调用，所以将此种分析方法称为递 归下降分析法。 本实验要求构造下述文法的递归下降分析程序： 文法 G[S]: S —> a | ^ | (T) T —> T,S | S 实验内容 首先，消去该文法左递归，得到文法 G’[S]: S —> a | ^ | (T) T —> ST’ T’ —> ,ST’ | 空串 然后，根据 LL(1)文法的判断条件，对非终结符 S 和 T’的不同产生式的 SSELECT 集进 行考察，经验证改进后的文法已经是 LL(1)文法。 最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部 符号串的结构编写。 （1）当遇到终结符 a 时，则编写语句 if (当前读来的输入符号 == a) 读下一个输入符号 （2）当遇到非终结符 A 时，则编写语句调用 A（）。 （3）当遇到 A —> 空串 规则时，则编写语句 if (当前读来的输入字符 不属于 FOLLOW(A) ) error() （4）当某个非终结符的规则有很多个候选式是，按 LL(1)文法的条件能唯一地选择一 个候选式进行推导。 实验结果 

实验总结 这次实验内容比较简单。由于有固定的模式来构造程序，因此即使对于其他 LL(1)文法 也很容易构造其相应的递归下降分析程序。 这次实验我学习了如何将递归下降分析思想具体转化为程序来实现，同时也加深了产生 式的 Follow 集在递归下降分析法中的应用，练习了通过 SELECT 集判断文法是否为 LL(1) 文法。 附录（源代码） #include #include #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scaner(); void Error(); 

T(); if (sym == ')') Scaner(); else Error(); } else printf("Please input : \n"); gets(token); p = 0; Scaner(); S(); if (sym == '#') printf("Success!\n"); else printf("Fail!\n"); return 0; } void S() { if (sym == 'a' || sym == '^') Scaner(); else if (sym == '(') { Scaner(); Error(); } void T() { S(); U(); } void U() { if (sym == ',') { Scaner(); S(); U(); } else if (sym != ')') Error(); } void Scaner() { sym = token[p++]; } void Error() { printf("Error!\n"); exit(0); } int main() {