编译原理-词法分析

1、课 程 设 计 报 告课程名称 编译原理 课题名称 Micro语言词法语法分析 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 湖南工程学院编译原理课程设计湖南工程学院课 程 设 计 任 务 书课程名称 编译原理 课 题 专业班级 学生姓名 学 号 审 批 任务书下达日期 任务完成日期 52011级编译原理课程设计任务书一、 课程设计的性质和目的编译原理课程设计是计算机专业课程，通过课程设计使学生进一步巩固课堂所学知识，全面熟悉、掌握编译程序编写的基本设计方法和技巧，进一步提高分析问题、解决问题及上机操作能力，为将来从事高层次的计算机软件开发工作打下一定的专业基础。二、 设计课题课

2、题一：应用编译原理的方法实现带括号的四则混合运算 给定条件：1、 词法符号定义如下：INTC à D+ FLOATC à (D+.D+) | (D+.) | ( .D+) FLOATC à( (D+.D+) | (D+.) | ( .D+)| (D+) ) ( E | e ) ( + | | ) D+ OPADD à +OPSUB à OPMUL à *OPDIV à /LPAREN à (RPAREN à )LINE à nASSIGN à =2、 表达式文法定义如下：01. S &

3、#224; E02. E à T03. E à E OPADD T04. E à E OPSUB T05. T à P06. T à T OPMUL P07. T à T OPDIV P08. P à INTC09. P à FLOATC10. P à LPAREN E RPAREN基本要求：1、 以ASSIGN作为文法结束符号； 2、 应用词法分析技术识别单词；3、 应用SLR(1)分析技术判别表达式的合法性；4、 应用尾动作文法技术计算表达式的类型与值；5、 要求表达式的类型与值严格一致。课题二：Mi

4、cro语言词法语法分析 给定条件：1、 词法符号定义如下：ID à L(L|D)*INTC à D+REALC à D+ · D+PLUS à +MULT à *LPAREN à (RPAREN à )COLON à ：ASSIGN à ：SEMI à ；LINE à nSTOP à ·FEOF à EOF2、 表达式文法定义如下：01. PROGàBEGIN DECL BODY END STOP02. DECLàDECL V

5、AR ID COLON TYPE SEMI03. DECLàVAR ID COLON TYPE SEMI04. TYPEàREAL 05. TYPEàINTEGER 06. BODYàBODY SEMI STM07. BODYàSTM08. STMàID ASSIGN EXP09. STMàWRITE LPAREN EXP RPAREN10. STMàREAD LPAREN ID RPAREN11. EXPàEXP PLUS FACT12. EXPàFACT13. FACTàFACT

6、MULT PRIM14. FACTàPRIM15. PRIMàID16. PRIMàINTC17. PRIMàREALC18. PRIMàLPAREN EXP RPAREN基本要求：1、 以FEOF作为文法结束符号； 2、 应用词法分析技术识别单词； 3、 应用SLR(1)分析方法进行语法分析；4、 报错要指明所在行。三、 课程设计报告要求1、 课程设计报告必须按本系规定的格式要求打印成册；2、 课程设计报告每人一份，正文必须包含如下几个方面的内容：1) 基本设计思想；2) 主要数据结构；3) 总结与体会。3、 课程设计报告装订顺序：封面、任务

7、书、目录、正文、源程序清单。四、 选题及考核办法1、 一人一组，学号为奇数者做课题一，学号为偶数者做课题二。2、 成绩考核按个人课题完成情况、设计报告质量及对课程设计的态度等综合评定。五、设计进度安排1、 讲课时间安排：2、 上机调试时间安排：17周：周一 8:0011:30 周二 2:306:00 周四8:0011:30 周五 2:306:003、 答辩时间安排：4、 其余时间：查阅资料，确定方案，设计课题相关程序。 目 录一、基本设计思想7二、 基本设计分析71. Micro语言词法分析72. Micro语言语法分析器8三、主要的数据结构14四、 调试及运行结果15五、 总结及体会17六

