编译原理-第二章形式语言基础.ppt

1,编译原理CompilerPrinciples,徐小龙xuxl南京邮电大学.计算机学院,第二章形式语言基础知识,教材：编译技术原理及其实现方法王汝传编著,2,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,3,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,4,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法,5,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法,6,2.1引言一、形式语言提出形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义即用数学方法（主要是代数方法）对语言进行形式化描述。语言非形式描述：人们交流思想的工具。从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言历史比较研究。1904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要掌握高等数学。1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。1946年电子计算机问世以来更加促使数学和语言学结合研究。,7,2.1引言一、形式语言提出,1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。为什么要提出形式语言呢？1.控制论出现，促使对语言的深入研究2.用计算机进行科技文献检索，自动作文摘要及其它信息处理时要求将自然语言转换成一定形式的信息。3.在计算机上从一种自然语言翻译成另一种自然语言也需要对语言进行形式描述，以便机器对其分析和综合。4.计算机编译理论、人工智能、数据库等需要对语言进行形式描述。,8,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法,9,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法,10,2.1引言二、语言描述方法无论是自然语言或者是程序设计语言，都是由许多句子组成，当然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的句子，哪些句子是不属于该语言的句子。,11,2.1引言二、语言描述方法我们可以用三种方法来描述语言，枚举法、文法生成法和自动机识别法：1.枚举法：如果一个语言仅含有有限个句子，就可以采用枚举法来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。2.文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。3.自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。,下面我们着重讨论用文法生成法来描述语言。,12,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,13,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,14,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,15,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,16,2.2用文法生成法对语言进行描述一、巴科斯范式BNF-BackusNormalForm例子：Thebigelephantatethepeanut.(大象吃花生）Thelittleboyranquickly.(小男孩跑得快）Themanhasadog.(这人有一条狗）以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。如何描述一个给定的句子在给定规则下是否成立呢？我们以“=”符号(或“”符号)表示”定义为”，以“|”符号表示“或”，以“”符号表示语法实体(语法单位)，这些符号是元语言符号，,17,句子=主语谓语主语=冠词形容词名词冠词=the形容词=big谓语=动词宾语动词=ate宾语=冠词名词名词=elephant|peanut我们把这种描述语法规则方法称巴科斯范式，也称巴科斯-瑙尔范式(BackusNormalForm)，简称BNF。,那么上面叙述的语法规则可写为：,18,步骤推导所用规则1谓语2形容词名词谓语3the形容词名词谓语4thebig名词谓语5thebigelephant谓语6thebigelephant动词7thebigelephantate8thebigelephantate冠词9thebigelephantatethe10thebigelephantatethepeanut可见句子thebigelephantatethepeanut成立。当然我们还可以推导出其它的句子，如thebigpeanutatetheelephant，在这里，我们只考虑句子的语法，而不考虑句子的语义。,根据以上规则，可以推导出句子Thebigelephantatethepeanut.过程如下：,19,巴科斯范式是描述语法规则一种表示方法,它是由巴科斯为了在ALGOL60报告中来描述ALGOL语言首先提出的。采用这种形式体系方式定义语法规则,可以用简洁的公式把各种语法规则严格而清晰描述出来。例如,在高级语言中大家所熟知的标识符这种语法成分,它用巴科斯范式描述为:标识符=字母|标识符字母|标识符数字而字母=A|B|C|D|Z数字=0|1|2|9这样便刻画出了标识符是以字母开始的一串字母和数字任意组合这种特点。,20,用巴科斯范式描述语言能给研究问题带来很大方便。如下面9个句子都是正确的：WeranHeranIranWeateHeateIateWesatHesatIsat如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。句子=主语谓语主语=We|He|I谓语=ran|ate|sat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。,21,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,22,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,23,2.2用文法生成法对语言进行描述二、语法和语义1.语法用类似巴科斯范式来描述某种语言，称为该语言的语法（也称文法）。实际上语法是在字母表上构造句子的一组规则。对于自然语言就是造句的规则；对于程序设计语言就是书写程序规则。,24,2.2用文法生成法对语言进行描述二、语法和语义2.语义语义是按照语法规则所构成结构的含义。对于自然语言，语义是所要表达的意思；对于程序设计语言，语义是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子语法上正确不等于语义上也是正确的。例如，“Thebigpeanutatetheelephant”在语法上是正确，在语义上是荒谬的。在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加以说明则是语义。对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还没能形式化，还得借助于自然语言。,25,编译程序如何将源程序变成目标程序？第一：就是语法分析，看源程序是否符合该语言的语法关系第二：就是语义分析，根据该语言语义生成目标代码这是两个核心问题。,2.2用文法生成法对语言进行描述二、语法和语义,26,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,27,第二章形式语言基础知识,2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义1.语法2.语义三、语法树,28,2.2用文法生成法对语言进行描述三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。,29,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,30,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,31,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,32,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,33,man,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,34,man,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,35,man,has,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,36,man,has,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,37,man,has,a,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,38,man,has,a,book,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,39,man,has,a,book,the,三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子themanhasabook的推导过程及对应的语法树,其中：称为语法树根带和不带的都称为语法树的结点一个结点以及向下射出部分称为子树没有向下射出部分的结点称为末端结点,40,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,41,第二章形式语言基础知识,2.1引言一、形式语言提出二、语言描述方法2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,2.4语法分析初步一、自顶向下语法分析二、自底向上语法分析2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法2.6文法其他表示法一、扩充巴科斯范式二、语法图,42,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,43,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,44,2.3形式语言基本概念和术语一、元语言1.元语言2.元语言变量,45,2.3形式语言基本概念和术语一、元语言1.元语言2.元语言变量,46,2.3形式语言基本概念和术语一、元语言1.元语言与编译有关的形式语言基本概念和术语：用来描述其它语言的语言，称元语言。被描述语言称对象语言。例如：英语教科书中，英语是对象语言，汉语是元语言。元语言与被描述语言可以是相同的，也可以是不同的。,47,2.3形式语言基本概念和术语一、元语言1.元语言2.元语言变量,48,2.3形式语言基本概念和术语一、元语言1.元语言2.元语言变量,49,2.3形式语言基本概念和术语一、元语言2.元语言变量元语言的词汇称为元语言的变量(或元语言的符号)。例如：在上一节中描述句子，我们用了等，这些符号的引入完全是为了描述英语句子thebigelephantatethepeanut.而这些引入符号并为出现在句子中，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。,50,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,51,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,52,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,53,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,54,2.3形式语言基本概念和术语二、符号和符号串1.字母表有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、或其它大写字母表示。例如V=a,b,c，V=,等都是字母表。|V|表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表=0,1，PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，(，)，=，等组成。注意：在一个语言中不能出现字母表以外的符号。,55,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,56,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,57,2.3形式语言基本概念和术语二、符号和符号串2.符号串（1）定义符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)例如：设V=a,b,c,则符号串有a,b,c,aa,ab,ac,ba,abc又如：设V=0,1,则符号串有0，1，00，01，10，11，000由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba，符号串01不同于10，今后我们常用t,u,v,x,y,z等小写字母表示符号串。（2）空符号串不包含任何符号的符号串称为空符号串，记为。（3）符号串长度符号串中所含符号个数称为该符号串的长度，设符号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|=0。,58,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,59,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,60,2.3形式语言基本概念和术语二、符号和符号串3.行集合字母表V上各种长度符号串构成行集合，记为V*，不包括空行的集合记为V+即V*=x|x是V上符号串且包括空符号串V+=x|x是V上符号串且不包括空符号串V+=V*-如：V=a,b，则V*=,a,b,aa,ab,ba,bb,aaa,bbb,V+=a,b,aa,ab,ba,bb,aaa,bbb,61,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,62,2.3形式语言基本概念和术语二、符号和符号串1.字母表2.符号串3.行集合4.关于行集合V*上几种运算,63,2.3形式语言基本概念和术语二、符号和符号串4.关于行集合V*上几种运算（1）联结设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即x=x1x2x3xm,y=y1y2y3yn则xy=x1x2x3xmy1y2y3yn显然x=x，x=x,64,（2）行集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为AB=xy|xA且yB由此定义，乘积AB是满足xA且yB的所有符号串xy所组成的集合。如：V=0，1V*=,0,1,00,01,10,11,000,001，010，011，100,101如果A=0，101B=10，11，110则AB=010，011，0110，10110，10111，101110,65,（3）符号串的方幂若XV*，是符号串则X0=，X1=X，X2=XX，X3=XXX，Xn=XXX(n个）如X=abc则X0=,X1=abc,X2=abcabcX3=abcabcabc（4）符号串集合的方幂设符号串集合AV*则A0=,A1=A,A2=AA,A3=AAA,An=AAAA(n个）如：设A=a,b，则A0=,A1=a,b，A2=a,ba,b=aa,ab,ba,bbA3=aaa,aab,aba,abb,baa,bab,bba,bbb,66,(5)闭包和正闭包设A为符号串集合，则A的正闭包定义为A+=A1A2An符号串集合A的闭包定义为A*=A0A+=A+如A=a,b则A+=a,baa,ab,ba,bb=a,b,aa,ab,ba,bb,aaa,bbb,A*=,a,b,aa,ab,ba,bb,aaa,bbb,我们可以证明：A+=AA*=A*AAA*=A（A0A1A2An）=A1A2An=A+,67,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,68,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,69,2.3形式语言基本概念和术语三、产生式（规则）1.定义2.字汇表,70,2.3形式语言基本概念和术语三、产生式（规则）1.定义2.字汇表,71,2.3形式语言基本概念和术语三、产生式（规则）1.定义产生式(规则)就是一个符号与另一个符号串的有序偶(U,x),通常记为Ux或U=x其中：U是符号,x是有限非空符号串。U称为规则的左部,x称为规则的右部如果Ux1，Ux2，Ux3，Uxn可以写成Ux1|x2|xn,并称xi是U的一个候选式。,72,2.3形式语言基本概念和术语三、产生式（规则）1.定义2.字汇表,73,2.3形式语言基本概念和术语三、产生式（规则）1.定义2.字汇表,74,2.3形式语言基本概念和术语三、产生式（规则）2.字汇表,（1）定义用于规则左部和右部中所有符号形成集合为字汇表，记为V。,75,（2）分类1）非终结符号出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN2）终结符规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT。终结符一般出现在规则的右部。显然,V=VNVT,VNVT=,76,如：在PASCAL中，对标识符的定义规则为：标识符=|字母=a|b|z数字=0|1|9由此得：VN=字母,数字,标识符VT=a,b,z,0,1,9,（2）分类,77,例如：有产生式:S=0S1S=01则VN=SVT=0,1V=S,0,1,（2）分类,78,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,79,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,80,2.3形式语言基本概念和术语四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为G=(VN,VT,P,Z)其中：VN是非终结符集合,VT是终结符集合,P代表产生式集,ZVN是文法G开始符号,也称识别符号,它至少要在一条产生式左部出现。文法G通常记为GZ。,81,对于前面例子中用8条文法规则来描述英语句子,其文法可表示为G=(VN,VT,P,Z)其中:VN=，,VT=the,big,elephant,peanut,ateP是前述8条规则Z=句子,2.3形式语言基本概念和术语四、文法,82,又例如：标识符文法可定义如下:GZ=(VN,VT,P,Z)VN=字母,数字,标识符VT=a,b,z,0,1,9P由下列规则组成:标识符=|字母=a|b|z数字=0|1|9Z=标识符,2.3形式语言基本概念和术语四、文法,83,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,84,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,85,2.3形式语言基本概念和术语五、推导和归约定义1设G为一个文法，U=u是G中一个规则，x和y是V*上符号串，使v=xUy与w=xuy则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v直接派生式，记作vw注意三点：1）v，w是两个不同符号串2）有一规则U=u3）直接推导vw若x=y=，则v=xUy=U，w=xuy=u可见vw即Uu说明一个规则就是一个直接推导例如句子直接推导到，而直接归约到。,86,例如:G=(VN,VT,P,S)VN=S,VT=0,1P:S=0S1S=01S=Z令v=xSy,w=x01y,因S=01(U=u)即vwxSyx01y若x=y=则S01(一个规则就是一个直接推导)同样S=0S1v=00S11，w=000S111Uu即vw00S11000S111,2.3形式语言基本概念和术语五、推导和归约,87,又如：标识符文法定义如下:GZ=(VN,VT,P,Z)VN=字母,数字,标识符VT=a,b,z,0,1,9P由下列规则组成:标识符=|字母=a|b|z数字=0|1|9Z=标识符则有：标识符a,从v出发应用规则U=u,把v=xUy中U替换为右部u,即v直接推导到w,这时长度可能增加,至少不会缩小:|w|v|。从w出发应用规则U=u,把w=xuy中u替换为左部U,即w直接归约为v,这时长度可能缩小,至少不会变:|v|w|。,88,定义2设u0,u1,u2,un均为V*上符号串,若w是v经过一系列直接推导得到的,即v=u0u1u2un-1un=w(n0)则称v推导到w,或称w归约到v,记作v+w称这个直接推导序列为长度为n的推导。如果v+w或者v=w(表示0步推导),则记作v*w称v广义推导到w或称w广义归约到v。显然,直接推导的长度为1,推导+的长度1,而广义推导*的长度0例如在前面的例子中,因S=0S1S=010S100S11000S11100001111所以0S1+00001111(n=3),89,例设有文法G整数:(1)=(2)=(3)=(4)=0(5)=1(6)=2(7)=3(8)=4(9)=5(10)=6(11)=7(12)=8(13)=9VwXUyxuy整数数字串规则1规则2数字数字规则3数字数字2数字规则62数字23规则7由此建立下列推导:223因此,+23,其推导长度为5。显而易见,在推导时,任意地选取规则(4)到(13),就可以推导得到任意整数。,90,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,91,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,92,2.3形式语言基本概念和术语六、句型和句子在上述推导过程中产生了一系列的符号串，它们或全由终结符组成（如：23），或全由非终结符组成（如：，），或由终结符和非终结符混合组成（如：2）。为了区别这些组成不同的符号串，我们引入句型和句子两个概念。定义：设GZ是一文法,若符号串x是由识别符Z推导而得,即Z*xxV*则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即Z*xxVT*则称句型x为该文法一个句子。例如在例2.16中,整数,数字数字,2数字,23等都是文法G的句型,其中仅23是句子。,可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。,93,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,94,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,95,2.3形式语言基本概念和术语七、语言设GZ为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G)(或记为L(G),即L(G)=x|Z*x且xVT*有时我们称这样定义的语言为形式语言，以区别于自然语言。上述公式包含两层意思：语言是句子集合，是VT*一个子集合，即VT中行集合子集。句子必须有该语言文法识别符推出。例如：GZ=(VN,VT,P,S)VN=SVT=0,1P:S=01,S=0S1S:识别符很容易推出：L（G）=0n1n|n1,96,又如：写一个文法，使其语言为偶整数集合。首先分析以下偶整数（1）偶整数最后一个数字应该是偶数字0，2，4，6，8（2）偶整数前面符号可以是+，-或不带符号由此得其文法应由下列规则组成：=|=0|2|4|6|8=1|3|5|7|9|=|=+|-所以文法可表示为：G=(VN,VT,P,)其中：VN=，VT=0，1，2，3，4，5，6，7，8，9，+，-,97,对于通常的程序设计语言其文法为:G程序=(VN,VT,P,程序)其中VN=程序,说明,语句,VT=0,1,9,a,z,-,(,),P=,说明=,语句=,L(G)=w|程序*w且wVT*由此可知,每一个w就是一个源程序，所谓PASCAL语言也就是所有PASCAL程序的集合。,98,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,99,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,100,2.3形式语言基本概念和术语八、递归文法构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G句子所描述的语言L(G句子)是有穷的，仅包含8个句子。但文法G整数所描述的语言L(G整数)是无穷的，它包含无穷多个句子，不难发现，两个文法其根本差别在于文法G整数有形如数字串=数字串数字的规则。在这个规则中左部和右部皆出现非终结符数字串。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。,101,2.3形式语言基本概念和术语八、递归文法1.定义2.说明,102,2.3形式语言基本概念和术语八、递归文法1.定义2.说明,103,2.3形式语言基本概念和术语八、递归文法1.定义对于一个文法,若有一个规则U=U,则称直接递归,若有规则U=U,则称直接左递归,若有规则U=U,则称直接右递归。若有推导式U+U,则称间接递归,若有推导式U+U,则称间接左递归,若有推导式U+U,则称间接右递归。非终结符U称递归非终结符。如果一个文法中至少含有一个递归非终结符,则将此文法称为递归文法。,例如：规则S=0S1是直接递归规则A=Aa是直接左递归规则B=aBB是直接右递归,104,例如：设有文法G的规则P为S=Qc|cQ=Rb|bR=Sa|a在这6条规则中,无直接递归规则,但有如下推导:QRbSabQcab所以Q+Qcab因此是间接左递归。显然，直接递归是间接递归一种特殊情况。,105,2.3形式语言基本概念和术语八、递归文法1.定义2.说明,106,2.3形式语言基本概念和术语八、递归文法1.定义2.说明,107,2.3形式语言基本概念和术语八、递归文法2.说明如果一个语言是无穷的，则描述该语言的文法必定是递归的。一般说，程序设计语言是无穷的，因此描述它们的文法必定是递归的。应当指出，从语法定义上角度来看，递归定义使文法的形式比较简练，给无限的语言有限的表示提供了一种可用的方法。然而在后面我们将会看到，文法的左递归性将会给某些语法分析方法的实现带来很大的麻烦。,108,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,109,2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性,第二章形式语言基础知识,110,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,111,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,112,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语定义：设GZ是一文法，w=xuy是其中一句型，若有Z*xUy,UVN且U+u,uV+则称u是一个相对于非终结符U、句型w的短语。若Z*xUy且Uu则称u是一个相对于非终结符U、句型w的简单短语。,113,例2.16设有文法G整数:(1)=(2)=(3)=(4)=0(5)=1(6)=2(7)=3(8)=4(9)=5(10)=6(11)=7(12)=8(13)=9VwXUyxuy整数数字串规则1规则2数字数字规则3数字数字2数字规则62数字23规则7由此建立下列推导:223,由定义可知：*，w=2所以+2，即2是相对于非终结符句型2的短语，而*，w=22所以2是相对于非终结符句型2的简单短语,114,例2.22设有文法GS=(S,A,B,a,b,P,S),其中P为S=ABA=Aa|bBB=a|Sb找出句型baSb的全部短语，简单短语，根据句型推导过程有SABbBBbaBbaSb由上可见，下式成立：S*baB且BSb所以子串Sb是相对于非终结符B，句型baSb的简单短语。同样有SABASbbBSbbaSb即S*bBSb且Ba子串a是相对于B，句型baSb的简单短语。还有S*Asb且A+ba即子串ba是相对于非终结符A，句型baSb的短语。对于句型baSb，再没有其它能产生新的短语推导了，所以句型baSb有短语ba简单短语a和Sb,115,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,116,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,117,2.3形式语言基本概念和术语九、短语和简单短语2、柄短语定义一个句型最左边的简单短语称为该句型的句柄(或柄短语)，而且句柄最左边的符号称句柄的头，句柄最右边的符号称句柄的尾。如上例句型baSb简单短语为a和Sb，由于a是最左简单短语，所以a又是句柄。,118,例如：设文法GSS=AA=B|A+BB=C|B*CC=|（A）现在我们看w=C+B*C句型SAA+BB+BC+BC+B*CS*C+BBB*CB*C是相对于B句型C+B*C的简单短语同样SAA+BB+BB+B*CC+B*CS*B+B*CBCC是相对于B句型C+B*C的简单短语。由于C在左边，所以C是句柄，柄头和柄尾都是C,119,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,120,2.3形式语言基本概念和术语九、短语和简单短语1.短语和简单短语2.柄短语3.再谈语法树,121,2.3形式语言基本概念和术语九、短语和简单短语3.再谈语法树前面我们曾利用语法树直观地描述句子语法结构关系，现在我们仍然借助于语法树进行句型和句子的推导，同时，利用它寻找短语和简单短语也是十分直观和方便的。（1）语法树形式定义设有文法G=（VN，VT，P，Z），满足下列条件的树即为一个语法树a.树中每一个结点都有标记，且该标记是VNVT中某一符号b.树根标记是识别符号c.若有一个结点至少有一个后继结点，则该结点标记必为非终结符d.若一个标记为U的结点，它有标记依次为X1，X2，X3，Xn的直接后继结点，则U=X1X2Xn必定是G的一条规则。,122,S,A,B,b,B,S,b,a,我们以例2.22文法GS为例，句型baSb的推导设有文法GS=(S,A,B,a,b,P,S),其中P为S=ABA=Aa|bBB=a|SbSABbBBbaBbaSb画出语法树如下图所示,123,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。,S,124,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。,S,A,B,125,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。,S,A,B,126,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。,S,A,B,b,B,127,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。,S,A,B,b,B,128,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。,S,A,B,b,B,a,129,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),其中B被替换成Sb(规则B=Sb)。,S,A,B,b,B,a,130,（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)