编译原理.ppt_文客久久网wenke99.com

资源描述

1、编译原理,尹剑飞科技楼13424410028,编译原理和技术的重要性,设计和开发编译器的原理和技术将会在一个计算机工作者的职业生涯中被多次使用。- 编译器的构造综合了计算机科学的各个方面：计算机理论、程序设计、软件工程，是理论应用于实践的成功典范。-,编译原理和技术的重要性,自计算机科学诞生以来，语言处理器的工程化就一直在推动，随着相关理论的开发不断改进。- 相对其它技术而言，编译器技术是一种内功修炼，因为任何计算机问题都可以化为语言翻译问题 - some one,第一章编译器介绍,1.1 编译器概貌1.2 源程序分析1.3 编译器的阶段1.4 编译器的同胞1.5 阶段的组合1.6 编译器构

2、造工具,1.1 编译器概貌,编译器（程序）,错误信息,第一个编译器出现于1950年,第一个Fortran编译器花了18人年,通过工具支持，基本的编译器可作为学生项目，在一个学期内完成。,1.1.1 编译器IO,分析 ( Analysis )综合 ( Synthesis ),分析,中间表示,综合,1.1.2 编译过程分为两个基本部分,1.1 编译器概貌,1.1 编译器概貌,1.1.3 语法树例子,=,position,initial,rate,60,+,*,position = initial + rate * 60,1.1 编译器概貌,很多软件（不一定是编译器）执行类似的“分析”结构编辑器，如

3、：HTML editor格式化（美化）打印，如：自动排版系统静态检查，如：语法检查器解释器，如：表达式计算器，SQL检查解释器，java ,1.1 编译器概貌,D.cpp,绝对机器码,E.asm,可重定位的机器码,库可重定位的机器码,a.h,b.h, .,C.cpp,程序的执行是怎样炼成的？,1.2 源程序 “分析”,分析包括三个阶段词法分析（线性分析）：字符-词（Token）语法分析（层次分析）：词-句语义分析：句-正确（有意义）的句子,1.2 源程序 “分析”,输入字符串：p o s i t i o n = i n i t i a l + r a t e * 6 0，得到下述词(Token

4、):标识符：position, initial, rate赋值运算符：=加法运算符：+乘法运算符：*数：60,1.2.1 词法分析（线性分析）,1.2 源程序 “分析”,赋值语句,标识符,=,表达式,+,表达式,表达式,标识符,*,表达式,表达式,position,initial,标识符,rate,数,60,position = initial + rate * 60 的语法树,标识符 | = rate,1.2.2 语法分析（层次分析）,与1.1.3不同的语法树,1.2 源程序 “分析”,程序的层次结构通常由递归规则定义：规则1：任何是规则2：任何是给定和，则下述也是表达式规则3： + 规

5、则4： * 规则5：（）,1.2.2 语法分析（层次分析）,那些是更基本的规则呢？,线性 VS 层次非递归定义 VS 递归定义三型文法 VS 二型文法（more on later),用自然语言表述计算机语言显示了它的不足，需要一种更为严谨更易评价的表达方法来刻画词法和语法等语言要素。,1.2.3 词法分析 VS 语法分析,1.2 源程序 “分析”,检查是否存在语义错误，获取类型信息。类型检查,1.2.3 语义分析,1.2 源程序 “分析”,position,=,+,rate,*,initial,60,position,=,+,rate,*,initial,60,int2real,1.3

6、编译器的阶段,源程序,词法分析器,语法分析,语义分析,中间代码生成器,代码优化器,代码生成器,目标程序,符号表，记录符号与其关联的属性，如类型、作用域，对于过程名符号，有其参数个数和类型、传值还是传引用、返回类型。符号在词法分析阶段进入符号表，而与其关联的属性要在后继阶段补充。float position, initial, rate;,1.3.1 符号表管理,1.3 编译器的阶段,1.3 编译器的阶段,在遇到错误时，应尽可能继续执行相应阶段。词法分析：不成词的余留串，如3int语义分析：语法结构良好，但语义错误，如加两个标识符，类型分别为数组和过程。,1.3.2 错误处理,中间代码可看作是一