8、源程序清单17一、基本设计思想该课题是根据Micro语法对输入的字符串源代码进行词法分析和语法分析，判定是否符合Micro的语法规则。基础知识有：基本符号；程序文本；程序文件；语义单位；单词分类；空格符号；换行符号；单词编码；语义信息；读进字符；识别字符；过滤格式符；常数翻译；读进常数；读进标识符；保留字。Micro语言定义：定义一个很小的语言Micro，其程序是由begin和end括起来的语句序列，而语句则只有赋值语句、输入语句和输出语句3种。变量均定义为整型变量。表达式由整数、变量和运算符组成。2、 基本设计分析 1.Micro语言词法分析 1） 以英文翻译为例：首次依次分辨出一个单词并查

9、字典，若查到则认为单词未错，否则认为单词错。如果是正确的单词，则还要确定其词类，即确定是名词还是动词。程序文件的处理过程也类似。 词法分析部分是通过构造有穷自动机来实现的。对自动机的每一个状态，都设置状态标志，这样就能够 实时查看词法分析进入的状态，在词法分析中需要对分析出的标识符进行是否有保留字的判断，保留字和词法分析的各状态标志都定义在全局变量中。2）Micro语言各词法元素的正则表达式ID à L(L|D)*INTC à D+REALC à D+ · D+PLUS à +MULT à *LPAREN à (RPAREN

10、 à )COLON à ：ASSIGN à ：SEMI à ；LINE à nSTOP à ·FEOF à EOF3）Micro语言的有限自动机13·0L1L|DD2D·34DD5+6*7(8)9:10=11;12nIDINTCREALCPLUSMULTLPARENRPARENCOLONASSIGNSEMILINESTOP2. Micro语言语法分析器1） 语法分析任务：语法分析的任务是检查源程序是否为合法的单词序列。若有错误，则可指出错误单词的位置（第几行，第几个单词）和错误性质等 语法分析部

11、分使用SLR(1)方法进行语法分析，该方法不显示的使用符号栈，而是使用状态栈，SLR(1)方法的核心是构造action表和goto表，这里使用了action图来表示，在课题中已经画出了各个状态接收Token后的动作，因此程序中只需要进行相应的添加即可。SLR(1)语法分析方法的主要动作有两个，一是进行移入操作（shiift）二是进行规约（reduce）动作。使用SLR(1)方法需要求出非终极符的Follow集。该编译程序对出错的信息进行了行输出，指出了出错的行，对出错行的处理时单独进行的。2） Micro语言SLR(1)语法分析01. PROGàBEGIN DECL BODY END

12、 STOP02. DECLàDECL VAR ID COLON TYPE SEMI03. DECLàVAR ID COLON TYPE SEMI04. TYPEàREAL 05. TYPEàINTEGER 06. BODYàBODY SEMI STM07. BODYàSTM08. STMàID ASSIGN EXP09. STMàWRITE LPAREN EXP RPAREN10. STMàREAD LPAREN ID RPAREN11. EXPàEXP PLUS FACT12. EXP

13、4;FACT13. FACTàFACT MULT PRIM14. FACTàPRIM15. PRIMàID16. PRIMàINTC17. PRIMàREALC18. PRIMàLPAREN EXP RPAREN符号FIRST集合FOLLOW集合PROGBEGINFEOFDECLVARID WRITE READ VARTYPEREAL INTEGERSEMIBODYID WRITE READSEMI ENDSTMID WRITE READSEMI ENDEXPID INTC REALC LPARENSEMI END PLUS RPAR

14、ENFACTID INTC REALC LPARENSEMI END PLUS RPAREN MULTPRIMID INTC REALC LPARENSEMI END PLUS RPAREN MULT 12BODYàBODY SEMI· STMSTMà·ID ASSIGN EXPSTMà·WRITE LPAREN EXP RPARENSTMà·READ LPAREN ID RPARENSTMS19ID S7WRITES8READS910DECLàVAR ID· COLON TYPE SEMICO

