编译原理实验(递归向下语法分析法实验).docx

实验二 递归向下分析法 一、 实验目和要求 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、 实验内容 功能描述 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为 LL（1）文法， 3、递归下降分析法实验设计思想及算法 为 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 ①如果 xi 为终结符号： if(xi= = 当前的符号) { NextChar()； return; } else 出错处理 ②如果 xi 为非终结符号，直接调用相应的过程 xi() 说明： NextChar 为前进一个字符函数。 程序结构描述程序要求： 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E-TG （2）G-+TG|—TG （3）G-ε （4）T-FS （5）S-*FS| / FS （6）S-ε （7）F-(E) （8）F-i 输入出的格式如下： (1)E 盘建立一个文本文档 222.txt存储一个以#结束的符号串(包括+—*/（）i#)，在此位 置 输 入 符 号 串 例 如 ：i+i*i# (2) 输出结果：i+i*i#为合法符号串 备注：输入一符号串如 i+i*#,要求输出为“非法的符号串” 函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。程序所用主要参数和头文件说明： #includestdio.h #includestdlib.h #includestring.h FILE *fp; //定义一个全局文件指针变量 char ch; //定义一个全局字符变量 #define N 20 //定义一个数组大小常量 char string[N]; //定义一个用于存储算式字符串的数组char *p; //定义一个全局字符指针变量 函数说明： 非终结符函数 E() 函数功能描述：根据以上文法要求 E-TG,所以从主函数开始调入第一个非终结符函数执行，显示调用产生式，依次嵌套调用非终结符函数 T（）和 G（），进行递归向下分析。 void E(){printf(E---TG..............%c\n,ch); T(); G();} 非终结符函数 T() 函数功能描述：根据以上文法要求 T-FS,首先显示算式匹配所用的显示调用的产生式， 依次嵌套调用非终结符函数 F（）和 S（），进行递归向下分析。 void T(){ printf(T---FS..............%c\n,ch); F(); S();} 非终结符函数 G() 函数功能描述：根据以上文法要求 G-+TG|—TG ，G-ε，如果当前字符变量 ch 为“+”， 则显示调用产生式，首先嵌套调用 test()函数判断是算式递归向下分析是否结束，若没有结束则继续依次嵌套调用非终结符函数 T（）和 G（）；如果当前字符变量 ch 为“-”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，继续依次嵌套调用非终结符函数 T（）和 G（）；如果当前字符变量 ch 既不为“+” 也不为“-”，非终结符 G 指向为空，函数只用于显示指向为空，找不到可以和文件中字符匹配的非终结符。void G(){ if (ch==+){ printf(G---+TG..............%c\n,ch); *p=ch; p++; ch=fgetc(fp); T(); G(); } else if(ch==-) { printf(G----TG..............%c\n,ch); *p=ch; p++; ch=fgetc(fp); T