7、种抽象机上的程序，如GCC产生的中间代码，Java Byte代码。重要特性：容易从语义分析阶段产生，容易翻译到目标代码。中间代码有多种形式。三地址码，最多三个操作数流控和过程调用（more on later),1.3 编译器的阶段,1.3.3 中间代码生成,1.3 编译器的阶段,1.3.4 代码优化1.3.5 代码生成,（more on later),1.4 编译器的同胞,预处理器宏扩展文件包含语法糖衣汇编器装载和联结器OS外部引用,1.5 阶段的组合,前端：主要依赖源程序，独立于目标机器，词法分析、创建符号表、语法分析、语义分析、中间代码生成，可能有优化器的参与。后端：代码优化、代码生成,

8、1.6 编译器构造工具,解析产生器扫描产生器语义导向的翻译引擎自动代码生成器。数据流引擎,Chaper2.1 一个简单的一遍编译器,文法基础,提纲,本章为后继章节，特别是编译器前端（词法分析、语法分析、中间代码生成）提供一个实践的铺垫。通过设计与开发一个简单的一遍编译器，展示了编译器前端构造的基本技术。该一遍编译器为将中缀表达式语句编译成后缀表达式语句。该例子还不够完善，希望同学们努力读懂并完善之。,编译器前端结构,字符流,词法分析器,单词流,语法导向的翻译器,中间代码,文法Grammar,我们采用文法来描述语言的句子结构在得到某语言的文法基础上，我们可判定一个句子是否属于该语言判定一个句子是

9、否满足某语言的文法成为语法分析的核心问题下面的内容围绕如何设计上下文无关的文法以解决这个判定问题,上下文无关的文法,stmt - if (expr) stmt else stmt上下文无关的文法，有以下几个组成：终止符（集合），或称为tokenif, (, ), else非终止符（集合）stmt, expr产生式（集合）stmt - if (expr) stmt else stmt左侧有且仅有一个非终止符有且仅有一个非终止符作为起始符，如非终止符S为文法G的起始符，表示为GS,描述加减的文法Glist，有以下4个产生式组成,list - list + digitlist - list digi

10、tlist - digitdigit - 0|1|2|3|4|5|6|7|8|9-左部相同的产生式，可以合并为： list - list + digit | list digit | digit终止符集合VT为：+,-,0,1,9，非终止符集合VN为：list, digit,文法导出串（句型）,从起始符开始，重复替换非终止符为其所在产生式的右侧，所得到的符号串即称为文法导出串，也称为句型。如文法Glist的句型有：list = list + digit （一个句型） = list digit + digit （一个句型） = digit digit + digit （一个句型） = 9 -

11、5 + 2 （一个句型且是句子）只包括终止符的文法导出串，称为该文法的句子，句子的集合，称为该文法定义的语言。,*,描述块的文法-Gblock,block - opt_stmts opt_stmts - stmt_list | stmt_list - stmt_list ; stmt | stmt,是终止符，还是非终止符,是终止符,给定文法GS，其分析树/语法树,根S为起始符叶节点为终止符（token）或中间节点为非终止符例子：9-5+2，按下述文法的分析树,分析树-Parse Tree语法树-Syntax Tree,9-5+2，按文法Glist的分析树（语法树）,list,list,digi

12、t,list,digit,digit,9,-,5,+,2,list - list + digit | list digit | digitdigit - 0 | 1| 2|3|4|5|6|7|8|9,9-5+2是Glist的一个句型（这里是句子）的依据：可为9-5+2产生一棵分析树,分析树构造过程/句型推导过程,list,list - list + digit | list digit | digitdigit - 0 | 1| 2|3|4|5|6|7|8|9,list,digit,list,digit,digit,9,-,5,+,2,list = list + digit,判断9-5+2是否

13、是文法Glist的句型（这里是句子）的最左推导过程如下：,= list digit + digit,= digit digit + digit,= 9 digit + digit,= 9 5 + digit,= 9 5 + 2,小结：分析树构造过程/句型推导过程,为判定一个串是否是一个文法的句型或句子，分析树方法与推导方法效果一样。分析树方法直观，但无法直接从结果分析树中看出推导步骤。推导方法可以看出中间推导过程。一个串是一个文法的句型或句子 iff存在一棵分析树（语法树） iff存在一个的最左推导或一个最右推导（规范推导）或即非最左也非最右推导。一棵分析树对应唯一的最左推导和唯一的最右推导。

