编译原理文法与语言

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理 长春工业大学计算机科学与工程学院,内容回顾,什么是编译程序,编译的过程,词法分析,语法分析,语义分析及中间代码生成,优化,目标代码生成,编译程序的结构与组织,1,文法和语言,字母表和符号串的基本概念,文法和语言的形式定义,递归规则与递归文法,语法树与文法的二义性,文法的分类,2,字母表和符号串的基本概念,字母表,：元素的,非空有穷,集合。记为。 字母表包含了语言中所允许出现的一切,符号,。,例如： = 0，1,符号串(字),：字母表中的符号所组成的,有穷,序列。,一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。,语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定。,3,字母表和符号串的基本概念,空串,：不包含任何符号的串，记为。,*,：表示上所有符号串的全体。,空集,：，不包含任何元素。,在本课程中，语言被认为是句子的集合。所以，一个语言就是对应于它的字母表上的一个符号串集合。,4,关于符号串的运算,符号串的长度,：指符号串x中所含符号的个数，记为|x|。,符号串相等,：若x、y是字母表上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。,符号串的前缀,：指从符号串x的末尾删除0或多个符号后得到的符号串。,符号串的后缀,：指从符号串x的开头删除0或多个符号后得到的符号串。,5,关于符号串的运算,符号串的子串,：指从符号串x的开头和末尾删除0或多个符号后得到的符号串。 符号串的前缀、后缀都是它的子串。,连接(并置),：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。,注意：连接没有交换率，即 xy yx,而对于空串有 x=x=x,方幂,：x的n次方幂即将n个x连接。,x,0,= , x,1,= x, x,2,= xx, x,n,=xxx=xx,n-1,=x,n-1,x,6,符号串集合的运算,乘积,：,令A、B为两个符号串集合，A和B的乘积AB定义为：,AB = xy | x,A且y B,A=A =A,A= A =,方幂,：A的n次方幂就是将n个A相乘。 A,0,= A,1,=A A,2,=AA,A,n,=AAA=AA,n-1,=A,n-1,A,7,符号串集合的运算,集合的正则闭包和集合的闭包,：,设A为一个集合，则集合A的正则闭包用A,+,表示，定义为：,A,+,=A,1, A,2, . A,n,表示A上的所有的非空符号串的集合。,集合A的闭包用A*表示，定义为：,A* =A,0, A,+,表示A上的所有符号串（包括空字符串）的集合。,例如：A =a，b，,则A,+,=a,b,aa,ab,ba,bb,aaa,aab,A* = ,a,b,aa,ab,ba,bb,aaa,aab,8,文法和语言的形式定义,形式语言描述的两种方法 枚举方法,使用文法来描述,9,文法是一种工具，它可用于严格定义句子的结构,。,例如，能够描述句子“,the monkey ate the banana,”的文法如下：, , , the, , ate, ,banana,monkey,10,文法的形式定义（产生式/规则）,产生式,：一个产生式是一个有序对(,)，通常写作 或 := 。其中为左部； 为右部。,产生式意味着能将一个符号串用另外一个符号串替换。因而又被称为,重写规则,。一组规则规定了一个语言的语法结构。,规则中的符号分为两类：,终结符号、非终结符号,11,终结符与非终结符,终结符,：,V,T,组成语言的基本符号,。在程序设计语言中就是以前屡次提到的单词符号。如：基本字，标识符，常数，算符，界符等。从语法分析的角度看，终结符是一个语言的不可再分的基本符号。,非终结符,：,V,N,也称语法变量，用来代表语法单位,。如“算术表达式”、“布尔表达式”、“赋值句”、“子程序”、“函数”等。一个非终结符代表一个一定的语法概念，是一个,类（集合）,记号，而不是一个个体记号。,V,T,V,N,， V,T,V,N,为该语言的字母表,12,文法的定义,Chomcky文法的定义：,G=(V,N,V,T,P,S),其中：V,N,非空有限的非终结符号集 V,T,非空有限的终结符号集,P 产生式集,S 开始符号/识别符号，S V,N,文法被用来精确而无歧义地描述语言的句子的构成方式。,文法描述语言的时候不考虑语言的含义。,13,例：按文法形式定义表示上例文法。,解：根据文法的形式定义，文法,G1=（ V,N,， V,T,，P，S）,V,N,=句子，主语，谓语，冠词，名词，动词，直接宾语,V,T,= the，ate，banana，monkey ,产生式集合P由右面8条规则组成,开始符号S= , , , the, , ate, ,banana,monkey,14,1.,2.,3.,4.0 5.1,6.2 7.3,8.4 9.5,10.6 11.7,12.8 13.9,产生式的简写：A B , A C 可以简化为： A B | C,1.,2. | ,3.0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,15,文法举例,G1=(V,N,V,T,P,S),其中:V,N,=E,V,T,= i, +,*, (, ),P= EE+E，,E E,*,E，,E (E) ，,E i,S=E,16,语言的形式定义,文法的作用是描述某种语言的句子的构成方式。使用文法我们可以产生对应语言的句子。,从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。,17,推导和直接推导,直接推导,：v=A ，w= ， 并且A 是文法中的一个 产生式，那么我们说v可以直接推导到w，或者w可以直接规约到v。记作 v,w。 其中，（V,N,V,T,）*,推导,：若v= ,0,1,2,n,= w (n0),则符号串w为符号串v的一个推导。记为v,+,w,v,*w含义: v=w或v ,+,w,18,例3 : G = (E, i, +, *, (, ) , P , E),P： E E + E | E * E | ( E ) | i,表达式(i),和(i+i)*i的推导：,E, (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,E E,0步推导,E (i + i)*i 6步推导 E (,i + i)*i 6步推导 E (E) 直接推导,19,句型、句子,对于文法GS， 称为G的一个,句型,，如果：,S,* ,开始符号是最简单的句型。,GS的一个句型被称为,句子,，如果：,V,T,*,也就是说句子是全部由,终结符号,组成的句型。,20,文法的语言,文法的,语言,：一个文法GS的语言，用L(GS)表示，定义如下：,L(GS) = | S,* 并且 ,V,T,*,一个文法的语言就是该文法的所有的句子的集合。,文法的语言是所有终结符号串所组成的集合的子集，一般是真子集。,文法和语言有如下关系：,给定一个文法,就能从结构上唯一的确定其语言,即: GL(G),给定一种语言,能确定其文法,但不唯一,即: LG1 或G2 或。,若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2)，则称文法G1和文法G2等价。,21,文法与语言举例,描述语言L=ba,n,| n=1的文法： S bA A aA | a,文法S AB A aA | a B bB | b描述的语言是： L=a,n,b,m,| m，n=1,22,文法与语言举例,已知文法GZ为：,Z aZb | ab,求该文法确定的语言。,已知语言为: L(G)=ab,n,a | n 1，构造产生该语言的文法。,23,思考题,=a，b，设计文法描述语言L=a,2n,，b,2n,| n=1,设计一个表示所有标识符的文法。,24,得到一个语言，是通过利用所有的侯选式推导出所有句子，构成一个集合。,但是一个句型到另一个句型(句子)的推导过程不是唯一的。,G = (E, i, +, *, (, ) , P , E),P： E E + E | E * E | ( E ) | i,表达式,(i+i)*i的推导过程,25,最左（右）推导,在推导之前确定推导的顺序，是对句子进行确定性分析所必须的。,最左（右）推导定义：在一个推导的过程中，如果每一步直接推导所被替换的总是最左（右）的非终结符号，那么这种推导称为最左（右）推导。,最右推导又称为规范推导。用规范推导得到的句型称为规范句型。,26,最左推导的例子,标识符文法GS:,SL| SD|SL, La|b|c|x|y|z, D0|1|2|7|8|9,最左推导：S,SD,SDD,LDD,aDD,a6D,a69,27,最右推导的例子,标识符文法GS:,SL| SD|SL, La|b|c|x|y|z, D0|1|2|7|8|9,最右推导：S,SD,S9,SD9,S69,L69,a69,28,递归规则与递归文法,递归规则是指那些在规则的右部含有与规则左部相同符号的规则。,例如：UxUy，右部含有与规则左部相同符号U，那么就是递归规则。,如果这个相同的符号出现在右部的最左端，则为左递归规则。 如 UUy,如果这个相同的符号出现在右部的最右端，则为右递归规则。如 UxU,29,若文法中至少包含一条递归规则,则称文法是直接递归的。,若文法中不含递归规则，但有推导过程,U=,+,xUy，所以该文法为间接递归文法。,递归文法使我们能用有穷的文法刻画无穷的语言。,30,语法树,用一张图来表示一个句型的推导，有助于理解句子语法结构的层次。,定义：设文法G=(V,N,V,T,P,S ),对于文法G的任意一个句型都存在一棵相应的语法树：,结点由符号组成。,根结点对应于开始符号。,只有非终结符号对应的结点有子结点。,一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。,31,语法树的例子,语法GS:,SAB,AaAb | ab,BcBd | cd,S,A,B,a,b,c,B,d,c,d,S=AB=abB=abcBd=abccdd,32,语法树的相关概念,结点：每个树的结点对应于一个符号。结点的名字就是该符号。,边：两个结点之间的连线。,根结点：没有边进入的结点。,分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）,子树：语法树的某个结点和它向下射出的部分。,33,语法树的相关概念,叶子/末端结点：没有向下射出的边的结点称为叶子/末端结点。在相对于句型的语法树中，叶子/末端结点可能是非终结符号。,34,用语法树表示上下文无关文法的推导,步骤1：根结点为开始符号。,步骤2：对于每一次推导,使用的规则U u，找出U对应的结点（此时应该是末端结点），从该结点向下画分支，子结点从左到右分别是u中从左到右的符号。,重复步骤2直到推导的最后一步。,在语法树的推导过程中，没有后代的端末结点自左至右排列起来就是一个句型,一棵语法树表示了一个句型很多可能的不同推导过程。,35,文法的二义性,定义：如果对于某文法的,一个句子存在两棵不同的语法树,，则该句子是二义性的。而该文法是二义性文法。,这里的二义性是指语法结构上的。,如果一个句子具有二义性，那么对这个句子的结构可能有多种正确的解释。通常情况下，句子的语义要通过其语法结构来定义，所以，二义性一般是有害的。,定理：文法的二义性是不可判定的。,36,文法二义性的例子,文法GE：EE + E | E * E | (E) | i,文法的句子:,i+i*i,，其语法树如下：,E,E,E,+,E,*,E,E,E,+,E,E,*,E,37,文法二义性的解决方法,对文法加以限制；,从语义解释方面加以限制。,38,IF语句文法如下：, IFTHEN,| IFTHEN ELSE,| ,说明该文法是二义性文法。,39,文法的实用限制,文法中不含形如P P的产生式。,文法中每个非终结符都有用。,必须存在含P的句型；,从S出发，存在推导：S=*,P,对于P不存在永不终结的回路。,必须存在终结符串V,T,*,使得P=,40,文法的化简和改造,无用符号和无用产生式的删除,产生式的消除,单产生式的消除,41,文法和语言的Chomsky分类,Chomsky文法根据对产生式的不同限制，可分为四类：0型，1型，2型，3型。我们主要用2型和3型文法。,42,0型文法/PSG(Phrase Structure Grammar ),0型文法的产生式：, ,，, （V,N,V,T,）,+,且至少含一V,N, （V,N,V,T,）*,相应语言称为0型语言，又称为递归可枚举集合。,43,1型文法/CSG(Context Sensitive Grammar ),1型文法的产生式：,1,A,2,1,2,，,其中A V,N,， ,1, ,2, (V,N,V,T,)* , (V,N,V,T,),+,。 ,1, ,2,为上下文。,1型文法也可以如下定义：所有的规则的右部都比左部长。,44,2型文法/CFG(Context Free Grammar ),2型文法的产生式：,A ,，其中A V,N, （V,N,V,T,）* 。,2型文法又称为上下文无关文法。,一般的程序设计语言的语法都使用2型文法描述。,2型文法的例子：S ab|aSb,45,3型文法/RG(Regular Grammar),文法产生式：（1）,Aa或者AaB,（2）,Aa或者ABa,其中A，B V,N,，aV,T,。,3型文法又称为右（左）线性文法，正则文法，其语言也称为正则语言。,3型文法的例子：S 0|1|1A|2B,A 1A|0B,B 0|1|0B,46,语言的层次,这四种语言可被4种自动机识别：,0型图灵机 1型线性界限自动机,2型下推自动机,3型有穷自动机,从外到内，四种文法对产生式的限制越来越多，语言的描述能力越来越弱,47,正规文法的描述能力比上下文无关文法的描述能力弱,正规文法只能用于描述单词的构成,上下文无关文法有足够的能力描述现今大多数程序设计语言的语法结构,例,L(G3) = a,n,b,n,|n,1,a,b的个数相同, 不能由任何正规文法产生，可以由下述上下文无关文法产生。,S -aSb,S -ab,同样，上下文无关语言的描述能力比上下文有关语言的描述能力弱。,48,例:G =(Vn,Vt,P,S)P:S-aSBE S-aBE EB-BEaB-ab bE-bb bE-beeE-ee,是一个上下文有关文法,49,小结,文法及语言的形式定义,递归规则与递归文法,语法树与二义文法,文法的分类,50,