编译原理课程设计报告2014.doc

1 课 程 设 计 报 告 课程名称课程名称 编译程序设计原理编译程序设计原理 课题名称课题名称 带括号的四则混合运算带括号的四则混合运算 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 学学 号号 姓姓 名名 指导教师指导教师 2014 年年 6 月月 19 日日 2 湖南工程学院湖南工程学院 课课 程程 设设 计计 任任 务务 书书 课程名称课程名称 编译程序设计原理编译程序设计原理 课课 题题 带括号的四则混合运算带括号的四则混合运算 专业班级专业班级 学生姓名学生姓名 学学 号号 指导老师指导老师 审审 批批 任务书下达日期 2014 年 6 月 16 日 任务完成日期 2014 年 6 月 19 日 2 2011 级 编译原理课程设计 任务书 一 课程设计的性质和目的 编译原理课程设计是计算机专业课程 通过课程设计使学生进一步巩固课堂所学知识 全面熟悉 掌握编译程序编写的基本设计方法和技巧 进一步提高分析问题 解决问题及 上机操作能力 为将来从事高层次的计算机软件开发工作打下一定的专业基础 二 设计课题 课题一 应用编译原理的方法实现带括号的四则混合运算 给定条件 1 词法符号定义如下 INTC D FLOATC D D D D FLOATC D D D D D E e D OPADD OPSUB OPMUL OPDIV LPAREN RPAREN LINE n ASSIGN 2 表达式文法定义如下 01 S E 02 E T 03 E E OPADD T 04 E E OPSUB T 05 T P 06 T T OPMUL P 07 T T OPDIV P 08 P INTC 09 P FLOATC 10 P LPAREN E RPAREN 基本要求 1 以 ASSIGN 作为文法结束符号 2 应用词法分析技术识别单词 3 应用 SLR 1 分析技术判别表达式的合法性 4 应用尾动作文法技术计算表达式的类型与值 5 要求表达式的类型与值严格一致 3 课题二 Micro 语言词法语法分析 给定条件 1 词法符号定义如下 ID L L D INTC D REALC D D PLUS MULT LPAREN RPAREN COLON ASSIGN SEMI LINE n STOP FEOF EOF 2 表达式文法定义如下 01 PROG BEGIN DECL BODY END STOP 02 DECL DECL VAR ID COLON TYPE SEMI 03 DECL VAR ID COLON TYPE SEMI 04 TYPE REAL 05 TYPE INTEGER 06 BODY BODY SEMI STM 07 BODY STM 08 STM ID ASSIGN EXP 09 STM WRITE LPAREN EXP RPAREN 10 STM READ LPAREN ID RPAREN 11 EXP EXP PLUS FACT 12 EXP FACT 13 FACT FACT MULT PRIM 14 FACT PRIM 15 PRIM ID 16 PRIM INTC 17 PRIM REALC 18 PRIM LPAREN EXP RPAREN 基本要求 1 以 FEOF 作为文法结束符号 2 应用词法分析技术识别单词 3 应用 SLR 1 分析方法进行语法分析 4 报错要指明所在行 4 三 课程设计报告要求 1 课程设计报告必须按本系规定的格式要求打印成册 2 课程设计报告每人一份 正文必须包含如下几个方面的内容 1 基本设计思想 2 主要数据结构 3 总结与体会 3 课程设计报告装订顺序 封面 任务书 目录 正文 源程序清单 四 选题及考核办法 1 一人一组 学号为奇数者做课题一 学号为偶数者做课题二 2 成绩考核按个人课题完成情况 设计报告质量及对课程设计的态度等综合评定 五 设计进度安排 1 讲课时间安排 19 周周五上午 2 上机调试时间安排 19 周周六周日上午 3 答辩时间安排 20 周周一上午 4 其余时间 查阅资料 确定方案 设计课题相关程序 5 目录 一 设计内容与设计要求 6 1 1 课程设计的性质和目的课程设计的性质和目的 6 1 2 设计课题设计课题 6 1 3 进度安排进度安排 7 二 基本设计思想 8 2 1 词法分析词法分析 8 2 2 语法分析语法分析 9 三 主要数据结构 14 四 调试运行结果 15 五 总结与体会 16 参考文献 17 6 一 设计内容与设计要求 1 11 1 课程设计的性质和目的课程设计的性质和目的 编译原理课程设计是计算机专业课程 通过课程设计使学生进一步巩固课堂所 学知识 全面熟悉 掌握编译程序编写的基本设计方法和技巧 进一步提高分析问 题 解决问题及上机操作能力 为将来从事高层次的计算机软件开发工作打下一定 的专业基础 1 21 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 n ASSIGN 2 表达式文法定义如下 01 S E 02 E T 03 E E OPADD T 04 E E OPSUB T 05 T P 06 T T OPMUL P 07 T T OPDIV P 08 P INTC 09 P FLOATC 10 P LPAREN E RPAREN 基本要求 1 以 ASSIGN 作为文法结束符号 2 应用词法分析技术识别单词 3 应用 SLR 1 分析技术判别表达式的合法性 4 应用尾动作文法技术计算表达式的类型与值 5 要求表达式的类型与值严格一致 7 1 31 3 进度安排进度安排 计算机计算机 0701 0702 班 班 第 18 周 星期五 8 00 12 00 星期六 8 00 12 00 第 19 周 星期天 8 00 12 00 计算机计算机 0703 班 班 第 18 周 星期五 14 00 18 00 星期六 14 00 18 00 第 19 周 星期天 14 00 18 00 8 二二 基本设计思想基本设计思想 本计算器采用编译原理的方法构建 先用有穷自动机辅助进行词法 把字符串 形式的算术表达式的格式标准化 分离出一个个词法单元 然后采用 SLR 1 文法分 析法进行文法分析 检查表达式的正确性 并在过程中计算出已分析出的部分表达 式的值 最终得出表达式的值 2 12 1 词法分析词法分析 由于各词法元素都可以用正则表达式来表示 所以做词法分析时采用正则表达 式形式化表示各个元素以便于程序实现 四则混合运算各词法元素的正则表达式如下所示 INTC D FLOATC D D D D FLOATC D D D D D E e D OPADD OPSUB OPMUL OPDIV LPAREN RPAREN LINE n ASSIGN 正则表达式把能够把各词法元素的格式用形式化的方法表示出来 是格式的判 断能够用程序来完成 但最终写程序时 用正则表达式直接分析对人来说仍然是不 太直接 不方便 所以把正则表达式转化为有限自动机 以是写程序实现词法分析 方便 如图 1 1 为四则混合运算的有限自动机 9 图 2 1 四则混合运算的有限自动机 2 22 2 语法分析语法分析 四则混合运算算术表达式符合 SLR 1 文法但不符合 LR 0 文法 所以语法分析 采用 SLR 1 语法分析方法 四则混合运算算术表达式的产生式如下 12 0 D 1 D D2 E e 46 D D 7 8 11 INTC FLOATC OPADD OPMUL OPDIV LINE ASSIGN 3 D E e 5 D FLOATC 9 10 13 n 14 OPSUB RPAREN LPAREN 10 01 S E 02 E T 03 E E OPADD T 04 E E OPSUB T 05 T P 06 T T OPMUL P 07 T T OPDIV P 08 P INTC 09 P FLOATC 10 P LPAREN E RPAREN 通过文法的产生式可以把四则混合运算算术表达式的文法中各个非终极符的 FIRST 集合和 FOLLOW 集合一一求出来 以便进行下一步分析 其FIRST 集和 FOLLOW 集如表 1 1 所示 表 2 1 四则混合运算算术表达式文法中非终极符的 FIRST 集和 FOLLOW 集 符号FIRST 集合FOLLOW 集合 SINTC FLOATC LPAREN ASSIGN EINTC FLOATC LPARENASSIGN OPADD OPSUB RPAREN TINTC FLOATC LPARENASSIGN OPADD OPSUB RPAREN OPMUL OPDIV PINTC FLOATC LPARENASSIGN OPADD OPSUB RPAREN OPMUL OPDIV 根据文法的产生式和 FIRST 集 FOLLOW 集即可确定文法的规约活前缀 DFA SLR 1 DFA 如图 1 2 所示 1 0 S E E T E E OPADD T E E OPSUB T T P T T OPMUL P T T OPDIV P P INTC P FLOATC P LPAREN E RPAREN E S1 TS2 PS3 INTCS4 FLOATCS5 LPARENS6 1 S E E E OPADD T E E OPSUB T ASSIGNR1 OPADDS7 OPSUBS8 2 E T T T OPMUL P T T OPDIV P ASSIGNR2 OPADDR2 OPSUBR2 RPARENR2 OPMULS9 OPDIVS10 4 P INTC ASSIGNR8 OPADDR8 OPSUBR8 RPARENR8 OPMULR8 OPDIVR8 3 T P ASSIGNR5 OPADDR5 OPSUBR5 RPARENR5 OPMULR5 OPDIVR5 5 P FLOATC ASSIGNR9 OPADDR9 OPSUBR9 RPARENR9 OPMULR9 OPDIVR9 6 P LPAREN E RPAREN E T E E OPADD T E E OPSUB T T P T T OPMUL P T T OPDIV P P INTC P FLOATC P LPAREN E RPAREN E S11 TS2 PS3 INTCS4 FLOATCS5 LPARENS6 7 E E OPADD T T P T T OPMUL P T T OPDIV P P INTC P FLOATC P LPAREN E RPAREN TS12 PS3 INTCS4 FLOATCS5 LPARENS6 3 图 2 2 SLR 1 DFA 9 T T OPMUL P P INTC P FLOATC P LPAREN E RPAREN PS14 INTCS4 FLOATCS5 LPARENS6 11 P LPAREN E RPAREN E E OPADD T E E OPSUB T RPARENS16 OPADDS7 OPSUBS8 10 T T OPDIV P P INTC P FLOATC P LPAREN E RPAREN PS15 INTCS4 FLOATCS5 LPARENS6 12 E E OPADD T T T OPMUL P T T OPDIV P ASSIGNR3 OPADDR3 OPSUBR3 RPARENR3 OPMULS9 OPDIVS10 8 E E OPSUB T T P T T OPMUL P T T OPDIV P P INTC P FLOATC P LPAREN E RPAREN TS13 PS3 INTCS4 FLOATCS5 LPARENS6 13 E E OPSUB T T T OPMUL P T T OPDIV P ASSIGNR4 OPADDR4 OPSUBR4 RPARENR4 OPMULS9 OPDIVS10 14 T T OPMUL P ASSIGNR6 OPADDR6 OPSUBR6 RPARENR6 OPMULR6 OPDIVR6 15 T T OPDIV P ASSIGNR7 OPADDR7 OPSUBR7 RPARENR7 OPMULR7 OPDIVR7 16 P LPAREN E RPAREN ASSIGNR10 OPADDR10 OPSUBR10 RPARENR10 OPMULR10 OPDIVR10 4 根据 SLR 1 DFA 即可用构造文法的相应 action 表和 goto 表如表 1 3 和表 1 3 所示 表 2 2 SLR 1 action INTCFLOATCOPAD D OPSUBOPMU L OPDIVLPARENRPARENASSIG N 0S4S5S3 1S7S8R1 2R2R2R2R2 3R5R5R5R5R5R5 4R8R8R8R8R8R8 5R9R9R9R9R9R9 6S4S5S6 7S4S5S6 8S4S5S6 9S4S5S6 10S4S5S6 11S7S8S16 12R3R3S9S10R3R3 13R4R4S9S10R4R4 14R6R6R6R6R6R6 15R7R7R7R7R7R7 16R10R10R10R10R10R10 表 2 3 SLR 1 goto ETP 0123 1 2 3 4 5 61123 7123 8133 914 1015 11 12 13 有了文法的 action 表和 goto 表 就可以根据表中所指示的状态转移情况 编写程序并 完成相应功能 5 三三 主要数据结构主要数据结构 程序的主要数据结构为栈 1 词法分析中用一个栈来保存分析中到达的状态 static char lexstack BUFSIZE 2 语法分析中一个状态栈用来保存已到达的状态 一个符号栈用来保存已读入的符号 或规约产生的符号中还没被规约掉的语法符号 struct int state TokenType token stack BUFSIZE 由于状态栈 与符号栈的出入栈是同步的所以两个栈写在同一个结构中 当读入一个字符或前一个规约产生一个符号 之后若不能直接规约这将该符号入栈到 token 并跳转到新的状态 原状态入栈 state 当一个活前缀被规约 被规约符号出栈 相应 状态也出栈 6 四 调试运行结果 正确的输入结果 得到值 40 7 五 总结与体会 编译原理这门学科对于我来说算是比较难懂的了 对于自己在过去一周的课程设 计中 我学到了不少的东西 当然是通过和同学交流讨论所学习到的 虽然不是很精通 但是多少还是了解了一点皮毛 对于老师给我们的那段代码 我还是自己很好的看了一 下 对于程序的某些部分还是不怎么熟悉 所以在自己编译和调试过程中出现了不少的 问题和错误 虽然这样 本次的课程设计还是让我受益匪浅的 因为它极大的提升了我的编程能 力和对程序的阅读理解能力 这样也使我对编译原理中的词法分析和语法分析部分比较 深刻的了解和熟悉 真的 通过此次课程设计我学到了很多东西 当然自己还有许多不足的地方需要 以后进一步的提高 这对我今后不管是学习还是生活都会很有帮助 当然我也深刻的 认识到了写代码必须要有比较过硬的理论基础作为铺垫才能编写出好的程序 如果不 熟练的掌握它们 很难写出高水平的代码 这样就不能很好的提高自己和锻炼自己 而这恰恰是我现在所缺乏的一种能力 希望以后很好的提升自己这方面的能力 在整 个课程设计过程中多亏老师耐心的指导 否则我也很难完成任务 在这里我要感谢老 师的悉心指导 这才让我能够很好的调试好代码 当然除了老师的帮助外还有许多热 心的同学 他们同样是我的榜样 是他们给我的意见和见解 让我的程序能够更加完 善 嗯 这些都是我的一点小小的体会 希望我们的指导老师周铁山老师身体健康 工作顺利 希望自己以后在学习中更上一层楼 8 参考文献 1 金成植 金英 编译程序设计原理 M 北京 高等教育出版社 2007 2 胡元义 柯丽芳 编译原理学习指导 M 西安电子科技大学出版社 2004 3 陈意云 张昱 编译原理实验教程 M 北京 高等教育出版社 2009 4 美 Andrew W Appel 美 Maia Ginsburg 编译原理 C 语言描述 北京 人民邮电出版社 2006 9 附录 源程序 include include include define BUFSIZE 256 static FILE in static FILE out typedef enum NONE 3 FEOF ERROR INTC FLOATC OPADD OPSUB OPMUL OPDIV LPAREN RPAREN LINE ASSIGN S E T P 文法的非终极符 11 13 LexType define Macro caseD 0 case 1 case 2 case 3 case 4 case 5 case 6 case 7 case 8 case 9 LexType lex char word static int lexstacktop 1 static char lextryword BUFSIZE static char lexstack BUFSIZE static LexType lextryflag BUFSIZE static char lexcurch static LexType lexstateflag ERROR INTC FLOATC ERROR ERROR ERROR FLOATC OPADD OPSUB OPMUL OPDIV LPAREN RPAREN LINE ASSIGN int state 0 int lexindex 0 do if lexstacktop 1 lexcurch fgetc in else lexcurch lexstack lexstacktop while lexcurch lexcurch t while 1 switch state case 0 switch lexcurch case Macro caseD state 1 break case state 3 break case state 7 break case state 8 break case state 9 break case state 10 break case state 11 break case state 12 break case n state 13 break case state 14 break default state 1 break break case 1 switch lexcurch case Macro caseD state 1 break 10 case state 2 break case E case e state 4 break default state 1 break break case 2 switch lexcurch case Macro caseD state 2 break case E case e state 4 break default state 1 break break case 3 switch lexcurch case Macro caseD state 2 break default state 1 break break case 4 switch lexcurch case Macro caseD state 6 break case case state 5 break default state 1 break break case 5 switch lexcurch case Macro caseD state 6 break default state 1 break break case 6 switch lexcurch case Macro caseD state 6 break default state 1 break break default state 1 break if state 1 break lextryword lexindex lexcurch maybe overflow lextryflag lexindex 1 lexstateflag state if lexstacktop 1 lexcurch fgetc in else lexcurch lexstack lexstacktop if lexindex 0 lextryword lexindex lexcurch lextryflag lexindex ERROR while lexindex 0 maybe overflow lextryword lexindex 1 0 strcpy word lextryword return lextryflag lexindex static int lineno 1 typedef struct 11 LexType type enum INT FLOAT valuetype union int intv float floatv value TokenType static TokenType curtoken buftoken NONE void getnexttoken char word if buftoken type NONE do curtoken type lex word if curtoken type INTC curtoken valuetype INT curtoken value intv atoi word if curtoken type FLOATC curtoken valuetype FLOAT curtoken value floatv atof word if curtoken type ERROR fprintf out Error line d s n lineno word if curtoken type LINE lineno while curtoken type ERROR curtoken type LINE else memcpy buftoken type NONE define ERRORPROCESS fprintf out pError line d n lineno return define shift num memcpy stack top state num getnexttoken word define Macro caseAASR ASSIGN case OPADD case OPSUB case RPAREN define Macro caseAASRMD Macro caseAASR case OPMUL case OPDIV define Macro NextcaseMDto9 10AndOther case OPMUL shift 9 break case OPDIV shift 10 break define Macro NextcaseIFLto456AndOther case INTC shift 4 break case FLOATC shift 5 break case LPAREN shift 6 break default ERRORPROCESS define Macro chhgInETPgoto State memcpy memcpy curtoken type State void parse void struct int state TokenType token stack BUFSIZE int top 0 char word 80 float ta tb 12 stack top state 0 getnexttoken word while 1 switch stack top state case 0 switch curtoken type case E shift 1 break case T shift 2 break case P shift 3 break Macro NextcaseIFLto456AndOther break case 1 switch curtoken type case ASSIGN R1 Macro chhgInETPgoto S if curtoken valuetype INT ACCEPT fprintf out d n curtoken value intv if curtoken valuetype FLOAT fprintf out f n curtoken value floatv return case OPADD shift 7 break case OPSUB shift 8 break default ERRORPROCESS break case 2 switch curtoken type case Macro caseAASR R2 Macro chhgInETPgoto E break Macro NextcaseMDto9 10AndOther break case 3 switch curtoken type case Macro caseAASRMD Macro chhgInETPgoto T break default ERRORPROCESS break case 4 switch curtoken type case Macro caseAASRMD Macro chhgInETPgoto P break default ERRORPROCESS break case 5 switch curtoken type case Macro caseAASRMD Macro chhgInETPgoto P break default ERRORPROCESS break 13 case 6 switch curtoken type case E shift 11 break case T shift 2 break case P shift 3 break Macro NextcaseIFLto456AndOther break case 7 switch curtoken type case T shift 12 break case P shift 3 break Macro NextcaseIFLto456AndOther break case 8 switch curtoken type case T shift 13 break case P shift 3 break Macro NextcaseIFLto456AndOther break case 9 switch curtoken type case P shift 14 break Macro NextcaseIFLto456AndOther break case 10 switch curtoken type case P shift 15 break Macro NextcaseIFLto456AndOther break case 11 switch curtoken type case RPAREN shift 16 break case OPADD shift 7 break case OPSUB shift 8 break default ERRORPROCESS break case 12 switch curtoken type case Macro caseAASR R3 memcpy if stack top 3 token valuetype INT curtoken value intv stack top 3 token value intv stack top 1 token value intv else curtoken valuetype FLOAT if stack top 3 token valuetype INT ta float stack top 3 token value intv else ta stack top 3 token value floatv if stack top 1 token valuetype INT tb float stack top 1 token value intv else tb stack top 1 token value floatv curtoken value floatv ta tb 14 curtoken type E top top 3 break Macro NextcaseMDto9 10AndOther break case 13 switch curtoken type case Macro caseAASR R4 memcpy curtoken type E if stack top 3 token valuetype INT curtoken value intv stack top 3 token value intv stack top 1 token value intv else if stack top 3 token valuetype INT ta float stack top 3 token value intv else ta stack top 3 token value floatv if stack top 1 token valuetype INT tb float stack top 1 token value intv else tb stack top 1 token value floatv curtoken value floatv ta tb top top 3 break Macro NextcaseMDto9 1