14、,9-5+2的最左推导与规范推导（最右推导）比较,最左推导,最右推导（规范推导）,list = list + digit,list = list + digit,= list - digit + digit,= list + 2,= digit - digit + digit,= 9 - digit + digit,list - list + digit | list digit | digitdigit - 0 | 1| 2|3|4|5|6|7|8|9,= 9 - 5 + digit,= 9 - 5 + 2,= list digit + 2,= list 5 + 2,= digit 5 +

15、2,= 9 - 5 + 2,最左归约和最右归约,与推导相反的过程称为归约最左归约是最右推导的逆过程最右归约是最左推导的逆过程关于归约，我们将在自底向上的语法分析章节详解。,文法二义性,文法Gstring为二义性文法string - string + string | string - string | 0|1|2|3|4|5|6|7|8|9因为有1棵以上的分析树对应9-5+2,大家动手画一下,Gstring在+,-运算符的左结合性问题上出现了二义性,文法二义性,给定文法GS：S - if E then S | if E then S else S | Nif E1 then if E2 the

16、n S1 else S2，是GS的合法句型，但存在不同的解释，即有1棵以上的分析树与之对应，所以GS为二义性文法。,GS在else与then结合性的问题上出现了二义性,文法二义性,给定某文法G，若存在某句子或句型w，与w对应的分析树（语法树）不只一个，则称G为二义性文法。或者说，与w对应的最左推导不只一个或者说，与w对应的最右推导不只一个我们在设计文法时，应努力避免二义性。,操作符的结合性-左结合,文法Glistlist - list + digit | list digit | digitdigit - 0 | 1| 2| 3|4|5|6|7|8|9-文法Glstlst - digit +

17、lst | digit lst | digitdigit - 0 | 1| 2| 3|4|5|6|7|8|9,谁体现左结合性？,操作符的结合性-左结合,list,list,digit,list,digit,digit,9,-,5,+,2,lst,lst,digit,digit,9,+,5,-,2,lst,digit,list - list + digit | list digit | digit,lst - digit + lst | digit lst | digit,操作符的结合性-左结合,文法描述了特定的数据结构文法设计也即数据结构设计合适的数据结构设计可以方便对数据的操作语法树操作包括

18、对语言特征（如左结合性）的验证经验：文法左递归可以体现左结合性但是，我们应转换文法中含有左递归的产生式，以去除左递归，从而利于自顶向下的语法分析（见后）,操作符的结合性-右结合,文法Grightright - letter = right | letterletter - a |b|z,a=b=c的语法树，如何画？,经验：文法右递归可以体现右结合性,文法设计内功心法1-左递归,文法Glistlist - list + digit | list digit | digitdigit - 0 | 1| 2| 3|4|5|6|7|8|9上述文法较好地体现了+,-运算的左结合性，要产生带有*,/运算的

19、表达式，可依照左递归范式进行。,四运算表达式文法Gex草案,文法Gexex - ex + digit | ex digit | ex * digit | ex / digit | digitdigit - 0 | 1| 2| 3|4|5|6|7|8|9,9-5*2，是文法Gex的句子吗？,文法Gex的ex产生式体现*, /比+,-优先吗？,文法设计内功心法2-按优先级引入非终止符,为处理以下3种优先级常数, () *,/+,-我们引入2个非终止符term：封装仅含有*,/计算过的表达式factor：封装仅含有常数,()计算过的表达式,文法设计内功心法2-按优先级引入非终止符,文法Gexprex

