简单编译器编译原理的设计.doc

1、编译原理课程设计简单编译器简单编译器目 录1 词法分析21.1 实验目的21.2 实验要求21.2.1待分析的简单的词法21.2.2 各种单词符号对应的种别码：21.2.3 词法分析程序的功能：31.3 词法分析程序的算法思想：31.3.1 主程序示意图：31.3.2 扫描子程序的算法思想：41.3.3 词法分析程序的C语言程序源代码：61.3.4 结果分析：61.3.5 总结：72 语法分析82.1 实验目的82.2实验要求82.2.1 待分析的简单语言的语法82.2.2 实验算法结构8语法分析程序的算法思想82.3 结果分析：132.4 总结：153 语义分析程序163.1 实验目的：16

2、3.2 实验要求：163.3 算法思想：163.3.1 程序结构图163.3.2 设置语义过程203.3.3 函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。213.3.4 简单赋值语句的翻译文法213.4 结果分析223.5 总结：251 词法分析(李梦珂 201181216 负责)1.1 实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。1.2 实验要求设计、编制并调试一个词法分析程序，三人一组。1.2.1待分析的简单的词法（1）关键字： int if then else while do

3、 read write所有的关键字都是小写。（2）运算符和界符： := = + - + - * / = = ; ( ) #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：ID = letter (letter | digit)*NUM = digit digit*（4） 空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 1.2.2 各种单词符号对应的种别码：表1.1 各种单词符号对应的种别码单词符号种别码 单词符号种别码int1+17If2-18Then3:=19else420while5!=21do623wr

4、ite8=24lettet（letter|digit）*10=25dight dight*11;26=12(27+13)28-1430*15!31/16:32 ,3335 36 1.2.3 词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。例如：对源程序输入如下： Int x,y; X:=2*y; If(x5) Then x:=2*x+2/3;#后经词法分析输出如下序列：( 35 (int 1)(x 10)(, 33)(y 10) (；26)(x 10)1.3

5、 词法分析程序的算法思想：算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。1.3.1 主程序示意图：主程序示意图如图1.1所示。其中初始包括以下两个方面： 关键字表的初值。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：Char *rwtab6 = “int”, “if”, “then”, “else”,“while”, “do”, “read”,”wr

6、ite”; 图1.1（2）程序中需要用到的主要变量为syn,token和sum 1.3.2 扫描子程序的算法思想：首先设置3个变量：token用来存放构成单词符号的字符串；sum用来整型单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图1.2所示。 图 1.21.3.3 词法分析程序的C语言程序源代码：1.3.4 结果分析：输入如下： Int x,y; X:=2*y; If(x5) Then x:=2*x+2/3;#后经词法分析输出如下序列：( 35 (int 1)(x 10)(, 33)(y 10) (；26)(x 10) 如图1.3所示： 图1.31.3.5 总结：词法分析的

7、基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。 2 语法分析2.1 实验目的编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。2.2实验要求利用C语言编制递归下降分析程序，并对简单语言进行语法分析。2.2.1 待分析的简单语言的语法用扩充的BNF表示如下：=;：=；：=：=ID：=：=+ | -：=* | /：=ID | NUM | （）2.2.2 实验算法结构输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印

8、“success”，否则输出“error”。例如： 输入 int a,x,b; a:=9; x:=2*3; b:=a+x 输出 success！ 语法分析程序的算法思想（1） 主程序示意图如图2.1所示。 图2.1 语法分析主程序示意图（2）递归下降分析程序示意图如图2.2所示。 图2.2 递归下降分析程序示意图（3）语句串分析过程示意图如图2.3所示。图2-3 语句串分析示意图（4）statement语句分析程序流程如图2.4、2.5、2.6、2.7所示。 图2.4 statement语句分析函数示意图 图2.5 expression表达式分析函数示意图图 2.6 term分析函数示意图 图

9、2.7 factor分析过程示意图2.3 结果分析：输入 后输出success！ 如图2.8所示：图2.8输入 后输出 error 如图2.9所示：图2.92.4 总结：通过本次试验，了解了语法分析的运行过程，主程序大致流程为：“置初值”调用scaner函数读下一个单词符号调用IrParse结束。递归下降分析的大致流程为：“先判断是否有声明”不是则“出错处理”，若是则“调用scaner函数”调用语句串分析函数“判断是否为end”不是则“出错处理”，若是则调用scaner函数“判断syn=0&kk=0是否成立”成立则说明分析成功打印出来。不成立则“出错处理”。3 语义分析程序3.1 实验目的：通

10、过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。3.2 实验要求：采用递归下降语法制导翻译法，对算术表达式、赋值语句进行语义分析并生成四元式序列。3.3 算法思想：3.3.1 程序结构图（1）主程序示意图如图3.1所示。 图3.1 语法分析主程序示意图（2）递归下降分析程序示意图如图3.2所示。（3）语句串分析过程示意图如图3.3所示。 图3.2递归下降分析程序示意图 图3.3 语句串分析示意图（4）statement语句分析程序流程如图3.4、3.5、3.6、3.7所示。 图3.4 statement语句分析函数示意图 图3.5 expr

11、ession表达式分析函数示意图图 3.6 term分析函数示意图图2-7 factor分析过程示意图3.3.2 设置语义过程（1）emit(char *result,char *ag1,char *op,char *ag2)该函数的功能是生成一个三地址语句送到四元式表中。四元式表的结构如下：structchar result8;char ag18;char op8;char ag28;quad20; (2) char *newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，char *newtemp(void)char *p; char m8; p=(char *

12、)malloc(8); k+; itoa(k,m,10); strcpy(p+1,m); p0=t; return(p);3.3.3 函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。3.3.4 简单赋值语句的翻译文法SID n ifD n p = E x 若ID定义,则emit x (n=x) ;否则错误E x T q + T r x=newtemp ;emit x qr (x=q + r)T x F q * F r x=newtemp ;emit x qr (x=q * r)F x ID n ifD n p

13、；x=n F x ( E q ) x=qF x NUM lexval ifD lexval p ; x= lexval ifD过程表示在符号表中查找标识符，若不存在，则报告“变量未定义而使用”的错误，若存在，返回标识符在符号表中的入口地址p。在执行语义规则，输出四元式时， 参数可用变量名、临时变量名以及整常数代替。 newtemp()函数用来产生临时变量, 如产生临时变量t1 : N=N+1; “t”| ITOS(N) ;emit()函数产生四元式代码: 例如用输出函数输出：t1=q+r 例如：翻译x=sum*(b+c)； 四元式是： t1=b+c t2=sum*t1 x=t2;在下面的递归下

14、降语法制导翻译程序中，sym和symval 读取词法分析结果中的单词二元式. 如：对于单词二元式 (ID sum）, 则ID存入syn中，sum存入scaner中。3.4 结果分析3.5 总结：通过本次试验，了解了语法分析的运行过程，主程序大致流程为：声明-“置初值”调用scaner函数读下一个单词符号调用IrParse四元式输出-结束。递归下降分析的大致流程为：“先判断是否有声明”不是则“出错处理”，若是则“调用scaner函数”调用语句串分析函数“判断是否为”不是则“出错处理”，若是则调用scaner函数“判断syn=0&kk=0是否成立”成立则说明分析成功打印出来。不成立则“出错处理”。26