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

实验二 递归下降语法分析

目的： 理解自定向下语法分析的基本模式，熟悉递归下降分析程序的构造。 内容： 采用递归下降法对赋值语句、算术表达式运算、while循环语句、if分支语句及其分类体系进行分析。 步骤：

1、重构单词内码表 在实验一的基础上，要求考虑while语句、if语句。以下为一参考实现： 保留字 内部编码 运算符号 内部编码 其他 if else while int float char byte 1 2 3 4 5 6 7 + - * / ** == < > <= >= <> 51 52 53 54 55 56 57 58 59 60 61 ( ) ; { } = , 数字 标识符 内部编码 81 82 83 84 85 86 87 100 110

2、定义语言文法

（1）定义所需的非终结符 选取高级语言的部分语句，先定义其中所涉及的非终结符： 符号 定义 程序 定义语句 可执行语句 赋值语句 关系表达式 符号 定义 定义语句集 变量列表 while语句 过程调用语句 算术运算符1 符号 定义 可执行语句集 关系运算符 If语句 类型声明 算术运算符2 表达式文法引入的几个符号依然使用。

（2）用文法表达其语法规范。 → →|ε → ; →,|ε →int | float | char | byte →;|ε →|| →while \

→if \ →=; → →<|>|==|<=|>=|!= → →|ε → →|ε →(E)|| →+|- →*|/ 说明： ① 大写字母构成的单词（也用尖括号括起）表非终结符，小写单词表终结符。由于

在词法分析阶段已经识别了数字和标识符，故逻辑上在此作为终结符对待；但另一方面又由于其概括性，又用尖括号括起。 ② 本文法设计对高级语言子集也作了较大的简化，如不考虑过程定义及调用；不考

虑输入输出；不考虑主程序；不考虑for循环；不考虑switch case语句；不考虑字符串常量；变量定义只能在文件开头等等。 3、编码

（1）递归下降子程序的基本模式（请注意规则和下面的颜色对应关系）： ① 文法中的每个非终结符对应一个过程（函数）。 ② 若某个非终结符有多个产生式候选，或者某个分支路径有多个候选。则根据该候选的Select集是否包含输入符进行选择。每个候选对应一个if分支。 ③ 选择好候选之后，对产生式候选的右部的符号由左到右依次处理。

（a）若为终结符。则判别是否与输入符号相等。 若相等，继续。否则转③

（b）若为非终结符，则调用该非终结符所对应的过程。 （c）若当前扫描的符号为当前候选的第一个符号，且当前候选同层次有ε候选项.则不作出错处理。否则均出错处理。

例1：S?(S)|a char str[];… //待检查的串 int ip; //扫描指针 void S() { //只有一个非终结符S if(str[ip]==’(‘) { //处理S?(S)候选 ip++; S(); if(str[ip]==’)’) ip++; else error(); } else if(str[ip]==’a’) { //处理S?a候选 ip++; } else //对应第1符号 error(); //但无ε候选项，必须出错。 } （2）本实验中需要考虑的具体问题 例2：S?(S)|ε char str[];… //待检查的串 int ip; //扫描指针 void S() { //只有一个非终结符S if(str[ip]==’(‘) { ip++; S(); if(str[ip]==’)’) ip++; else error(); //不与第1个符号，出错。 } //最外层if不构造出错处理分支。 } ① 上例比较的是字符。而本实验中用的是符号（单词）编码，是经过词法分析后的编码。依据字符串的排列和内码排列构成的两套系统是同构的。不影响语法分析的结果。希望大家能理解“同构”的含义。也就是后面定义的token数组相当于本例的str。这点变通能力希望大家有。

② 对于多个候选依据Select集来判定，具体实现时可定义一个函数： boolean inSelect(x,α),判别 x∈SELECT(α)是否成立。 数据结构可采用二维表格的方式，在inSelect内部查表。 ③ 虽然处理的是内码，但可用宏定义，则程序可读性好： /* 终结符定义 */ #define $if 1 /* if */ #define $else 2 /* else */ #define $while 3 /* while */ ……

④ 关于上面规则的具体运用，可看模板代码。实现了两个非终结符，其余的需要同学们自己去实现，注意利用词法分析程序的成果。

4、测试 构造正反测试用例，如：正确实例：while(ip<>0) {} 错误实例：while(ip<>=){} 本程序内部分支多，且实验时间有限。要达到较为全面测试覆盖比较难，因此只要求赋值语句、算术表达式、while、if四种语句均有正反测试用例。

本文来源：https://www.bwwdw.com/article/ykja.html