21、- 0|1|9,Gexpr的特点：,可产生四则运算表达式（句子）,体现结合性和优先级,可处理括号,无二义性,左递归,一位十进制,只能一次产生一个表达式,我们离一个简单的后缀表达式编译器还有多远,语法制导的翻译概念自顶向下（递归下降）的语法分析（解析）预测分析方法左递归消除后缀表达式代码生成,练习,给定上下文无关的文法GSS- S S+ | S S * | aaa+a*是GS的句子吗？GS产生的语言是什么？写出下述语言的文法an bn| n=0任何不是以0开始的所有偶整数所组成的集合所有由奇数个1和偶数个0所组成的符号串的集合后缀表示的算法表达式逗号分隔的左结合的标识符列表,练习,下面是否存在二

22、义性？S - 0 S 1 | 01S - S v SS - SS-S a | b SS - S ( S ) S | 给定文法GS:S ABS cA bAA aB aSbB c试分别用最左推导和规范推导导出bbaacb,Chapter2-2 语言的形式化定义基础,语言的形式化定义基础,以下给出若干本书用到的基本语言形式化定义的基本概念以便于读本书时理解,字母表,字母表(符号集)由符号组成的集合，如字母表A=a,b,ca,b,c称为符号，一般为常量，也可以是变量，根据具体上下文确定。,符号串,符号串A=a,b,c是一个字母表，则a,b,c,ab,ac,bc,abc,aabc等都是字母表A上的符号串

23、。设,，x 是符号串，若x = ,则称是x的子串；特别地，当= （= ）时，称是x的前（后）缀,若 x，则称是x的真前（后）缀,符号串操作,符号串长|ab|=2，长度为0的符号串，记为,符号串连接若令符号串x=abc，符号串y=123，则xy表示符号串x与y的连接，即xy=abc123 x = x = x,符号串的n次方幂若有符号串x,则 x1 = x, x2 = xx, xn = xn-1x = xxn-1 特别地有， x0= ,strlen(“ab”),strcat(x,y),符号串连接的特征,x, 是的单位元,因此我们定义x0 = ,=,x,x,=,符号串集合的操作,符号串集合的和（

24、并集）A + B = w| w A 或 w B，其中A,B为符号串的集合,符号串集合的积AB = xy | x A 且 y B,符号串集合的方幂A1 = A, A2 = AA, An = An-1A = AAn-1 (n0),符号集合和运算（并运算）的特征, 满足交换律, 是的单位元, + A,=,A,=,A + ,符号集合连接运算的特征,是的零元,A,=,=,A,符号集合连接运算的特征,A0 = ,是的单位元,A,=,A,A,=,符号集合的闭包,A的正闭包：,A的自反传递闭包：,文法形式定义和语言的Chomsky分类,文法形式定义G=(VN, VT, P, S)，其中VN VT = ,VN

25、VT = V,文法GE:E - E + T| E T | TT - T * F | T / F | FF - D | (E)D - 0|1|9,G=( E, T, F, D, +,-,*,/,(,),0,1,2.,9, E - , T - , F - , D - , E),四类基本的文法,Chomsky将文法按产生语言的能力由强到弱分为四类基本的文法0型文法（短语结构文法，PSG）1型文法（前后文有关文法/上下文相关的文法，CSG）2型文法（前后文无关的文法/上下文无关的文法，CFG）3型文法（正规文法，RG）,0型文法（短语结构文法，PSG）,若文法G中任一产生式都有一般形式 V+ V* 其