15、LONS178STMàWRITE· LPAREN EXP RPARENLPAREN S156BODYàSTM·SEMIR7ENDR72PROGàBEGIN DECL·BODY END STOPDECLàDECL· VAR ID COLON TYPE SEMIBODYà·BODY SEMI STMBODYà·STMSTMà·ID ASSIGN EXPSTMà·WRITE LPAREN EXP RPARENSTMà·RE

16、AD LPAREN ID RPARENBODYS4VARS5STMS6IDS7WRITES8READS90PROGà·BEGIN DECL BODY END STOPBEGINS113DECLàDECL VAR ID· COLON TYPE SEMICOLONS2011PROGàBEGIN DECL BODY END· STOPSTOPS189STMàREAD· LPAREN ID RPARENLPAREN S167STMàID· ASSIGN EXPASSIGNS145DECLàDE

17、CL VAR· ID COLON TYPE SEMIIDS134PROGàBEGIN DECL BODY· END STOPBODYàBODY· SEMI STMEND S11SEMI S123DECLàVAR· ID COLON TYPE SEMIID S101PROGàBEGIN· DECL BODY END STOPDECLà·DECL VAR ID COLON TYPE SEMIDECLà·VAR ID COLON TYPE SEMIDECLS2VARS32

18、2EXPàFACT·FACTàFACT· MULT PRIMMULTS35 SEMIR12ENDR12PLUSR12RPARENR1223FACTàPRIM·SEMIR14ENDR14PLUSR14RPARENR14MULTR1421STMàID ASSIGN EXP·EXPàEXP· PLUS FACTPLUSS34SEMIR8ENDR820DECLàDECL VAR ID COLON· TYPE SEMITYPEà·REALTYPEà

19、3;INTEGERTYPES33REALS31INTEGERS3219BODYàBODY SEMI STM·SEMIR6ENDR618PROGàBEGIN DECL BODY END STOP·FEOFR117DECLàVAR ID COLON· TYPE SEMITYPEà·REALTYPEà·INTEGERTYPES30REALS31INTEGERS3216STMàREAD LPAREN· ID RPARENIDS2915STMàWRITE LPAREN

20、3; EXP RPARENEXPà·EXP PLUS FACTEXPà·FACTFACTà·FACT MULT PRIMFACTà·PRIMPRIMà·IDPRIMà·INTCPRIMà·REALCPRIMà·LPAREN EXP RPARENEXPS28FACTS22PRIMS23IDS24INTCS25REALCS26LPARENS2714STMàID ASSIGN· EXPEXPà·EXP

21、PLUS FACTEXPà·FACTFACTà·FACT MULT PRIMFACTà·PRIMPRIMà·IDPRIMà·INTCPRIMà·REALCPRIMà·LPAREN EXP RPARENEXPS21FACTS22PRIMS23IDS24INTCS25REALCS26LPARENS2735FACTàFACT MULT· PRIMPRIMà·IDPRIMà·INTCPRIMà&

22、#183;REALCPRIMà·LPAREN EXP RPARENPRIMS42IDS24INTCS25REALCS26LPARENS2733DECLàDECL VAR ID COLON TYPE· SEMISEMIS4031TYPEàREAL·SEMIR427PRIMàLPAREN· EXP RPARENEXPà·EXP PLUS FACTEXPà·FACTFACTà·FACT MULT PRIMFACTà·PRIMPRIMà

23、;·IDPRIMà·INTCPRIMà·REALCPRIMà·LPAREN EXP RPARENEXPS36FACTS22PRIMS23IDS24INTCS25REALCS26LPARENS2734EXPàEXP PLUS· FACTFACTà·FACT MULT PRIMFACTà·PRIMPRIMà·IDPRIMà·INTCPRIMà·REALCPRIMà·LPAREN EXP RP

