第一三章引论及文法.ppt

1、编译原理,任课教师：周长敏,第一章 编译程序概论,1.1 什么是编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译阶段的组合 1.5 编译技术和软件工具,1.1 什么是编译程序,一个编译程序就是一个语言翻译程序。它把一种语言（称作源程序）书写的程序翻译成另一种语言（称作目标语言）的等价的程序,1.1 什么是编译程序,1.2 编译过程概述,词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成,编译过程概述,词法分析阶段,这个阶段的任务是从左到右一个字符一个字符地读入源程序对构成源程序的字符流进行扫描和分解。,词法分析,一个C源程序片断： int a; a = a

2、+ 2; 单词类型 单词值 保留字 int 标识符(变量名) a 界符 ; 标识符(变量名) a 算符(赋值) = 标识符(变量名) a 算符(加)+ 整数 2 界符 ；,语法分析,语法分析的任务是在词法分析的基础依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树或其他的内部码).通过语法分析确定整个输入串是否构成一个语法上正确的程序.,语义分析阶段,审查源程序有无语义错误，为代码生成阶段收集类型信息。如类型检查、强制类型转换、检查数组下标等。 例如：整型数据+实型数据,中间代码生成,在语义分析之后，将源程序表示成一种内部表示形式。 “中间代码”是一种结构简单、含义明确的记号系统

3、。很多编译程序采用了一种近似“三地址指令”的“四元式”。 四元式的形式为（运算符，运算对象1，运算对象2，结果）,代码优化,此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效。,目标代码生成,这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编代码。,编译程序的结构,词法分析程序 语法分析程序 语义分析程序 中间代码生成程序 代码优化程序 目标代码生成程序 出错处理程序 表格管理程序,1.4 编译阶段的组合,编译过程的前端（front end） 词法分析、语法分析、语义分析和中间代码生成等 编译过程的后端 （back end）

4、目标代码生成等,1.5 编译技术和软件工具,语言的结构化编辑器 语言程序的调试工具 语言程序测试工具 高级语言之间的转换工具 并行编译技术,练习题：,1_是两类程序语言处理程序。 A高级语言程序和低级语言程序 B解释程序和编译程序 C 编译程序和操作系统 D系统程序和应用程序 2、高级语言编写的程序经编译后产生的程序叫_。 A源程序B目标程序C连接程序 D 解释程序 3、编译程序是一种常用的_软件。A.应用 B.系统 C.工具 D.测试,4、对编译程序而言，输入数据是_,输出结果是_。 5、画出编译程序的总体结构图，简述各部分的主要功能。 6、课本P11-12页，第一章练习题第1-4题。,编译

5、程序用来翻译高级语言编写的源程序 正如翻译英文一样，要先学习英语的单词和语法！ 语法（文法）：描述句子的构成规则。（例：句子主语+谓语 ）只需要一些简单的规则就可以概括中文句子的结构。 那么高级程序语言如何用简单的规则来表示呢？,课前思考：,描述程序语言的符号系统,第三章文法和语言,所谓一个程序语言的文法是指一组规则，用它可以形成和产生一个合适的程序。,3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型的分析 3.7 有关文法实用中的一些说明, = = | =我|你|他 = 王明|大学生|工人|英语 =

6、 =是|学习 = |,3.1 文法的直观概念,有了以上规则，即可推导出（产生）句子,寻找=左端的带有的规则并把它表示成=右端的符号串，这个动作表示成： = ，然后再得到的串中，选取或，再用相应的规则=右端代替，重复下去，得到句子。,“我是大学生”的推导过程,= = = 我 = 我 = 我是 = 我是 = 我是大学生,同样，还可以推导出“王明是大学生”，“我学习英语”等无数句子。因此可以说： 文法是以有穷集合刻画无穷集合的一种工具。,规则集,句子集合,C语言的基本符号有if,while,for,字母、数字和+、-、（、）、=等分界符，由这些符号组成的各种可能序列的符号串构成一个无穷的集合，而C语

7、言就是这个集合的子集。,英语的基本符号有26个字母和一些标点符号，由这些基本符号所组成的各种可能序列的符号串构成一个无穷的集合，而英语就是这个集合的子集。,3.2 符号和符号串,字母表：元素的非空有穷集合，字母表中的元素又称为符号，因此字母表也称为符号表（语言的基本符号集合） 符号串：由字母表中的符号组成的任何有穷序列称为符号串（各种句子） =0，1 符号串有01 11 10 A=a，b，c 符号串有a，b，c，ab，aaca,3.2 符号和符号串,任何一种语言都是由该语言的基本符号所组成的符号串集合的子集。,符号串,符号顺序不同，符号串不同 ab和ba不同 可以使用字母表示符号串 x=STR

