带括号的四则混合运算编译原理课程设计报告

1 课 程 设 计 报 告 课程名称课程名称 编译程序设计原理编译程序设计原理 课题名称课题名称 带括号的四则混合运算带括号的四则混合运算 专专 业业 班班 级级 学学 号号 姓姓 名名 指导教师指导教师 2014 年年 6 月月 27 日日 2 湖南工程学院湖南工程学院 课课 程程 设设 计计 任任 务务 书书 课程名称课程名称 编译程序设计原理编译程序设计原理 课课 题题 带括号的四则混合运算带括号的四则混合运算 专业班级专业班级 学生姓名学生姓名 学学 号号 指导老师指导老师 审审 批批 任务书下达日期 2014 年 6 月 23 日 任务完成日期 2014 年 6 月 27 日 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 三 课程设计报告要求 1 课程设计报告必须按本系规定的格式要求打印成册 2 课程设计报告每人一份 正文必须包含如下几个方面的内容 1 基本设计思想 2 主要数据结构 3 总结与体会 3 课程设计报告装订顺序 封面 任务书 目录 正文 源程序清单 四 选题及考核办法 1 一人一组 学号为奇数者做课题一 学号为偶数者做课题二 2 成绩考核按个人课题完成情况 设计报告质量及对课程设计的态度等综合评定 五 设计进度安排 1 讲课时间安排 18 周周一上午 2 上机调试时间安排 18 周周三周四上午 3 答辩时间安排 18 周周五上午 4 其余时间 查阅资料 确定方案 设计课题相关程序 4 目录 一一 设计内容与设计要求设计内容与设计要求 6 1 1 课程设计的性质和目的 6 1 2 设计课题 6 1 3 进度安排 7 二二 基本设计思想基本设计思想 8 2 1 词法分析 8 2 2 语法分析 9 三三 主要数据结构主要数据结构 14 四四 调试运行结果调试运行结果 15 五五 总结与体会总结与体会 16 5 一 设计内容与设计要求 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 要求表达式的类型与值严格一致 6 1 31 3 进度安排进度安排 计算机计算机 1181 班 班 第 18 周 星期一 8 00 12 00 2 30 5 30 星期二 8 00 12 00 2 30 5 30 7 二二 基本设计思想基本设计思想 本计算器采用编译原理的方法构建 先用有穷自动机辅助进行词法 把字符串 形式的算术表达式的格式标准化 分离出一个个词法单元 然后采用 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 为四则混合运算的有限自动机 8 图 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 9 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 四 调试运行结果 正确的输入结果 得到值 35 7 五 总结与体会 这次课程设计的过程我遇到了很多的困难 不过有足够的时间给我看书和查资料 从这次课程设计的过程我也看到了自己学习的理论知识的不足 通过这次课程设计我 对于编译原理有了更加深入的了解 也懂得了构造一种语言的编译器所要考虑的过程 还有锻炼了我看别人写的大型的程序的能力 进一步加强了我写程序和读程序的能力 这次实验用是 C 语言 对此并不熟练 所以在修改的过程中遇到了一些比较 难的问题 但在老师与同学们的讨论后才得以解决 同时 也就此机会熟悉和回忆了 了 C 语言 为今后进行 C 设计积累了不少的经验 这次实验我做了五个内容 其中在增加一些语句的时候遇到的困难比较大 不过 通过查资料和与同学讨论我最后解决了这个问题 也学到了很多的东西 在这次实验 中充分理解了团结就是力量 在编译程序实现的过程中反复使用了递归调用的思想 且也使用了模块化处理问 题的思想 使用模块化的思想关键是在抽象阶段要抽象出对应的模块 且模块的层次 必须是清晰的 在实现此程序中 由于要实现关键字和符号表中字段的搜索 实现中 就必须注意快速查找的方法 而在实现的过程中多次用到了二分搜索的方法 这是个 比较快的搜索方法 由于此程序的实现相对比较复杂 且不方便调试 改进时可以把此程序的词法分 析 语法分析和执行原代码作为单独的测试程序来测试 这样也方便大家来调试 通过本次的课设我知道了一个算法的设计是需要静下心来仔细的研究的 且实现 中必须先了解程序的整个流程 也就是说在编程中首先必须看懂那些对应的 UML 图 只有在图的指导下 编程中才不会盲目 也有一定的方向性 同样在编程中必须注意 代码的规范 多写一些对应的注释是很必要的 要时刻想这代码并不是给你自己看的 而是必须要给别人看 因此我觉得代码的规范是相当重要的 8 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 10AndOther break case 14 switch curtoken type case Macro caseAASRMD R6 me