毕业答辩-C语言编译器设计与实现.ppt

,C语言编译器的设计和实现,LOGO,姓名：专业：软件1008学院：软件学院指导教师：,目录,背景及意义,相关技术及理论,系统需求分析,系统总体设计,系统详细设计和实现,背景及意义,背景,随着计算机的广泛应用，计算机程序设计语言也从初期的机器语言发展为汇编语言，以及限制的各种高级程序设计语言。而编译技术室计算机语言发展的支柱，也是计算机科学中发展最迅速、最成熟的一个分支，他集中体现了计算机发展的成果与精华。其核心思想就是把同样的逻辑结构和思想从一种语言表示的程序转换为另外一种语言表示的程序。从高级语言，最终到硬件执行的物理信号，这一层层的转化，都涉及编译技术的应用。因此，编译技术是人类智慧到机器执行的桥梁，从软件到硬件层层推进的衔接力量。,背景及意义,编译器是一种相当复杂的程序，其代码的长度可从几千行到几百万行不等。编写甚至读懂这样的一个程序都非易事，大多数的计算机专业人员从来没有编写过一个完整的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。因此，掌握这一技术具有非常重大的实际意义。,意义,相关环境,VC2012,软件环境,硬件环境,CPU：IntelCoreI5操作系统：Windows7,相关理论,编译原理形式语言理论词法分析语法分析语义分析中间代码生成,使用技术,标准C+实现,保存不同信息的数据结构,大量算法,开发步骤,1.认真分析，合理分工2.算法设计，方案确定3.语言选择，编制程序4.调试程序，确保质量5.资料整理，文本形成,系统需求分析,两者语法结构上可以不同，但语义上是等同的,系统需求分析,识别C源文件语法正确性判断出错类型识别词法错误分析C源文件语义,系统总体设计,系统详细设计和实现,词法分析语法分析语义分析中间代码生成,词法分析,词法分析的功能,属性字：单词的一种机内表示(反映单词的有关特性).,单词符号（单词）：程序语言具有独立意义的最小语法单位,保留字(关键字),常数,标识符,界限符(特殊符号),程序语言定义的具有固定意义的标识符如:Pascal中的begin、end、if、while。,用来表示各种名字.如:变量名、数组名、过程名等。,如:128、0.123、3.14E-2。,如:+、-、*、/、=、=、=、=等。,单词符号,词法分析,单词符号的种类,词法分析程序的设计与实现,初始化,读字符,是字母?,读标识符,数字?,取数字,查常量表,生成属性字,写到输出流,是否分析结束,结束,特殊符号?,出错,查特殊符号表,生成属性字,查保留字表,查到?,查名字表,生成属性字,生成属性字,Y,Y,Y,Y,N,N,N,N,Y,N,语法分析,自顶向下LL（1）递归下降自底向上LR（0）SLR（1）LR（1）LALR（1）,语法分析-LR（1）,LR(K)是一种有效的自底向上语法分析方法。它的适应范围广，分析速度快，且能准确及时地发现语法错误，所以是当前最一般的语法分析方法。LR(0)是基础，但分析能力低，局限性大SLR(1)“简单LR”实现容易，能力较强，不适合有些文法LR(1)分析能力最强，适用于大多数文法，但工作量大LALR(1)能力介于SLR(1)与LR(1)之间，空间节省,语法分析-LR（1）,1、分析思想及逻辑结构,语法分析-LR（1）,1、分析思想及逻辑结构,分析表,总控程序,控制机构,r4,语法分析-LR（1）,语法分析采用LR分析器，由于分析表数据量庞大，采用程序自动算出。1)求非终结符的first集。为方便以后访问，求完所有非终结符的first集后将它放在一个以非终结符为键的hash表中。,语法分析-LR（1）,2)求项目集闭包，需要用到第1步中的结果。闭包利用集合的唯一性，故使用C+标准STL库中的set模板。利用一个三元式存储标识一个产生式：structitem_nodesize_tcfg_no;/产生式编号size_tdot_pos;/加点位置intpossible_prefix;/输入符号;,语法分析-LR（1）,3)求go函数。即是一个项目集遇到输入代码流中的一个符号后转向的另一个状态时候的项目集，并将之返回。4)求整个文法的项目集簇。项目集的个数即为有穷状态自动机的状态个数，根据以上57个产生式，本编译器产生的状态为171个。,语法分析-LR（1）,5)生成LR(1)分析表，由于分析表的庞大，故将之生成后存于文件中。即action_goto_table.txt6)完成LR分析器，读入第5步的分析表即可进行语法分析。,语法分析-LR（1）,A：AB，AABBaBbGA的LR分析表,语法分析-LR（1）,ACTION,GOTO,S4,S5,语义分析,将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，而属性的计算以语义规则(semanticrules)的形式赋予由文法符号组成的产生式；在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。最终生成三地址码的四元式表示形式,语义分析,对于在语法分析的每一个非终结符号，需要记录该符号所包含的代码，对于表达式的翻译，还要记录表达的地址，定义结点U_node如下：structU_nodestringname;/名字stringcode;/四元式代码inttype;/类型intaddr;/地址stringop;/操作符intinstr;/当前指令地址vectortruelist;/布尔表达式真出口vectorfalselist;/布尔表达式假出口vectornextlist;/跳转指令出口;,语义分析,LR分析器里面的栈节点,structstack_nodeintstate;tokentok;U_nodenodeInfo;,语义分析,LR分析器里面的栈节点,structstack_nodeintstate;tokentok;U_nodenodeInfo;,语义分析,符号表，使用链表存储,structidenfie