8、 符号串的长度：如果某符号串x中有m个符号，则其长度为m，表示为|x|=m 001110的长度为6 空符号串：即不包含任何符号的符号串，用表示，长度为0，即|=0,符号串的运算,符号串的头尾，固有头和固有尾： 如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头 设z=abc，那么 z的头（前缀）：,a，ab，abc 固有头：,a，ab 尾（后缀）：，c，bc，abc 固有尾：，c，bc,Z=aabb,求符号串Z的头尾，固有头和固有尾,练习：,符号串的省略写法,省略写法： 强调头：z=x 强调某符号在符号串中某处出现：z=x 强调符

9、号是符号串的第一个符号：z=a,符号串的运算,符号串的连接： 设x和y是符号串，他们的连接xy是把y的符号写在x的符号之后得到的符号串 x=ST，y=abu xy=STabu |x|=2，|y|=3，|xy|=5 特殊的连接：x=x=x,符号串的运算,符号串的方幂： 设x是符号串，把x自身连接n次得到符号串z，即z=xxxx，称为符号串x的方幂，写作z=xn，即把符号串x相继地重复写n次 x0=，x1=x，x2=xx，x3=xxx x=AB， x0=，x1=AB，x2=ABAB，x3=ABABAB 对于n0，有xn=xxn-1=xn-1x,符号串的运算,符号串集合：若集合A中的一切元素都是某字

