编译原理2013年6月18日222341.doc

课 程 设 计 报 告课程名称 编译原理 课题名称 Micro语言词法语法分析 专 业 计算机科学与技术 班 级 1 学 号 2010130301 姓 名 波子汽水 指导教师 周铁山 年 月 日 2010级编译原理课程设计任务书一、 课程设计的性质和目的编译原理课程设计是计算机专业课程，通过课程设计使学生进一步巩固课堂所学知识，全面熟悉、掌握编译程序编写的基本设计方法和技巧，进一步提高分析问题、解决问题及上机操作能力，为将来从事高层次的计算机软件开发工作打下一定的专业基础。二、 设计课题课题一：应用编译原理的方法实现带括号的四则混合运算 给定条件：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 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、 要求表达式的类型与值严格一致。课题二：Micro语言词法语法分析 给定条件：1、 词法符号定义如下：ID L(L|D)*INTC D+REALC D+ D+PLUS +MULT *LPAREN (RPAREN )COLON ：ASSIGN ：SEMI ；LINE nSTOP FEOF EOF2、 表达式文法定义如下：01. PROGBEGIN DECL BODY END STOP02. DECLDECL VAR ID COLON TYPE SEMI03. DECLVAR ID COLON TYPE SEMI04. TYPEREAL 05. TYPEINTEGER 06. BODYBODY SEMI STM07. BODYSTM08. STMID ASSIGN EXP09. STMWRITE LPAREN EXP RPAREN10. STMREAD LPAREN ID RPAREN11. EXPEXP PLUS FACT12. EXPFACT13. FACTFACT MULT PRIM14. FACTPRIM15. PRIMID16. PRIMINTC17. PRIMREALC18. PRIMLPAREN EXP RPAREN基本要求：1、 以FEOF作为文法结束符号； 2、 应用词法分析技术识别单词； 3、 应用SLR(1)分析方法进行语法分析；4、 报错要指明所在行。三、 课程设计报告要求1、 课程设计报告必须按本系规定的格式要求打印成册；2、 课程设计报告每人一份，正文必须包含如下几个方面的内容：1) 基本设计思想；2) 主要数据结构；3) 总结与体会。3、 课程设计报告装订顺序：封面、任务书、目录、正文、源程序清单。四、 选题及考核办法1、 一人一组，学号为奇数者做课题一，学号为偶数者做课题二。2、 成绩考核按个人课题完成情况、设计报告质量及对课程设计的态度等综合评定。五、设计进度安排1、 讲课时间安排：待定2、 上机调试时间安排：第十八周、周二、周三、周四 上午 E 6013、 答辩时间安排：待定4、 其余时间：查阅资料，确定方案，设计课题相关程序。22目 录一、 基本设计思想3二、 主要数据结构4三、 系统调试5四、总结与体会8五、附件 ：源程序清单9一、 基本设计思想本课程设计的主要任务为词法分析和语法分析，词法分析主要任务是输入单词、拼单词、分析单词，并转换为内部表达形式通常称为机内码，为下一步语法分析做准备。 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述具体操作位一是进行词法分析部分，二是进行语法分析部分。构造编译器可以首先对源代码进行词法分析输出含token序列的中间文件，然后作为语法分析的输入，但是这样得两次读取文件，并且需要增加额外的内存开销，因此这里采用一次读取文件，在有这个当前的一个token时，经过词法分析得到一个token即可进行语法分析，这样以后就是词法分析得到一个token后就进行语法分析，程序更加简练。在两个大模块中需要频繁的使用到关键字，词法分析符号，文法非终极符等常量，因此这些常量都定义在全局变量里。（1） 词法分析词法分析部分是通过构造有穷自动机来实现的。 对自动机的每一个状态，都设置状态标志，这样就能够实时查看词法分析进入的状态。词法分析的状态机图在课题中已经给出。在词法分析中需要对分析出的标识符进行是否是保留字的判断，保留字和词法分析的各状态标志都定义在全局变量中。（2） 语法分析语法分析部分是用SLR(1)方法进行语法分析，该方法不显示的使用符号栈，而是使用状态栈，SLR(1)方法的核心是构造action表和goto表，这里使用了action图来表示，在课题中已经画出了各个状态接收token后的动作，因此程序中只需要进行相应的添加即可。SLR(1)语法分析方法的主要动作有两个，一是进行移入操作（shift)，而是进行规约（reduce）动作，鉴于这两个动作的代码较少，而且使用频率高，因此程序中使用了宏定义的形式。使用SLR(1)方法需要求出非终极符的Follow集合，而求解follow集需要使用到first集合，这里在课题中已经给出了各非终极符的first集合follow集，进而就可以确定规约所需要的产生式编号。该编译程序对出错的信息进行了行输出，指出了出错的行，对出错行的处理事单独进行的。二、 主要数据结构在词法分析部分使用了堆栈lexstack来记录出现的错误的字符，用枚举类型来定义频繁使用的关键字，文法非终极符等常量。在本程序中没有使用递归的方法来进行词法分析，这里使用了while循环和switch语句相结合的方式，有效的提高了词法分析的效率。在语法分析部分，使用了状态栈state来保存语法分析进入的各个状态，对于每一个状态的可能的两种动作，采用了宏定义的形式来定义移入动作（SHIFT)和规约动作（REDUCE)。这里显示的使用了状态栈，不显示的使用符号栈，在进行规约动作中需要指出文法产生式左部的非终极符和该产生式右部的文法符号的个数。规约的动作可以是一个递归的过程，这里也是使用了while循环和switch语句相结合的方式来对当前的token和预读入的token进行相应的处理。该程序的主要的函数及其功能如下：int main(int argc,char *argv)函数:如果在命令行中运行本程序的话，需要带上相应的参数，其中第一个参数即为该程序可执行文件的名称，第二个参数为要进行编译处理的源程序的文件名，第三个参数为经过该程序处理后错误信息的输出文件名（可以没有该参数）。LexType lex(char *word)函数：该函数主要是进行词法分析，通过调用该函数即可得到一个token，该token的值保存在参数word中。void getnexttoken(char *word)函数：该函数也是获取一个token，它是通过调用lex函数来实现获取一个token的。 void parse(void)函数：该函数主要是语法分析的部分，通过语法分析即可得出相应的分析结果。 各函数的调用关系是main函数调用parse函数，parse函数调用getnexttoken函数，而getnextttoken函数则调用词法分析函数lex;三、 系统调试本程序的调试与测试，是通过构造一个语法树，得到一个确定的句子，然后对该句子作为源程序输入进行测试。这里主要测试了两个测试例子，分别如下：第一个测试使用的是maobo.txt文件中的源程序，其中的语法树、测试代码和结果下图所示： 图一：maobo.txt源代码的语法树图 图二:maobo.txt文件源代码及测试结果 因为最后一行少了个 . 所以报错在第四行。这里需要注意read(x)后面没有分号，这是由产生式决定的，通过语法树很容易看出。 下面是maobo2.txt文件中的源代码的语法树、测试代码及结果： INTCPRIMIDPRIMFACTFACTPLUSEXPTYPECOLONIDREALINTEGERIDEXPASSIGNRPARENIDLPARENREADSTMSEMISTMSEMITYPECOLONBODYSEMIIDVARDECLVARSTOPENDBODYDECLBEGINPROG 图三：maobo.txt文件源代码的语法树 图四：maobo2.txt文件的源程序即测试结果 这里同样需要注意赋值语句x:=y+5的后面也没有分号，该源程序的语法树如上面的图三所示，从语法树的图中可以很容易的看出合格的源程序的格式。 在调试的过程中，首先需要构造出语法树，然后根据语法树得到相应的句子，这样在调试的过程中若出现错误就只可能是代码编写的错误，而不会是输入的源程序的错误。盲目的测试调试最终只会越调越乱。四、总结与体会 本次课程设计做起来挺有难度的，好久没写过C和C+程序语言，有些生疏了，本来基础就不怎么好的，要写这个编译器还真有挑战性，不过幸好有万能的百度，在文库里面找到了一个学长做过的这个课题的报告，经过好几天的认真研究和分析终于看懂了，再稍加改进，勉强完成本次课程设计。本次课程设计让我感受到了，书本上写的和实际上操作起来还是有一定差距的，编译原理这门课我是有认认真真学的，考试之前花了好几个星期研究了first集和follow集，学会了画语法分析树和消除左递归以及自动机的化简转换。做课程设计感觉还是有难度的，这么一个看似庞大的系统设计起来很费时间。自认为考试考得还可以应该难度不大，可是我错了，很惭愧的参考了很多往届学姐学长们的精华，才勉强完成本次课程设计。作为一个计算机系的学生深深地感到惭愧！最后还是要感谢帮助我支持我的老师和同学们！衷心感谢！五、附件 ：源程序清单#include #include #define LexTypeNum 30#define ReserveNum 7#define BUFSIZE 256#define SHIFT(NUM) state+top=NUM;getnexttoken(word);break;/移入操作#define REDUCE(SYM,NUM) top=top-NUM;buftoken=curtoken;curtoken=SYM;break;/规约操作#define ERRORPROCESS fprintf(out,Error line:%dn,lineno);return;typedef enum NONE=-3, FEOF, ERROR, /*关键字*/ 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, FACT, PRIM LexType;static char *lexreserve=begin,end,var,read,write,integer,real;/保留字static LexType lexstateflag=ERROR,ID,INTC,ERROR,REALC,PLUS,MULT,/对每一个状态设置一个状态标志 LPAREN,RPAREN,COLON,ASSIGN,SEMI,LINE,STOP;static FILE *in; /源程序文件static FILE *out; /static char lexcurch= ;static char lexstackBUFSIZE;/词法分析栈static int lexstacktop=-1; /词法分析栈顶指针static char lextrywordBUFSIZE; static LexType lextryflagBUFSIZE;static int lexindex;/*实现语法分析时使用的变量*/static LexType curtoken;static LexType buftoken=NONE;static int lineno=1;LexType lex(char *word) int state; lexindex=0; state=0; while(lexcurch= |lexcurch=t) if (lexstacktop=-1) lexcurch=fgetc(in); else lexcurch=lexstacklexstacktop-; while (1) if (lexindex) lextryflaglexindex-1=lexstateflagstate; switch (state) case 0: switch (lexcurch) 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 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: 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 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; case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state=2;break; case +: state=5;break; case *: state=6;break; case (: state=7;break; case ): 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(lexcurch) 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 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: 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 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: case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state=1;break; default: state=-1;break; ; break; case 2: switch(lexcurch) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state=2;break; case .: state=3;break;default: state=-1;break; ; break; case 3: switch(lexcurch) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state=4;break;default: state=-1;break; ; break; case 4: switch(lexcurch) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state=4;break;default: state=-1;break; ; break; case 5: case 6: case 7: case 8: state=-1; break;case 9: switch(lexcurch) case =: state=10; break; default: state=-1;break; ; break;case 10:case 11:case 12:case 13: state=-1; break; default: state=-1;break; if (state=-1) break; lextrywordlexindex+=lexcurch;/*maybe overflow*/ if (lexstacktop=-1) lexcurch=fgetc(in); else lexcurch=lexstacklexstacktop-; if (lexindex=0&lexcurch=EOF) return FEOF; lextrywordlexindex=lexcurch; lextryflaglexindex=ERROR; while (lexindex0 & lextryflaglexindex=ERROR) lexstack+lexstacktop=lextrywordlexindex-;/*maybe overflow*/ lextrywordlexindex+1=0; strcpy(word,lextryword); if (lexstacktop=-1) lexcurch=fgetc(in); else lexcurch=lexstacklexstacktop-; if (lextryflaglexindex=ID) for (state=0;stateReserveNum;state+) if (!strcmp(word,lexreservestate) return (LexType)state; return lextryflaglexindex;void getnexttoken(char *word) if (buftoken=NONE) do curtoken=lex(word); if (curtoken=ERROR) fprintf(out,Error line:%d %sn,lineno,word); if (curtoken=LINE) lineno+; while(curtoken=ERROR|curtoken=LINE); else curtoken=buftoken; buftoken=NONE; void parse(void) int stateBUFSIZE; int top=-1; char word80; state+top=0; getnexttoken(word); while (1) switch(statetop) /* need code here */ case 0: switch(curtoken) case BEGIN: SHIFT(1); default: ERRORPROCESS ; break; case 1: switch(curtoken) case DECL:SHIFT(2); case VAR:SHIFT(3); default: ERRORPROCESS ; break; case 2: switch(curtoken) case BODY:SHIFT(4); case VAR: SHIFT(5); case STM:SHIFT(6); case ID:SHIFT(7); case WRITE:SHIFT(8); case READ:SHIFT(9); default: ERRORPROCESS ; break; case 3: switch(curtoken) case ID:SHIFT(10); default: ERRORPROCESS ; break; case 4: switch(curtoken) case END:SHIFT(11); case SEMI:SHIFT(12); default: ERRORPROCESS ; break; case 5: switch(curtoken) case ID:SHIFT(13); default: ERRORPROCESS ; break; case 6: switch(curtoken) case SEMI: case END:REDUCE(BODY,1);break; default: ERRORPROCESS ; break; case 7: switch(curtoken) case ASSIGN:SHIFT(14); default: ERRORPROCESS ; break; case 8: switch(curtoken) case LPAREN:SHIFT(15); default: ERRORPROCESS ; break; case 9: switch(curtoken) case LPAREN:SHIFT(16); default: ERRORPROCESS ; break; case 10: switch(curtoken) case COLON:SHIFT(17); default: ERRORPROCESS ; break; case 11: switch(curtoken) case STOP:SHIFT(18); default: ERRORPROCESS ; break; case 12: switch(curtoken) case ID:SHIFT(7); case WRITE:SHIFT(8); case READ:SHIFT(9); case STM:SHIFT(19); default: ERRORPROCESS ; break; case 13: switch(curtoken) case COLON:SHIFT(20); default: ERRORPROCESS ; break; case 14: switch(curtoken) case EXP:SHIFT(21); case FACT:SHIFT(22); case PRIM:SHIFT(23); case ID:SHIFT(24); case INTC:SHIFT(25); case REALC:SHIFT(26); case LPAREN:SHIFT(27); default: ERRORPROCESS ; break; case 15: switch(curtoken) case FACT:SHIFT(22); case PRIM:SHIFT(23); case ID:SHIFT(24); case INTC:SHIFT(25); case REALC:SHIFT(26); case LPAREN:SHIFT(27); case EXP:SHIFT(28); default: ERRORPROCESS ; break; case 16: switch(curtoken) case ID:SHIFT(29); default: ERRORPROCESS ; break;case 17: switch(curtoken) case TYPE:SHIFT(30); case REAL:SHIFT(31); case INTEGER:SHIFT(32); default: ERRORPROCESS ; break; case 18: switch(curtoken) case FEOF: /* ACCEPT R1 */ fprintf(out, successful!n); return; default: ERRORPROCESS break; /* need code here */ case 19: switch(curtoken) case SEMI: case END:REDUCE(BODY,3); default: ERRORPROCESS ; break;case 20: switch(curtoken) case REAL:SHIFT(31); case INTEGER:SHIFT(32); case TYPE:SHIFT(33); default: ERRORPROCESS ; break; case 21: switch(curtoken) case PLUS: SHIFT(34); case SEMI: case END: REDUCE(STM,3) /* R8 */ default: ERRORPROCESS break; /* need code here */ case 22: switch(curtoken) case MULT:SHIFT(35); case PLUS: case RPAREN: case SEMI: case END:REDUCE(EXP,1); default: ERRORPROCESS ; break;case 23: switch(curtoken) case PLUS: case MULT: case RPAREN: case SEMI: case END:REDUCE(FACT,1); default: ERRORPROCESS ; break;case 24: switch(curtoken) case PLUS: case MULT: case RPAREN: case SEMI: case END:REDUCE(PRIM,1); default: ERRORPROCESS ; break;case 25: switch(curtoken) case PLUS: case MULT: case RPAREN: case SEMI: case END:REDUCE(PRIM,1); default: ERRORPROCESS ; break;case 26: switch(curtoken) case PLUS: case MULT: case RPAREN: case SEMI: case END:REDUCE(PRIM,1); default: ERRORPROCESS ; break;case 27: switch(curtoken) case FACT:SHIFT(22); case PRIM:SHIFT(23); case ID:SHIFT(24); case INTC:SHIFT(25); case REALC:SHIFT(26); case LPAREN:SHIFT(27); case EXP:SHIFT(36); default: ERRORPROCESS ; break;case 28: switch(curtoken) case PLUS:SHIFT(34); case RPAREN:SHIFT(37); default: ERRORPROCESS ; break;case 29: switch(curtoken) case RPAREN:SHIFT(38); default: ERRORPROCESS ;