24、ARENFACTS41PRIMS23IDS24INTCS25REALCS26LPARENS2732TYPEàINTEGER·SEMIR530DECLàVAR ID COLON TYPE· SEMISEMIS3929STMàREAD LPAREN ID· RPARENRPARENS3828STMàWRITE LPAREN EXP· RPARENEXPàEXP· PLUS FACTRPARENS37PLUSS3426PRIMàREALC·SEMIR17ENDR17PLUSR17R

25、PARENR17MULTR1725PRIMàINTC·SEMIR16ENDR16PLUSR16RPARENR16MULTR1624PRIMàID·SEMIR15ENDR15PLUSR15RPARENR15MULTR1543PRIMàLPAREN EXP RPAREN·SEMIR18ENDR18PLUSR18RPARENR18MULTR1841EXPàEXP PLUS FACT·FACTàFACT· MULT PRIMMULT S35SEMIR11ENDR11PLUSR11RPARENR1139D

26、ECLàVAR ID COLON TYPE SEMI·IDR3WRITER3READR3VARR342FACTàFACT MULT PRIM·SEMIR13ENDR13PLUSR13RPARENR13MULTR1340DECLàDECL VAR ID COLON TYPE SEMI·IDR2WRITER2READR2VARR238STMàREAD LPAREN ID RPAREN·SEMIR10ENDR1037STMàWRITE LPAREN EXP RPAREN·SEMIR9ENDR936PR

27、IMàLPAREN EXP· RPARENEXPàEXP· PLUS FACTRPARENS43PLUSS34三、主要的数据结构在词法分析部分使用了堆栈lexstack来记录出现的错误的字符，用枚举类型来定义频繁使用的关键字，文法非终极符等常量。在本程序中没有使用递归的方法来进行词法分析，这里使用了while循环和switch语句相结合的方式，有效地提高了词法分析的效率。在语法分析部分，使用了状态栈state来保存语法分析进入的各个状态，对于每一个状态的可能的两种动作，采用了宏定义的形式来定义移入操作（shift）和规约动作（reduce）。这里显示的使

28、用了状态栈，不显示的使用符号栈，在进行规约动作中需要指出文法产生式左部的非终极符和该产生式右部的文法符号的个数。规约的动作可以是一个递归的过程，这里也是使用了while循环和swith语句相结合的方式来对当前的Token和预读入的Token进行相应的处理。该程序的主要函数及其功能如下：int main(int argc,char *argv)函数：如果在命令行中运行本程序的话，需要带上相应的参数，其中第一个各参数即为该程序可执行文件的名称，第二个参数为要进行编译处理的源程序的文件名，第三个参数为经过程序处理后错误信息的输出文件名（可以没有参数）LexType lex(char *word)函数

29、：该函数主要是进行词法分析，通过调用该函数即可得到一个Token，该Token的值保存在参数word中。Void getnexttoken(char *word)函数：该函数也是获取一个Token，它是通过调用lex函数来实现获取一个Token的。Void parse（void）函数：该函数主要是语法分析的部分，通过语法分析即可得出相应的分析结果。各函数的调用关系式main函数调用parse函数，parse函数调用getnexttoken函数，而getnexttoken函数则调用词法分析函数lex；4、 调试及运行结果测试用例：BeginVar x：integer； Read(x)End。手动

30、分析如下：1(LPAREN，“（”)2(ID，“x”) 3(COLON，“：”) 4(SEMI，“；”) 5(STOP，“.”) 6(RPAREN，“)”)01Var x:integer; read(x) end.S3013x: integer; read(x) end.S1001310: integer; read(x) end.S170131017integer; read(x) end.S32013101732; read(x) end.R50131017TYPE ; read(x) end.S30013101730; read(x) end.S3901310173039read(x)

31、end.R301DECL read(x) end.S2012read(x) end.S90129(x) end.S16012916x) end.S2901291629) end.S380129162938end.R10012STM end.S60126end.R7012BODY end.S40124end.S11012411.S1801241118FEOFR10PROG测试用例及其运行结果1.错误在第三行：2.错误在第四行：3.正确的micro语言文法：5、 总结及体会通过此次课程设计，使我更加扎实的掌握了词法分析及语法分析的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又