10、母表上的符号串，则称A为该字母表上的符号串集合（简单说法：由许多符号串组成的集合） 例如：两个符号串集合A和B的乘积表示为： AB=xy|xA且yB，即AB是满足x属于A，y属于B的所有符号串xy所组成的集合,符号串的运算,例如： A=a，b，B=c，d 则集合AB=ac，ad，bc，bd 对任意符号串x，有x=x=x，所以有A=A=A * ：表示字母表上的所有有穷长的串的集合 =0，1，即*=，0，1，00，01，10，11，000，001，010，,符号串的运算,也可将*表示为字母表的方幂形式： *=012n *称为集合的闭包 +=12n称为集合的正闭包 显然 有*=0+， +=*=*(试

11、证明看？）,集合的正闭包和集合的闭包,集合的闭包比正闭包多个!,3.3 文法和语言的形式定义, = = | =我|你|他 = 王明|大学生|工人|英语 = =是|学习 = |,= = = 我 = 我 = 我是 = 我是 = 我是大学生,非终结符,终结符,产生式,开始符号,终结符号：是一个语言不可再分的基本符号，如：标示符、常数、算符、界符等。 非终结符号：用来代表语法范畴，是由终结符号和非终结符号组成的符号串，如：表达式、语句、子程序、函数等。 开始符号：是一个特殊的非终结符号，代表语言中我们最感兴趣的语法范畴。 产生式：也称规则,3.3 文法和语言的形式定义,文法即是用规则（产生式）来描述语

12、言：语言中的每个句子可以用严格定义的规则来构造 文法的定义 推导的概念 句型、句子和语言的定义,3.3 文法和语言的形式定义,规则：也称为重写规则、产生式或生成式 是形如或=的(, )有序对 其中称为规则的左部，称为规则的右部。 或=读作“定义为” 例如：Aa,文法G定义为四元组(VN，VT，P，S )其中 VN：非终结符号(或语法实体，或变量)集； VT：终结符号集；构成语言文法的单词，是语法成分的最小单位。 P：规则( )的集合，(VN VT )*，且至少包含一个非终结符， (VN VT )*； S：称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN，VT和P

13、是非空有穷集。VN和VT不含公共的元素即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表,文法的定义,文法的定义,例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,文法的写法,(1) G：SaAb Aab AaAb A,(2) GS： SaSb Aab AaAb A (3) GS: SaSb Aab |aAb |,习惯： 第一条产生式左部是识别符，用括起的是非终结符，不用的是终结符，或大写字母表示非终结符，小写字母表示终结符,直接推导“”： 是文法G的产生式（或规则），若有v,w满足：v=,w= , 其中V*,V*

14、，则称v直接推导到w,记作 v w，也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,推导的定义,推导的定义,若存在v =w0 w1 . wn=w,(n0) 则记为vw，称作v推导出w，或w归约到v，推导长度为n 若有vw或 v=w， 则记为vw,+,+,*,例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111,+,句型、句子的定义,句型 有文法G，若S = x，则

15、称x是文法G的句型。 句子 有文法G，若S = x，且xVT*，则称x是文法G的句子。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S，0S1，00S11，000S111，00001111 G的句子00001111，01,*,*,句型、句子,例：GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号a，+，*，(和)构成的算术表达式,(文法生成的)语言的定义,由文法G生成的语言记为L(G)，它是文法G的一切句子的集合: L(G)=x|S = x，其中S为文法

16、的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,*,例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen | n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,3.4 文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式，都有(VNVT)*，且至少含有一个非

17、终结符，(VNVT)* 1型文法（上下文有关）：对任一产生式，都有|， 仅仅 S除外 2型文法（上下文无关） ：对任一产生式，都有VN， (VNVT)* 3型文法（正规文法）：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT *,文法的类型,例：1型（上下文有关）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD Ca BDbD Db AabD,文法的类型,例：2型（上下文无关）文法 文法GS：SAB ABS|0 BSA|1,3型文法,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,0型文法,文法的类型,四类文法之间的逐级“包含”关系,

18、四种文法之间的关系 是将产生式做进一步限制而定义的。,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法产生的语言称为1型语言或上下文有关语言 2型文法或上下文无关文法产生的语言称为2型语言或上下文无关语言 3型文法或正则（正规）文法产生的语言称为3型语言正则（正规）语言,说明,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。 2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。,3.5 上下文

19、无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构。如无特别说明，“文法”均指上下文无关文法。 语法树-句型推导的直观表示,语法树,设G=( VN，VT，P，S)为一上下文无关文法，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN 4. 如果结点n有标记A，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标

20、记而构成的行称为句型,上下文无关文法的语法树,句型aabbaa的可能推导序列和语法树,例: GS: SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树) 一棵语法树表示了一个句型的种种可能的(但未必是

21、所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢,例：GE:E i E E+E E E*E E (E),句型 i*i+i 的两个不同的最左推导： 推导1：E E+E E*E+E i*E+E i*i+E i*i+i 推导2：E E*E i*E i*E+E i*i+E i*i+i,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是

22、二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。,如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件 二义文法改造为无二义文法 GE:E i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定算符优先性和结合性,文法的二义性和语言的二义性,3.6 （上下文无关文法）句型的

23、分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,句型的分析算法分类,分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,两种方法反映了两种语法树的构造过程。 自上而下方法是从文法符号开始，将它做

24、为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,自上而下的语法分析,例：文法G： S cAd A ab A a识别输入串w=cabd是否为该文法的句子,自下而上的语法分析,例：文法G： S cAd A ab A a识别输入串w=cabd是否该文法的句子,自上而下的语法分析(1)S cAd (2) A ab (3) A a 识别输入串w=cad是否为该文法的句子,若S cAd 后选择(2)扩展A，S cAd cabd 那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d

25、匹配，宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子） -显然是错误的结论。 导致失败的原因是在分析中对A的选择不是正确的。,S c A d a b 这时应该回溯，把A为根的子树剪掉，扫描过的输入串中的A吐出来，再试探用产生式（3）,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？ 2）在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,短语

26、直接短语 句柄,G是一文法，S是文法的开始符号，是文法G的一个句型。如果有SA且 A 则称是句型相对于非终结符A的短语。如有A则称是句型相对于规则A的直接短语（简单短语）。一个句型的最左直接短语称为该句型的句柄。,*,+,从句型的推导树上很容易找出句型的短语和直接短语。设A是句型的某一子树的根，其中是形成此子树的末端结点的符号串，则其中是句型的相对于A的短语。若这个子树只有一层分支，则是句型的直接短语。,3.7 有关文法实用中的一些说明,引入文法的目的：描述程序设计语言 一方面，对文法提出一些限制条件，但并不真正限制语言； 另一方面，对文法进行扩充,3.7.1 有关文法的实用限制,限制化简文法

27、 文法中不含有有害规则和多余规则 有害规则：形如UU的产生式。会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则 文法中不含有不可到达和不可终止的非终结符 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1. A必须在某句型中出现 即有S =A，其中，属于V* 2. 必须能够从A推出终结符号串t来 即A =t，其中tVT*,*,*,化简文法,例：GS ： 1) SBe 2) BCe D为不可到达 3) B

28、Af C为不可终止 4) AAe 5) Ae 6) CCf 7) Df 产生式 2），6），7）为多余规则应去掉。,3.7.2 上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A， AVN，称这种规则为规则 因为规则会使得有关文法的一些讨论和证明变得复杂，有时会限制这种规则的出现 两种定义的唯一差别是句子在不在语言中 文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L=L也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L 和L- 分别是上下文有关语言、上下文无关语言和正规语言。,练习题,1、文法G：S xSx | y 所识别的语言是 。 Axy*x B(xyx)* Cxx*yxx* Dx*yx* 2、文法 G 产生的_的全体是该文法描述的语言。 A句型 B终结符集 C非终结符集 D句子 3、设 G 是一个给定的文法， S 是文法的开始符号，如果 Sx( 其中 xV*), 则称 x 是文法 G 的一个_。 A 候选式 B 句型 C 单词 D产生式,4、已知文法G(E)为： ET|E+T|E-T TF|T*F|T/F F(E)|i 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。,解：可为E+T*F构造一棵语法树（见下图），所以它是所给文法的句型。 从语法树中容易看出，E+T*F