26、中，对，不加任何限制PSG: Phrase Structure Grammar)。由0型文法生成（或者说：定义）的语言称为0型（递归可枚举）语言。它可由图灵（Turing）机识别。,0型文法（短语结构文法，PSG）,文法GSSACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 就是一个0型文法，它所产生的语言为,1型文法（前后文有关文法，CSG）,若一0型文法所有产生式具有形式（第一定义） 1A2 12 其中， 1,2V* V+ AVN| 1A2 |(S为起始符）且S不出现在任何产生式的右侧。 CSG ( Context Sensitive Grammar) 。1型文

27、法产生的语言称为前后文有关语言CSL，它可由线性限界自动机识别。,CSG第一定义,根据定义，含有产生式的文法不是1型文法。但S- （S为起始符）可作为1型文法的特例而接受之，条件是S不出现在所有产生式的右边。例文法G： S | A AaABC AabC CBBC bBbb bCbc cCcc因G含有S ，但S不出现在所有产生式的右侧，按第一定义，G仍被认为是1型文法。,CSG第二定义,1 型文法还有另一种定义形式（第二定义）： G的每个产生式形为且满足： | | | | , V+第二定义产生的语言=第一定义产生的语言-，即S-不可能存在于第二定义中。今后，我们采用第一定义。,2型文法（前后文

28、无关的文法，CFG）,若一1型文法G中所有产生式具有形式: A 其中，V+， AVNCFG(Context Free Grammar)。2型文法产生的语言称为前后文无关语言CFL，它可由下推自动机识别。非严格CFG允许-产生式存在，即非严格CFG产生式形式为 A 其中，V*，AVN,2型文法（前后文无关的文法，CFG,GS=(S,a,b, SaSb Sab, S) 产生的语言为,3型文法（正规文法，RG）,若一2型文法G中仅含有形如 AaB 或 Aa 的产生式，其中 A,B VN , a VT 则称G为右线性文法。类似地，若G中仅含有形如 ABa 或 Aa的产生式，则称G为左线性文法。3型

29、文法（正规文法）的产生式只有上述两种形式。,3型文法（正规文法，RG）,RG（Regular Grammar），3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。3型文法还可拓广定义为 AB A （ VT +）（不推荐!）,四类语言之间的关系,CSG，CFG，RG产生语言的特征,RG：xy*zCFG：anbnCSG：anbncn，anbncndn,练习,给定上下文无关的文法GSS- S S+ | S S * | aaa+a*是GS的句子吗？GS产生的语言是什么？写出下述语言的文法an bn| n=0任何不是以0开始的所有偶整数所组成的集合所有由奇数个1和

30、偶数个0所组成的符号串的集合后缀表示的算法表达式逗号分隔的左结合的标识符列表,练习,下面是否存在二义性？S - 0 S 1 | 01S - S v SS - SS-S a | b SS - S ( S ) S | 给定文法GS:S ABS cA bAA aB aSbB c试分别用最左推导和规范推导导出bbaacb,练习,下面的文法哪些是正规文法、右线性文法、上下文无关文法或上下文有关文法？（1）S aB (2) S AB B Bc A a B b B bC C c B b C c,（3）S aB (4) S AB B bC A a C c B bC C C c C ,（5）S aAb (6)

31、S aA aA aB S aA aaA A aA B b A aB A a A a B b,（7）S aCd (8) S aA aC B S aC aaA A bAb B b A a,Chapter2-2 语言的形式化定义基础,4类语言识别方法,题纲,目的和基本思想规则序列规则序列应用实例,目的和基本思想,通过特定的过程（算法），以识别任意文法是4类文法（语言）中的哪一类特定的过程是通过一系列有序的判定规则定义的每一判定规则，针对某一产生式P，判定P是哪一类文法中的产生式运用判定规则，对所有产生式Pi，得到其判定集合Pi-所属的文法产生式，其中最大者决定文法G是哪一类文法,规则序列：1. A-

32、规则,for 产生式P，顺序应用规则16：1. A- 规则1.1 若A为起始符且A在某产生式的右则，则 P是短语文法的产生式1.2 否则不影响前面对每条产生式的判定结果，即如下情况不影响判定结果：1.2.1 A为起始符且A不在任何产生式右则1.2.2 A不为起始符,规则序列：2. 右线性规则,当产生式P不满足规则1时，应用下述规则2. 右线性规则若P满足下面3个条件，则P是右线性产生式2.1 左侧只有一个非终止符（VN)2.2 右侧最多只有1个VN且在最右2.3 右侧至少有1个VT且在最左,规则序列：3. 左线性规则,当产生式P不满足规则2时，应用下述规则：3. 左线性规则若P满足下面3个条

33、件，则P是左线性产生式3.1 左侧只有一个非终止符（VN)3.2 右侧最多只有1个VN且在最左3.3 右侧至少有1个VT且在最右,规则序列：4. CFG规则,当产生式P不满足规则3时，应用下述规则4. CFG规则若P满足下面3个条件，则P是CFG产生式4.1 左侧只有一个VN4.2 右侧=1个VN4.3 若右侧仅有1个VN ，则该VN 不在右侧的两端，否则依据规则3/4识别,规则序列：5. CSG规则,当产生式P不满足规则4时，应用下述规则5. CSG规则若P满足下面2个条件，则P是CSG产生式5.1 左侧串长1且至少有一个VN5.2 右侧串长=左侧串长注意，| |=0,规则序列：6. PSG

