实验二 递归下降法语法分析.doc

实验二 递归下降语法分析目的：理解自定向下语法分析的基本模式，熟悉递归下降分析程序的构造。内容：采用递归下降法对赋值语句、算术表达式运算、while循环语句、if分支语句及其分类体系进行分析。步骤：1、重构单词内码表在实验一的基础上，要求考虑while语句、if语句。以下为一参考实现： 保留字 内部编码 运算符号 内部编码 其他 内部编码 if 1 + 51 ( 81 else 2 - 52) 82 while 3 * 53 ; 83 int 4 / 54 84float 5 * 55 85 char 6 = 56 = 86 byte7 58 = 60 数字100 61 标识符1102、定义语言文法（1）定义所需的非终结符选取高级语言的部分语句，先定义其中所涉及的非终结符：符号定义符号定义符号定义程序定义语句集可执行语句集定义语句变量列表关系运算符可执行语句while语句If语句赋值语句过程调用语句类型声明关系表达式算术运算符1算术运算符2表达式文法引入的几个符号依然使用。 （2）用文法表达其语法规范。 | ; ,|int | float | char | byte;|while ( ) if ( ) else =;|=|=|!=|(E)|+|-*|/ 说明： 大写字母构成的单词（也用尖括号括起）表非终结符，小写单词表终结符。由于在词法分析阶段已经识别了数字和标识符，故逻辑上在此作为终结符对待；但另一方面又由于其概括性，又用尖括号括起。 本文法设计对高级语言子集也作了较大的简化，如不考虑过程定义及调用；不考虑输入输出；不考虑主程序；不考虑for循环；不考虑switch case语句；不考虑字符串常量；变量定义只能在文件开头等等。3、编码（1）递归下降子程序的基本模式（请注意规则和下面的颜色对应关系）： 文法中的每个非终结符对应一个过程（函数）。 若某个非终结符有多个产生式候选，或者某个分支路径有多个候选。则根据该候选的Select集是否包含输入符进行选择。每个候选对应一个if分支。 选择好候选之后，对产生式候选的右部的符号由左到右依次处理。（a）若为终结符。则判别是否与输入符号相等。若相等，继续。否则转（b）若为非终结符，则调用该非终结符所对应的过程。（c）若当前扫描的符号为当前候选的第一个符号，且当前候选同层次有候选项.则不作出错处理。否则均出错处理。例1：S(S)|achar str; /待检查的串int ip; /扫描指针void S() /只有一个非终结符S if(strip=() /处理S(S)候选ip+; S();if(strip=) ip+;else error(); else if(strip=a) /处理Sa候选 ip+; else /对应第1符号 error(); /但无候选项，必须出错。例2：S(S)|char str; /待检查的串int ip; /扫描指针void S() /只有一个非终结符S if(strip=() ip+; S();if(strip=) ip+;else error(); /不与第1个符号，出错。 /最外层if不构造出错处理分支。（2）本实验中需要考虑的具体问题 上例比较的是字符。而本实验中用的是符号（单词）编码，是经过词法分析后的编码。依据字符串的排列和内码排列构成的两套系统是同构的。不影响语法分析的结果。希望大家能理解“同构”的含义。也就是后面定义的token数组相当于本例的str。这点变通能力希望大家有。 对于多个候选依据Select集来判定，具体实现时可定义一个函数：boolean inSelect(x,),判别 xSELECT()是否成立。数据结构可采用二维表格的方式，在inSelect内部查表。 虽然处理的是内码，但可用宏定义，则程序可读性好：/* 终结符定义 */#define $if1/*if*/#define $else2/*else*/#define $while3/*while*/ 关于上面规则的具体运用，可看模板代码。实现了两个非终结符，其余的需要同学们自己去实现，注意利用词法分析程序的成果。4、测试构造正反测试用例，如：正确实例：whil