计算机学院实验报告课程名称：编译原理实验人学号：******xx 姓名：xxx 实验完成日期：2014年5月20日报告完成日期：2014年5月20日目录实验一词法分析程序的设计与实现 (3)词法的正规式描述： (3)状态图： (4)词法分析程序数据结构与算法： (4)词法分析算法： (5)实验结果： (7)实验中遇到的问题及其解决： (8)1、保留字的检测问题： (8)2、关于0为首位的数字是int8、int10和int16的判断问题： (8)3、关于回退的问题： (8)实验二自顶向下的语法分析—递归子程序法 (9)改写后的产生式集合： (9)化简后的语法图： (9)递归子程序算法 (10)实验结果： (13)实验中遇到的问题及其解决： (14)1、消除左递归，提取左因子之后的E、T对应的子程序的编写问题： (14)2、缩进的控制： (14)实验三语法制导的三地址代码生成程序 (15)语法制导定义： (15)三地址代码生成器的数据结构 (16)三地址生成器算法： (17)实验结果： (21)实验中遇到的问题及其解决： (22)1、根据化简后的产生式修改语法制导定义： (22)2、使用真假出口法和继承属性来确定goto的标号： (22)实验一词法分析程序的设计与实现词法的正规式描述：标识符 <字母>(<字母>|<数字字符>)*十进制整数 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*八进制整数 0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十六进制整数0(x|X)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e |f)*运算符和分隔符 + - * / > < = ( ) ;关键字 if then else while do .状态图： 开始标识符或保留字a-z/A-Z Int8或int10或int160十进制数1-9保留字标识符其他运算符和分隔符If/then/while/do/else + - * / > < = ( ) ;Int 16X/xint81-7int10其他词法分析程序数据结构与算法：//单词类class Token {public :int type;//种别string value;//属性值string name;//单词具体内容Token() {type = DEFAULT;value = NONE_OF_VALUE;}Token(int type, string value, string name): type(type), value(value), name (name){}~Token() {}};词法分析算法：Token* TokenScan(ifstream &from_file) {char ch;//用于保存从文件中读取的字符//读第一个字符int i =0;char value[30] ="";//用来存放token的属性值ch = from_file.get();while (ch == BLANK || ch == TAB || ch == NEWLINE) {ch = from_file.get();}////////////////////////////////////以下为标识符的检测//////////////////////////////////////////////////////////////////////////// if (isalpha(ch)) {value[i++] = ch;ch = from_file.get();////判断后续的是否为IDN的成分（数字或字母）while (isalnum(ch)) {value[i++] = ch;ch = from_file.get();}//直到不是IDN成分，回退一字符from_file.unget();//TODO：这里加上保留字检测部分//进行字符串的对比，即可比较出保留字，通过压栈的形式来获得完整的属性值////////////////////////////////////以下为保留字的检测//////////////////////////////////////////////////////////////////////////// if (strcmp(value, WORD_IF) ==0) return new Token(IF, NONE_OF_VALUE, WO RD_IF);if (strcmp(value, WORD_THEN) ==0) return new Token(THEN, NONE_OF_VALUE, WORD_THEN);if (strcmp(value, WORD_ELSE) ==0) return new Token(ELSE, NONE_OF_VALUE, WORD_ELSE);if (strcmp(value, WORD_WHILE) ==0) return new Token(WHILE, NONE_OF_VALU E, WORD_WHILE);if (strcmp(value, WORD_DO) ==0) return new Token(DO, NONE_OF_VALUE, WO RD_DO);return new Token(IDN, value, value);}////////////////////////////////////以下为数字的检测//////////////////////////////////////////////////////////////////////////// if (isdigit(ch)) {value[i++] = ch;//如果第一个数字是0，则有可能是INT10的0、INT8或INT16if (ch =='0') {ch = from_file.get();if ((ch >='0'&& ch <'8') || ch =='x'|| ch =='X') {//如果0后面紧跟着数字0-8，则为INT8if (isdigit(ch)) {while (ch >='0'&& ch <'8') {value[i++] = ch;ch = from_file.get();}from_file.unget();return new Token(INT8, value, value);}value[i++] = ch;//到这一步的都是INT16ch = from_file.get();while (isdigit(ch) || (ch >='a'&& ch <='f')) {value[i++] = ch;//TODO:这里没有解决0xrtr的问题ch = from_file.get();}from_file.unget();return new Token(INT16, value, value);} else {//0后面的不为0-7的digit或x或X等 8或16进制特征字符，则为10进制的0，回退一个字符from_file.unget();return new Token(INT10, value, value);}}//能到这一步的都是INT10,且不为0打头ch = from_file.get();while (isdigit(ch)) {value[i++] = ch;ch = from_file.get();}from_file.unget();return new Token(INT10, value, value);}////////////////////////////////////以下为运算符的检测//////////////////////////////////////////////////////////////////////////// value[i++] = ch;switch (ch) {case'+':return new Token(ADD, value, "+");case'-':return new Token(MINUS, value, "-");case'*':return new Token(MUL, value, "*");case'/':return new Token(DIC, value, "/");case'>':return new Token(MORE, value, ">");case'<':return new Token(LESS, value, "<");case'=':return new Token(EQU, value, "=");case'(':return new Token(LBRAC,value, "(");case')':return new Token(RBRAC, value, ")");case';':return new Token(COMMA, value, ";");default:ErrorHandle(from_file); break;}return new Token(DEFAULT, NONE_OF_VALUE, NONE_OF_VALUE); }实验结果：实验中遇到的问题及其解决：1、保留字的检测问题：一开始的时候我的想法是遇到if、while、do、then等单词的首字母时即开始划分状态，后来发现这样子判断的分支会特别多，而且效率不是很高，对保留字集合的扩展支持的也不是很好。

后来我发现保留字存在于标识符的子集，所以为什么不先判断标识符然后再判断是不是保留字呢？后来我就照着这个思路成功实现了功能。