34、规则,当产生式P不满足规则5时，应用下述规则6. PSG规则P是短语文法（PSG）产生式,规则序列应用实例,下面的文法哪些是正规文法、右线性文法、上下文无关文法或上下文有关文法？（1）文法GSS aB B Bc B b C c解：对文法GS的每条产生式顺序应用规则16，有：,规则序列应用实例1,S aB （由规则2，得右线性） B Bc （由规则3，得左线性）B b （由规则2/3，得左/右线性）C c （由规则2/3，得左/右线性）因为G中存在左线性和右线性产生式，所以G为正规文法。即max右线性,左线性,左/右线性 = 正规文法,规则序列应用实例2,(2) S AB （由规则4，得CFG）

35、 B Bc （由规则3，得左线性）B b （由规则2/3，得左/右线性）C c （由规则2/3，得左/右线性）按最大文法原则，G为CFG，即maxCFG，左线性, 左/右线性=CFG,规则序列应用实例3,（3）GSS aB （按规则2，右线性） B bC （按规则2，右线性）C c （按规则2/3，左/右线性） C （按规则1，不影响） max右线性, 左/右线性,不影响=max右线性, 右线性,不影响=右线性，所以G为右线性注意C c 可以判定为左线性也可以是右线性，但若判定为左线性，则max= 右线性, 左线性,不影响=正规，则将文法G所属文法类放大了。,规则序列应用实例4,（4）GSS

36、 aAb （按规则4，CFG）aA aB （按规则5，CSG） aA aaA （按规则5，CSG）B b （按规则2/3，左/右线性）A a （按规则2/3，左/右线性）max=CFG,CSG,左/右线性=CSG，即G为CSG,规则序列应用实例5,(8) GSS aA （按规则2，右线性）aC B （按规则6，PSG）aC aaA （不用判断了）B b （不用判断了）maxPSG, = PSG，即G为短语文法,Chapter3.1 词法分析,概念,提纲,关于suffix的Lexer:getNextToken解决思路基于状态编程的Lexer:getNextToken关于状态的问题所需学习的理论知

37、识3.1 设计扫描器时应考虑的问题3.1.2 单词符号的内部表示3.1.3 识别标识符的若干约定和策略,关于suffix的Lexer:getNextToken,有多少人读过Suffix源代码？,http:/192.168.150.81/sei 进入编译原理-第二章,关于suffix的Lexer:getNextToken,while (1) cin c; /超前读 if (c = | c = t) ; / omit white space else if (c = n) / number of lines else if (isdigit(c) / number else if (isalpha

38、(c) / identifier,keywords else if (c = EOF) else / *,/,+,-,err ,单词识别程序的自动生成问题,else if 风格、回退字符回题,单词识别的长度和优先次序,输入缓冲区问题,讨论-else if 风格,Switch/case/default 风格：与else if一样：对输入分类、前后处理之间无关联,while (1) c = inFile-get(); switch(c) case EOF: ; case : case t: case r: ; case n: ; default: ,while (1) switch(current

39、_state) case s_zero: cin c_char; c_state = s_ws; break; case s_ws: if (c_char= | c_char= t) cin c_char; else c_state = s_n; break;case s_n: if (c_char = n) +line_no; cin current_char; else current_state = s_digit; break;,状态编程风格：对程序自身的状态分类，前后有关联,讨论-单词识别的长度和优先次序,为单词识别的长度建立一个规则,对于有共同前缀的单词，采取最长匹配原则：最长单词优先,=,b,a,输入流,词法分析,c, current_char; current_state = s_ws;break;case s_ws:if (current_char = | current_char = t) cin current_char; else current_state = s_n; break;case s_n:case s_digit:case s_number:case s_alpha:case s_id_keyword:case s_EOF:case s_unknown: ,

展开阅读全文