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

《实验二 递归下降法语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二递归下降语法分析目的：理解自定向下语法分析的基本模式，熟悉递归下降分析程序的构造。内容：采用递归下降法对赋值语句、算术表达式运算、while循环语句、if分支语句及其分类体系进行分析。步骤：1、重构单词内码表在实验一的基础上，要求考虑while语句、if语句。以下为一参考实现： 保留字内部编码运算符号内部编码其他内部编码if1+51(81else2-52)82while3*53;83int4/54{84float5**55}85char6==56=86byte7<57,87  >58  <=59  >=60数字100   <>61标识符1102、定义

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

3、ε

4、→;→,

5、ε→int

6、float

7、char

8、byte→;

9、ε→

10、

11、→while"("")"{}→if"("")"{}else{}→=;→→<

12、>

13、==

14、<=

15、>=

16、!=→→

17、ε→→

18、ε→(E)

19、

20、

21、→+

22、-→*

23、/说明：①大写字母构成的单词（也用尖括号括起）表非终结符，小写单词表终结符。由于在词法分析阶段已经识别了数字和标识符，故逻辑上在此作为终结符对待；但另一方面又由于其概括性，又用尖括号括起。②本文法设计对高级语言子集也作了较大的简化，如不考虑过程定义及调用；不考虑输入输出；不考虑主程序；不考虑for循环；不考虑switchcase语句；不考虑字符串常量；变量定义只能在文件开头等等。3、编码（1）递归下降子程序的基本模式（请注意规则和下面的颜色对应关系）：①文法中的每个非终结符对应一个过程（函数）。②

24、若某个非终结符有多个产生式候选，或者某个分支路径有多个候选。则根据该候选的Select集是否包含输入符进行选择。每个候选对应一个if分支。③选择好候选之后，对产生式候选的右部的符号由左到右依次处理。（a）若为终结符。则判别是否与输入符号相等。若相等，继续。否则转③（b）若为非终结符，则调用该非终结符所对应的过程。（c）若当前扫描的符号为当前候选的第一个符号，且当前候选同层次有ε候选项.则不作出错处理。否则均出错处理。例1：Sà(S)

25、acharstr[];…//待检查的串intip;//扫描指针voidS(){//只有一个非终结符Sif(str[ip]==

26、’(‘){//处理Sà(S)候选ip++;S();if(str[ip]==’)’)ip++;elseerror();}elseif(str[ip]==’a’){//处理Sàa候选ip++;}else//对应第1符号error();//但无ε候选项，必须出错。}例2：Sà(S)

27、εcharstr[];…//待检查的串intip;//扫描指针voidS(){//只有一个非终结符Sif(str[ip]==’(‘){ip++;S();if(str[ip]==’)’)ip++;elseerror();//不与第1个符号，出错。}//最外层if不构造出错处理分支。}（

28、2）本实验中需要考虑的具体问题①上例比较的是字符。而本实验中用的是符号（单词）编码，是经过词法分析后的编码。依据字符串的排列和内码排列构成的两套系统是同构的。不影响语法分析的结果。希望大家能理解“同构”的含义。也就是后面定义的token数组相当于本例的str。这点变通能力希望大家有。②对于多个候选依据Select集来判定，具体实现时可定义一个函数：booleaninSelect(x,α),判别x∈SELECT(α)是否成立。数据结构可采用二维表格的方式，在inSelect内部查表。③虽然处理的是内码，但可用宏定义，则程序可读性好：/*终结符定义*/#def

29、ine$if1/*if*/#define$else2/*else*