(需打印的)编译原理实验报告.doc

编译原理 实验报告 20122013学年第一学期 班 级 姓 名 学 号 指导教师 张春梅 实验一 词法分析器的设计（4学时）一、实验目的和要求加深对状态转换图的实现及词法分析器的理解。熟悉词法分析器的主要算法及实现过程。要求学生掌握词法分析器的设计过程，并实现词法分析。二、实验基本内容给出一个简单语言的词法规则，画出状态转换图，并依据状态转换图编制出词法分析程序，该程序的数据输入是一段C代码，输出数据为单词的二元式。现给出词法规则如下：单词符号 种别码 内码auto 1break 2case 3char 4const 5continue 6default 7do 8float 9for 10if 11int 12long 13return 14struct 15switch 16void 17while 18 30 32= 33= 34!= 35( 36） 37 38 39* 40/ 41* 42= 43， 44； 45! 46 47& 48| 49 50 51标识符 60常数 70 二进制形式三、问题描述及基本算法提示1 状态转换图的实现让每个结点对应一小段程序。 需引进一组全局变量和过程、函数 （1）ch 字符变量，存放最新读进的源程序字符。（2）strToken 字符数组，存放构成单词符号的字符串。 （3）GetChar 子程序过程，将下一个输入字符读到ch中，搜索指示器前移一个字符位置。 （4）GetBC 子程序过程，检查ch中字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。（5）Concat 子程序过程，将ch中的字符连接到strToken之后。例如， 假定strToken 原来的值为“AB”,而ch中存放着C,经调用Concat后，strToken的值就变为”ABC”。（6）IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。（7）Reserve 整型函数过程，对strToken中的字符找保留字表，若它是一个保留字，则返回它的编码，否则返回0值。（8）Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。（9）InsertId 整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。（10）InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。2词法分析器构造基本算法int k=0,i=0,code;char strToken20=”; /*置strToken为空串*/while (ai!=0) GetChar();GetBC();if (IsLetter() k=0; while (IsLetter() or IsDigit() Concat();GetChar(); Retract(); code : = Reserve(); if(code = 0) 输出二元式：; else 输出二元式：;else if (IsDigit() k=0; while(IsDigit() Concat();GetChar(); Retract(); 输出二元式：; else if (ch = ) GetChar();if (ch=) 输出二元式31, ;else Retract(); 输出二元式 30,;else if (ch = ) GetChar();if (ch=) 输出二元式= ;else Retract(); 输出二元式 ; else if (ch = = ) GetChar();if (ch=) 输出二元式;else Retract(); 输出二元式;else if (ch = !) GetChar();if (ch=) 输出二元式;else Retract(); 输出二元式;else if (ch = *) GetChar();if (ch=*) 输出二元式;else Retract(); 输出二元式 ;else if (ch = () 输出二元式;else if (ch = ) 输出二元式;else if (ch = +) 输出二元式;else if (ch = -) 输出二元式;else if (ch = /) 输出二元式;else if (ch = ,) 输出二元式;else if (ch = ;) 输出二元式;else if (ch = ) 输出二元式;else if (ch = ) 输出二元式;else if (ch = ) 输出二元式;else if (ch = &) GetChar();if (ch=&) 输出二元式;else Retract(); 输出二元式 ;else if (ch = |) GetChar();if (ch=|) 输出二元式;else Retract(); 输出二元式;else if (ch=0) return; printf(“ERROR INPUT!n”); 四、实验测试结果：实验成绩 指导教师 实验二 语法分析器设计LR分析器（8学时）一、实验目的和要求使学生理解LR分析器的构造过程及产生LR分析表的具体算法二、实验基本内容选择一种LR文法（LR（0）、SLR（1）、LALR（1）、LR（1），设计出一个LR分析器。1 对输入的文法进行判断，是否为相应LR文法，若不是提示重新输入文法。2 若是构造相应的LR分析表。3 输入一个句子，输出其分析过程（移进，归约，接受）三、问题描述及算法提示4 文法进行拓广5 构造I 的闭包CLOSURE（I）I是文法G的任一项目集。（1）I的任何项目都属于CLOSURE（I）（2）若AB属于CLOSURE（I）。则关于BVN的产生式B项目BCLOSURE（I） （3）重复执行上述步骤直至CLOSURE（I）不再增大为止。6 求出状态转换函数GO（I，X）GO（I，X）CLOSURE（J）J形如AX的项目|AX属于I4求出项目集规范族C的算法（1）CLOSURE（S S）C（2）对C中每一项目集I和文法G的每个符号X做若GO(I,X)非空且不属于C,则把GO(I,X)加入C（3）重复（1）,（2） 直至C不再增大为止.5. LR(0)分析表构造假定C=I0,I1In,每个项目Ik的下标K作为分析器状态,令包含项目S S的集合Ik的下标K为初态.分析表的ACTION子表和GOTO子表的构造(1)若项目Aa属于Ik且GO(Ik，a)Ij. aVT,则置ACTIONk,a为”把(j,a)移进栈”,简记为S j(2)若项目AIk,那么对于任意aVT(或#)置ACTIONk,a为“用产生式A进行归约”简记为rj (A是文法G的第j个产生式)(3)若项目S SIk,则置ACTIONk,#为“接受“，记为“acc”(4)若GO(Ik,A)= Ij,A为非终结符,置GOk,a= j(5)分析表中凡不能用规则（1）（4）填入信息的空白格置上“报错标志”6.写出总控程序进行分析输入：一个输入串和一张LR分析表输出：若L（G），对于的一个自下而上的分析，否则出错。开始时，（S0，）在分析栈顶，在输入缓冲区ip指向输入串的第一个输入符号 while (t=True) DO BEGIN使S是栈顶状态，a是ip指向的符号； if actions,a=sj then Begin将a和j压入分析栈，修改ip，使其指向下一个输入符号； end； else if actions,a=rj (A) Begin从分析栈顶弹出2|个符号，令S是当前栈顶状态;将A和gotos,A压入分析栈;输出产生式Aendelse if actions,a=acc return else error();endif; end