实验三递归下降分析法.doc

实验二：自上而下语法分析 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。 根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。 本次实验的目的主要是加深对自上而下分析法的理解。 二、实验预习提示 自下而上分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法 A．递归下降 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照， 若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U-u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1-x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。 （4）对于右部中的每个符号xi  = 1 \* GB3 ①如果xi为终结符号： if(xi= = 当前的符号) { NextChar()； return; } else 出错处理  = 2 \* GB3 ②如果xi为非终结符号，直接调用相应的过程xi() 说明： NextChar为前进一个字符函数。 B．LL（1）分析法 1、LL（1）分析法的功能 LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。 X∈VN ‘#’‘S’进栈，当前输入符送a 上托栈顶符号放入X 若产生式为 X? X1X2…Xn 按逆序即Xn…X2X1入栈 出错 X=’#’ X∈VT X=a M[X,a]是产生式吗 出错 X=a 读入下一个符号 结束 是 是 是 是 否 否 否 否 否 是 2、LL（1）分析法实验设计思想及算法 三、实验过程和指导： （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求： 程序输入/输出示例： 对下列文法，用两种分析法对任意输入的符号串进行分析： （1）E-TG （2）G-+TG （3）G-ε （4）T-FS （5）S-*FS （6）S-ε （7）F-(E) （8）F-i 输出的格式如下： (1)递归下降分析程序 输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# 输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 (2)LL（1）分析： 输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# 输出结果：i+i*i#为合法符号串 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。 分析栈剩余输入串所用产生式Ei+i*i#E-TG4.与读文件有关的函数： FILE *fp; ????? if((fp=fopen(E:\\222.txt,r))==NULL){?? //读取文件内容，并返回文件指针，该指针指向文件的第一个字符 ?fprintf(stderr,error opening.\n); ?????????? exit(1); ????? } fgetc（fp） 从数据流中区下一个字符 fopen? 文件打开函数，返回指向文件第一个字符的指针 （四）程序思路（仅供参考）： 递归下降分析法： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 LL（1）分析法： 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；