32、一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获龋最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，

33、收获喜悦，也永远不可能得到社会及他人对你的认可!课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。通过这次课程设计，我掌握了编译原理基本的设计与实现，对于编译器和解释器的概念有了较深的理解。我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮

34、助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重

35、，但可喜的是最终都得到了解决。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。6 源程序清单#include <stdio.h>#include <string.h>#define ReserveNum 7#define BUFSIZE 1024#define SHIFT(NUM) top+; statetop=NUM; getnexttoken(word,in,out)#define REDUCE(SYM,NUM) top=top-NUM; buftoken=curtoken;

36、 buftokenflag=1; curtoken=SYM#define ERRORPROCESS fprintf(out,"Error line:%dn",lineno)typedef enum /*关键字*/ BEGIN, END, VAR, READ, WRITE, INTEGER, REAL, /*其它词法符号*/ ID, INTC, REALC, PLUS, MULT, LPAREN, RPAREN, COLON, ASSIGN, SEMI, STOP, LINE, /*文法的非终极符*/ PROG, DECL, BODY, TYPE, STM, EXP, FAC

37、T, PRIM, /*词法分析和语法分析程序依赖的2个单词类别*/ FEOF, ERROR LexType;/* 语法分析使用的变量 */static LexType curtoken,buftoken;static int buftokenflag=0;static int lineno=1;LexType lex(char *word,FILE *in) static char *Reserve="begin","end","var","read","write","integer

38、","real" static LexType StateFlag=ERROR,ID,INTC,ERROR,REALC,PLUS,MULT, LPAREN,RPAREN,COLON,ASSIGN,SEMI,LINE,STOP; static char stackBUFSIZE; static int stacktop=-1; char trywordBUFSIZE; LexType tryflagBUFSIZE; int index;int state;char curchar;index=0;state=0; curchar=' ' while(

39、curchar=' '|curchar='t') if (stacktop=-1) curchar=fgetc(in); else curchar=stackstacktop-; if (curchar=EOF) word0=EOF;word1='0' return FEOF; while (1) trywordindex=curchar; switch (state) case 0: switch (curchar) case 'A': case 'B': case 'C': case '

40、D': case 'E': case 'F': case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case

41、 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z': case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k'

42、: case 'l': case 'm': case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z':state=1;break;/1 case '0&

43、#39;: case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': state=2;break;/2 case '+': state=5;break; case '*': state=6;break; case '(': state=7;break; case ')'

44、: state=8;break; case ':': state=9;break; case '': state=11;break; case 'n': state=12;break; case '.': state=13;break; default: state=-1;break; ; break; case 1: switch (curchar) case 'A': case 'B': case 'C': case 'D': case 'E':

45、case 'F': case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case 'U': case 'V&

46、#39;: case 'W': case 'X': case 'Y': case 'Z': case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': case &

47、#39;m': case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x':/L case 'y': case 'z': case '0': case '1': case '2'

48、: case '3': case '4': case '5': case '6': case '7': case '8': case '9':/D state=1;break;/1 default: state=-1;break; ; break; case 2: switch (curchar) case '0': case '1': case '2': case '3': case '4': case

49、 '5': case '6': case '7': case '8': case '9':/D state=2;break; case '.': state=3;break; default: state=-1;break; ; break; case 3: switch (curchar) case '0': case '1': case '2': case '3': case '4': case '5'

50、;: case '6': case '7': case '8': case '9': state=4;break; default: state=-1;break; ; break; case 4: switch (curchar) case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case &#

51、39;8': case '9': state=4;break; default: state=-1;break; ; break; case 5: state=-1;break; case 6: state=-1;break; case 7: state=-1;break; case 8: state=-1;break; case 9: switch (curchar) case '=': state=10;break; default: state=-1;break; ; break; case 10: state=-1;break; case 11: state=-1;break; case 12: state=-1;break; case 13: state=-1;break; default: