《编译原理课程设计》由会员分享,可在线阅读,更多相关《编译原理课程设计(34页珍藏版)》请在金锄头文库上搜索。
1、编译原理课程设计翟玉庆、周晓宇1、课程主要目的加深对编译原理及编译程序构造过程的理解增强程序设计能力学会编写工具软件2、课程主要实施方式分组完成项目每组三人分阶段提交项目结果小组交流所用程序设计语言不限3、项目基本内容通过自己所设计的工具生成C Subset或Cminus的词法和语法分析器通过你所设计的词法分析程序工具SeuLex生成C Subset或Cminus的词法分析器和语法分析程序生成工具SeuYacc生成C Subset或Cminus的语法分析器3、主要项目SeuLexLex输入文件的解析正规表达式的解析一个正规表达式到NFA的转换算法实现多个NFA的合并NFA的确定化和最小化算法实
2、现返回状态与返回内容的对应SeuLex应用3、主要项目SeuYaccYacc输入文件的解析上下文无关文法到对应LR(1)文法的下推自动机的构造LR(1)文法的下推自动机到相应分析表的构造LR(1)总控程序的构造(查表程序)LR(1)到LALR(1)的映射符号表的构建与相应管理程序语义动作程序的加入SeuYacc的应用4、主要进程安排第12周周五交SeuLex第14周周五交SeuYacc第14、15周末小组交流5、提交文档要求项目报告(要求打印)项目主要内容和分工协作情况项目涉及的主要数据结构定义项目涉及的主要算法流程描述项目实施过程中存在的主要问题及其解决方法项目实施过程中的主要收获包含项目讲
3、解PPT文件及可演示的项目程序和源程序的光盘(每个班一张,每个小组一个目录)6、成绩评定方式完成全部要求,文档规范,并可演示优秀完成基本要求,文档规范,并可演示良好强化班同学至少达到良好水平结构 定义段 % 规则段 % 用户子例程段 7、Lex定义段 变量 常量 正规表达式 7、Lex定义段 起始于%符号,终止于%符号,其间可以是包括include语句、声明语句在内的C语句。 “ #define LT 1 extern int lineno;% /*正规表达式*/ delim tn ws delim+ letter A-Za-z digit 0-9 id letter(letter|digit
4、)*7、Lex规则段 起始于“%”符号,终止于“%”符号,其间则是词法规则。 词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成,动作部分是由C语言语句组成,这些语句用来对所匹配的模式进行相应处理。 7、Lex用户子例程段 可以包含用C语言编写的子程序,而这些子程序可以用在前面的动作中,这样就可以达到简化编程的目的 install_id() . 7、Lex 结构 定义 % 规则 % 辅助子例程 8、Yacc定义段 % #define YYSTYPE double % %token NUMBER %left + - %left * / 注:%token NUMBER表明了NUMB
5、ER是一个单词符号,%left则表明了运算符号的左结合性,并且*和/和优先级比+和-的优先级高。 8、Yacc规则段 %expr : NUMBER $=$1; | expr + expr $ = $1 + $3; | expr - expr $ = $1 - $3; | expr * expr $ = $1 * $3; | expr / expr $ = $1 / $3; %8、Yacc用户子例程段 #include extern char yytext; extern int column; yyerror(s) char *s; fflush(stdout);printf(n%*sn%*s
6、n, column, , column, s); 8、Yacc主要参考资料1、编译原理课程设计,王雷等,机械工业出版社,20052、Lex与Yacc,杨作梅等译,机械工业出版社,2003重要提示1、Cminus或Csubset Lex and Yacc定义可参照 a)Lex definition for MiniC lex.l,ANSICgrammar.doc b)Yacc definition for MiniC minic.y, ANSICgrammar.doc 重要提示2、RENFA a)类似算术表达式计算分析过程 使用算法优先基本思想,将中缀变为后缀 Writing own regul
7、ar expression parser.html重要提示2、RENFA b)递归下降分析法 main.java expcat_expfactorterm(expr)重要提示2、RENFA c)根据RE文法构造相应LR语法分析表 重要提示3、求-闭包 使用栈,深度优先遍历Writing own regular expression parser.html 重要提示4、SeuLex示例程序 lex.cpp 重要提示5、SeuYacc示例程序 yacc.cpp 重要提示6、SeuLex数据结构定义 NFA: LinkList/List/Set/Vector DFA: LinkList/List/S
8、et/Vector/ HashTable 重要提示7、SeuYacc数据结构定义 LrItem: LrState: 重要提示8、SeuLex算法 对正规表达式添加”.”操作符号:如果*、)、字符后面是字符或(则在此符号后加. 并以#结束重要提示9、SeuLex算法 DFA最小化:初始状态DFA分为非终态结点和终态结点并且终态相同的集合。在程序编写过程中发现如果仅仅将结点分为终态和非终态两个集合,那么最后终态就会出现冲突。重要提示10、SeuYacc算法 闭包算法:项目中每一个产生式只需做一遍扩展即可,如果每次扫描项目中已有的所有产生式并做扩展,会带来很多冗余的操作,影响了效率,可在产生式中设计了一个标志位,保证同一个项目中每个产生式只做一次扩展。