前后文无关文法和语言

1、1第二章第二章 前后文无关文法和语言前后文无关文法和语言n语言文法概述语言文法概述n文法和语言的形式定义文法和语言的形式定义n文法的类型文法的类型n上下文无关文法及其语法树上下文无关文法及其语法树n句型的分析句型的分析n有关文法实用中的一些说明有关文法实用中的一些说明第第2章章 前后文无关文法和语言前后文无关文法和语言本章目的本章目的 为语言的语法描述寻求工具。为语言的语法描述寻求工具。 通过该工具，可以：通过该工具，可以：y掌握掌握对源程序给精确无二义（严谨、简洁、易对源程序给精确无二义（严谨、简洁、易读）读）的语法描述手段之一的语法描述手段之一-文法。文法。y根据语言文法的特点来指导语法分

2、析的过程根据语言文法的特点来指导语法分析的过程y从描述语言的文法可以自动构造出可用的分析从描述语言的文法可以自动构造出可用的分析程序程序y制导语义翻译制导语义翻译第第2章章 前后文无关文法和语言前后文无关文法和语言本章难重点本章难重点 关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。形式是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。第第2章章 前后文无关文法和语言前后文无关文法和语言第第2章章 前后文无关文法和语言前后文无关文法和语言文法及语言的表示 当我们表述一种语言时，无非是说明这种语言的句子（句子句

3、子：一定字符集（称字母表）上的一字符一定字符集（称字母表）上的一字符串串），如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构（也就是各种属性的单词所允许的排列规则），比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则： 第第2章章 前后文无关文法和语言前后文无关文法和语言“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工

4、人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 第第2章章 前后文无关文法和语言前后文无关文法和语言 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。第第2章章 前后文无关文法和语言前后文无关文法和语言英语句子sentence subject This | Computers | Iverb-phrase | adverb neververb is | run | am | tellobject t

5、he | a | noun university | world | cheese | liesThis is a university.Computers run the world.I am the cheese.I never tell lies.第第2章章 前后文无关文法和语言前后文无关文法和语言语言概述语言概述n 语言是由句子组成的集合，是由一组记号所构成的语言是由句子组成的集合，是由一组记号所构成的集合。集合。n 汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体n 英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体n 程序设计语言程序设计语言-所有

6、该语言的程序的全体所有该语言的程序的全体 语法语法：每个句子构成的规律：每个句子构成的规律n 研究语言研究语言 语义语义：每个句子的含义：每个句子的含义 语用语用：每个句子和使用者的关系：每个句子和使用者的关系第第2章章 前后文无关文法和语言前后文无关文法和语言研究程序设计语言 语法：每个程序构成的规律 语义：每个程序的含义1、 - 表示构成语言句子的各个记号之间的组合规律。语法包括：词法规则和语法规则 例如：C语法规定了构成条件语句的各个记号的组合规律为：第一个单词（记号）必须是”if”，然后是单词”(”、表达式，.。2、 - 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）

7、 对一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。离开语义，语言只不过是一堆符号的集合。 所谓一个语言的语义是这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。 阐明语义要比阐明语法难的多，现在还没有一种形式系统描述语义。第第2章章 前后文无关文法和语言前后文无关文法和语言 例如：我们根据例如：我们根据C C语法可以判断出声明语句语法可以判断出声明语句”intint i=999;” i=999;”是正确的，但是无法判断出声明语句是正确的，但是无法判断出声明语句”intint i=9999999;” i=9999999;”是是错误的，因为该

8、语句的语法没有错误（即单词的排列顺序是错误的，因为该语句的语法没有错误（即单词的排列顺序是对的），其错误是因为数值对的），其错误是因为数值99999999999999超过了整型变量的最大超过了整型变量的最大允许值。这个错误就需要语义检查才能发现。允许值。这个错误就需要语义检查才能发现。 如果不考虑语义，即只从语法这一侧面来看语言，这种意如果不考虑语义，即只从语法这一侧面来看语言，这种意义下的语言称作义下的语言称作形式语言形式语言。形式语言抽象地定义为一个数学。形式语言抽象地定义为一个数学系统。系统。“形式形式”是指这样的事实：语言的所有规则只以什么是指这样的事实：语言的所有规则只以什么符号串能

9、出现的方式来陈述。形式语言理论是对符号串集合符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。研究的基础。第第2章章 前后文无关文法和语言前后文无关文法和语言有关定义和记号有关定义和记号符号符号：可以相互区别的记号（元素）。：可以相互区别的记号（元素）。字母表字母表 ：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。符号串符号串：由字母表：由字母表 中的符号组成的任何有穷序列中的符号组成的任何有穷序列称为该字母表上的符号串。称为该字母表上的符号串。1.1.空符号串空符

10、号串(没有没有符号的符号串符号的符号串) )是是 上的符号串上的符号串 2.2.若若x x是是 上的符上的符号串号串,a,a是是 的元素的元素, ,则则xaxa是是 上的符号串上的符号串 3.3. y y是是 上的符号串上的符号串, ,当且仅当它可以由当且仅当它可以由1 1和和2 2导出。导出。 例如：例如： =a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串第第2章章 前后文无关文法和语言前后文无关文法和语言 符号串符号串s s的头（的头（前缀前缀）：移走符号串）：移走符号串s s尾部尾部的零个或多于零个符号得到的符号串的零个或

11、多于零个符号得到的符号串. . 如：如：b b是符号串是符号串bananabanana的一个前缀的一个前缀. . 符号串符号串s s的尾（的尾（后缀后缀）：删去符号串）：删去符号串s s头部头部的零个或多于零个符号得到的符号串的零个或多于零个符号得到的符号串. . 如如:nana:nana是符号串是符号串bananabanana的一个后缀的一个后缀. . 符号串符号串s s的的子串子串：从：从s s中删去一个前缀和一中删去一个前缀和一个后缀得到的符号串个后缀得到的符号串. . 如如: :anaana是符号串是符号串bananabanana的一个子串的一个子串. .第第2章章 前后文无关文法和语

12、言前后文无关文法和语言符号串的运算符号串的运算符号串的符号串的长度长度：符号串中符号的个数：符号串中符号的个数. .符号串符号串s s的长的长度记为度记为| |s|s|。 的长度为的长度为0 0连接连接：符号串：符号串x x、y y的连接的连接, ,是把是把y y的符号写在的符号写在x x的符号的符号之后得到的符号串之后得到的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a = a a = a 方幂方幂：符号串自身连接：符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaaaa aa n n个个a aa

13、 a1 1=a, a=a, a2 2=aa=aa则则a a0 0=符号串符号串集合集合：若集合：若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符号串，则称的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。第第2章章 前后文无关文法和语言前后文无关文法和语言两个符号串集合两个符号串集合A A和和B B的乘积定义为的乘积定义为 AB =AB = xyxy|x|x A A且且y y B B 若集合若集合A=A= ab,cdeab,cde ，B B = = 0,10,1 则则 ABAB = = ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1

14、使用使用 * *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集）组成的集合。合。* *称为称为的的闭包闭包。 上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为 + + 。+ +称为称为的的正闭包正闭包。.2*.32*第第2章章 前后文无关文法和语言前后文无关文法和语言例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,第第2章章 前后文无关文法和语言前后文无关文法和语言语言语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言

15、是*的一个子集)。例如：字母表=a,b , *=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。 是一个语言。 即 是一个语言。第第2章章 前后文无关文法和语言前后文无关文法和语言文法和语言的形式定义 如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的如果

16、语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：有穷表示有两个途经： - - 生成方式生成方式 （文法文法）：语言中的每个句子可以用）：语言中的每个句子可以用严格定义的规则来构造。严格定义的规则来构造。 - - 识别方式（识别方式（自动机自动机）：用一个过程，当输入的一）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停任意串属于语言时，该过程经有限次计算后就会停止并回答止并回答“是是”，若不属于，要么能停止并回答，若不属于，要么能停止并回答“不是不是”，（要么永远继续下去。），（要么永远继续下去。） 第第2章章 前后文无关文法和语言前后文无关文法和语言文法是程序

17、语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.第第2章章 前后文无关文法和语言前后文无关文法和语言文法和语言的形式定义文法和语言的形式定义n文法的定义文法的定义n推导的定义推导的定义n句型、句子、语言的定义句型、句子、语言的定义第第2章章 前后文无关文法和语言前后文无关文法和语言文法的定义文法

18、的定义文法文法G定义为四元组（定义为四元组（VN，VT，P，S） VN ：非终结符集：非终结符集 VT ：终结符集：终结符集 P：产生式（规则）集合：产生式（规则）集合 S：开始符号：开始符号VNVT= ， SSVNV=V=VNVT，称为文法，称为文法G G的文法的文法符号集合符号集合第第2章章 前后文无关文法和语言前后文无关文法和语言文法文法G定义为四元组定义为四元组(VN，VT，P，S )，其中 VN为非终结符号(或语法实体，或变量)集； VT为终结符号集； P为产生式(也称规则)的集合； VN，VT和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左

19、部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表第第2章章 前后文无关文法和语言前后文无关文法和语言规则的定义规则的定义n规则（重写规则、产生式或生成式），规则（重写规则、产生式或生成式），是形如是形如或或=的（的（，）有）有序对，且序对，且VV+ +，VV* *。 称为规则的左部称为规则的左部( (或生成式或生成式的左部的左部) )。 称为规则的右部称为规则的右部( (或生成式或生成式的右部的右部) )。第第2章章 前后文无关文法和语言前后文无关文法和语言文法的定义文法的定义n例：文法例：文法G=（VN，VT，P，S） VN = S ,

20、VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号第第2章章 前后文无关文法和语言前后文无关文法和语言 是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。第第2章章 前后文无关文法和语言前后

21、文无关文法和语言 文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。 产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有： P1 P2 Pn 为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成 P1 2 n 其中，每个i(i=1,2,n)称为P的一个候选式，直竖“ ”读为“或”，它与“”一样是用来描述文法的元语言符号(即不属于的字符)。第第2章章 前后文无关文法和语言前后文无关文法和语言

22、例例 文法文法G=（VN，VT，P，S） VN =标识符，字母，数字标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z z 0,0, , 99 S=第第2章章 前后文无关文法和语言前后文无关文法和语言例:试构造产生标识符的文法。解答首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有： La b z D0 1 9 TL D 其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有 ST ST 其中，产生式ST ST是一种左递归形式，由它可以产生一串T。第第2

23、章章 前后文无关文法和语言前后文无关文法和语言 最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即 IL LS 因此，产生标识符的文法GI为： G=(a,b,z,0,9,I,S,T,L,D,P,I) P:IL LS ST ST TL D La b z D0 1 9第第2章章 前后文无关文法和语言前后文无关文法和语言例:写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。解答根据题意，我们可以将奇数划分为如图21所示的三个部分，即最高位允许出现19，用非终结符B表示；中间部分可以出现任意多位数字09，每一位用非终结符D表示；最低位只允许出现1、3、5、7、

24、9等奇数，用A表示。第第2章章 前后文无关文法和语言前后文无关文法和语言图21 奇数划分示意MB最高位中间位DDDA最低位第第2章章 前后文无关文法和语言前后文无关文法和语言 由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法GN为： G=(0,1,9,N,A,M,B,D,P,N) P:N NA MA/*一位数字多位数字*/ M MB MD/*仅两位数字(无中间位)多于两位数字*/ A A1 3 5 7 9 B B1 2 3 4 5 6 7 8 9 D D0 B第第2章章 前后文无关文法和语言前后文无关文法和语言推导推导 推导把产生式看

25、成重写规则，把符号串中的非终结符用其产生式右部的串来代替。亦即：从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。第第2章章 前后文无关文法和语言前后文无关文法和语言“我是大学生”的推导过程 开始先找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子 主语谓语 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词， 那么得到：主语谓语 代词谓语， 重复做下去. 句子：“我是大学生”的全部动作过程是：句子 主语谓语 代词谓语 我谓语 我动词直接宾语

26、我是直接宾语 我是名词 我是大学生 第第2章章 前后文无关文法和语言前后文无关文法和语言 实际上，推导过程就是对所要分析的句子进行断句（语法分析）的过程。 例如，句子“我是大学生 ”如果符合句子的规则，则其在语法结构上必然是由两部分组成的：前一部分是主语，后一部分是谓语；又因为主语是由代词或名词组成的，所以符合上述文法的句子的前缀必是代词或名词。这样，如果所要识别的字符串的第一个单词不是或，则该句子不符合文法；否则，继续判断其后续子串是否符合谓语的语法. 第第2章章 前后文无关文法和语言前后文无关文法和语言推导的定义推导的定义直接推导“”是文法G的产生式，若有v,w满足：v=,w= , 其中V

27、*,V*则称v直接推导到w,记作 v w 或w直接归约到v其中“”表示直接推导出，是应用产生规则进行推导的记号。注意“”与“”不同，“”是产生式中的定义记号。直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换，从而得到。我们给出推导的说明如下： 第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：G G： S0S1S0S1， S01S01 S S 0S1 0S1 00S11 00S11 000S111 000S111 0000111100001111 句子 主语谓语 代词谓语 我谓语我动词直接宾语 我是直接宾语 我是名词 我是大学生第第2章章 前后文无关文法和语言前后文

28、无关文法和语言(1)如果1可直接推出2，2可直接推出3，n-1可直接推出n，即存在一个自1至n的推导序列：123n(n0)，则我们称1可推导出n，记为1 n，它表示从1出发经过一步或若干步可推导出n。(2)如果记1 1，则表示从1出发，经过0步或者若干步可推导出n；也即1 n意味着或者1 n，或者1 n。推导的定义推导的定义第第2章章 前后文无关文法和语言前后文无关文法和语言例如，对下面的文法GE： EE+E E*E (E)i(3.1)其中，惟一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发进行一系列的推导，如表达式i+i*i的推导如下： EE+EE+E*E E+E*iE+i*ii

29、+i*i第第2章章 前后文无关文法和语言前后文无关文法和语言文法的句型、句子的定义文法的句型、句子的定义句型句型：有文法G，若S = x，则称x是文法G的句型。句子句子：有文法G，若S = x，且xVT*，则称x是文法G的句子。由定义可知，仅含终结符的句型是一个句子。开始符S本身只能是文法的一个句型而不可能是一个句子；此外，上面推导出的i+i*i是文法GE的一个句子(当然也是一个句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。例：G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001

30、111G的句子00001111, 01*第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：GGE E ： E EE+T|TE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a句子：用符号句子：用符号a a，+ +，* *，( (和和) )构成的算术表达式构成的算术表达式第第2章章 前后文无关文法和语言前后文无关文法和语言文法，语言的定义文法，语言的定义由文法由文法G G生成的生成的语言语言记为记为L

31、(G),L(G),它是文法它是文法G G的一的一切句子的集合切句子的集合: : L(G L(G)=x|S )=x|S = x x，其中，其中S S为文法的开始符号，且为文法的开始符号，且x xV VT T* * 例：例：G G： S S0S10S1， S S0101 L(G L(G)=0)=0n n1 1n n|n|n11*例 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 第第2章章 前后文无关文法和语言前后文无关文法和语言S a S BE (SaSBE) a aBEBE (SaBE) aab

32、EBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成第第2章章 前后文无关文法和语言前后文无关文法和语言使用产生式(1)n-1次，得到推导序列：S=an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaa

33、BBBEEE。即有： S =* anBnEn接着，使用产生式(4)一次，得到S = anbBn-1En，然后使用产生式(5)n-1次得到：S = anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S = anbnen 也能证明，对于n1，串anbnen是唯一形式的终结符号串 *第第2章章 前后文无关文法和语言前后文无关文法和语言n已知语言描述，写出文法已知语言描述，写出文法y例：若语言由例：若语言由0 0、1 1符号串组成，串中符号串组成，串中0 0和和1 1的个的个数相同，构造其文法。数相同，构造其文法。A 0B|1CA 0B|1CB 1|1A|0BBB 1|1A|0B

34、BC 0|0A|1CCC 0|0A|1CCn已知文法，写出语言描述已知文法，写出语言描述y例：例：GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a第第2章章 前后文无关文法和语言前后文无关文法和语言文法的等价文法的等价若若L(GL(G1 1)=L(G)=L(G2 2) )，则称文法，则称文法G G1 1和和G G2 2是等价的。是等价的。如文法如文法G G1 1AA：A0R A0R 与与G G2 2SS：S0S1 S0S1 等价等价 A01 SA01 S0101 RA1 RA1第第2章章 前后文无关文法和语言前后文无关文法和语言文法的类型文法的类型

35、语言学家NoamChomsky于1956年首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。第第2章章 前后文无关文法和语言前后文无关文法和语言 1、0型文法与0型语言(对应图灵机) 如果文法G的每一个产生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一个非终结符；V*；则称文法G为0型文法或短语文法，记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵(Turing)机。第第2章章 前后文无关文法和语言前后文无关文法和语言 2、1型文法与1型语

36、言(对应线性界限自动机，自然语言) 文法G的每一个产生式，均在0型文法的基础上增加了字符长度上满足 的限制，则称文法G为1型文法或上下文有关文法，记为CSG。1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。 1型文法的另一种定义方法是文法G的每一个产生式具有下列形式： A 其中，、V*，AVN，V+；显然它满足前述定义的长度限制，但它更明确地表达了上下文有关的特性，即A必须在、的上下文环境中才能被所替换。第第2章章 前后文无关文法和语言前后文无关文法和语言 3、2型文法与2型语言(对应下推自动机，程序设计语言) 文法G的每一个产生式具有下列形式： A 其中，AVN

37、，V*，则称文法G为2型文法或上下文无关文法，记为CFG。2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。第第2章章 前后文无关文法和语言前后文无关文法和语言 4、3型文法与3型语言(对应有限自动机) 文法G的每个产生式具有下列形式： Aa或AaB 其中，A、BVN，aVT*，则文法G称为3型文法、正规文法或右线性文法，记为RG。3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。 3型文法还可以呈左线性形式： Aa或ABa第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： S

38、SCDCDAbbAAbbA C CaCAaCABaBaaBaB C CbCBbCBBbbBBbbB AD ADaDaD CC BD BDbDbD DD Aa AabDbD第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABAB ABS|0BS|0 BSA|1SA|1第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：3 3型（正规）文法型（正规）文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0GI：I lTI lT lTT dTT lT d第第2章章 前后文无关文法和语言前后文无关文法和语言 四

39、类文法的关系与区别 由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。13型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。四类文法的区别如下： (1)1型文法中不允许有形如“A”的产生式存在，而2、3型文法则允许形如“A”的产生式存在； (2)0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。第第2章章 前后文无关文法和语言前后文无关文法和语言2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法第第2章章 前后文无关文法和语言前后文

40、无关文法和语言上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树-句型推导句型推导的的直观表示直观表示第第2章章 前后文无关文法和语言前后文无关文法和语言 例文法G=(E,+,*,i,(,),P,E)其中P为： Ei , EE+E , EE*E , E(E) E表示算术表达式, i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即： 变量是算术表达式；若E1和E2是算术表达式，则E1+ E2，E1*E2和(E1)也是算术表达式 描述一种简单赋值语句

41、的产生式： 赋值语句i=E 描述条件语句的产生式： 条件语句if条件then语句 if条件then语句else语句第第2章章 前后文无关文法和语言前后文无关文法和语言句型、推导 GE EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*Fa+F*F a+a*F a+a*a （对所给句子a+a*a推导序列中的每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换 ） EE+T E+T*F E+T*a E+F*a E+a*aT+a*a F+a*a a+a*a （对所给句子a+a*a推导序列中的每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换 ）E

42、E+T T+T T+T*F F+T*F F+F*Fa+F*F a+F*a a+a*a （推导序列中的每一步推导没有固定的替换规律 ）第第2章章 前后文无关文法和语言前后文无关文法和语言规范推导最左最左（最右最右）推导：在推导的任何一步,其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导规范推导。由规范推导所得的句型称为规范句型第第2章章 前后文无关文法和语言前后文无关文法和语言语法树 对程序语言来说，有两个问题需要解决： 其一是判别程序在语法上是否正确； 其二是句子的识别或分析。在编译方法中，为了便于识别或分析句子而引入了语法树这一重要的辅助工具。语法树以图示化的形式把句

43、子分解成各个组成部分来描述或分析句子的语法结构，这种图示化的表示与所定义的文法规则完全一致，但更为直观和完整。 第第2章章 前后文无关文法和语言前后文无关文法和语言 对文法G=(VT,VN,S,) ，满足下列条件的树称为GS的语法树： (1) 每个结点用GS的一个终结符或非终结符标记； (2) 根结点用文法开始符S标记； (3) 内部结点(指非树叶结点)一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、xn，则Ax1x2xn一定是文法GS的一条产生式； (4) 如果某结点标记为，则它必为叶结点且是其父结点的惟一子结点。第第2章章 前后文无关文法和语言前后文

44、无关文法和语言 相应于一个句型的语法树是以文法的开始符S作为根结点的，并随着推导逐步展开；当某个非终结符被它对应的产生式右部的某个候选式所替换时，这个非终结符所对应的结点就产生出下一代新结点，即候选式中从左至右的每一个符号都依次顺序对应一个新结点，且每个新结点与其父结点之间都有一条连线(树枝)。在一棵语法树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是一个句型。 构造语法树构造语法树第第2章章 前后文无关文法和语言前后文无关文法和语言EEEE*Eiii第一代第二代第三代第四代 图2-2 句子i+i*i的语法树 第第2章章 前后文无关文法和语言前后文无关文法和语言GE E：

45、 EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE + T E + T T E E + T T F第第2章章 前后文无关文法和语言前后文无关文法和语言上下文无关文法的语法树的用处上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的

46、结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。第第2章章 前后文无关文法和语言前后文无关文法和语言上下文无关文法的语法树上下文无关文法的语法树推导过程中推导过程中施用施用产生式产生式的的顺序顺序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第第2章

47、章 前后文无关文法和语言前后文无关文法和语言 一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢? 第第2章章 前后文无关文法和语言前后文无关文法和语言例：例：GE:GE:E E i iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推

48、导：推导推导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第第2章章 前后文无关文法和语言前后文无关文法和语言 在构造语法树时可以发现，一个句型的最左推导及最右推导只是决定先生长左子树还是先生长右子树，句型推导结束时相应的语法树也随之完成，这时已不能看出是先生长左子树还是先生长右子树，所呈现的只是已经长成的这个句子或句型的语法树，这与使用文法规则进行推导是有差异的，即使用文法规则的推导过程是有先后之分的。 第第2章章 前后文无关文法和语言前后文无关文法和语言二义文法二义文法文法GS的一个句子如果能找到两种不同的最

49、左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。例如，对文法GE，句子i+i*i存在着两种最左推导或最右推导，所形成的两棵不同的语法树如图23所示。第第2章章 前后文无关文法和语言前后文无关文法和语言EEEE*EiEEEE*Eiii(a)ii(b)图23 句子i+i*i的两棵不同语法树第第2章章 前后文无关文法和语言前后文无关文法和语言 再如，条件语句的文法GS为： GS: Sif B S Sif B S else S SA /*A指其它语句*/ 其中，VN = B,S,A，VT=if, else，则

50、句型if B if B S else S所对应的两棵不同语法树见图24。因此，文法GS是二义性文法。 第第2章章 前后文无关文法和语言前后文无关文法和语言SifS(a)(b)BSifSelseBSBSifSelseifSB图24 句型 if B if B S else S 的两棵不同语法树 第第2章章 前后文无关文法和语言前后文无关文法和语言 哪一个是正确的则取决于将单个else部分与第1个或第2个if语句结合：第1个分析树将else部分与第1个if语句结合；第2个分析树将它与第2个if语句结合。这种二义性称作悬挂else问题。 可生成带有两个不同分析树的串的文法称作二义性文法。由于这个文法并

51、不能准确地指出程序的语法结构，所以它是分析程序表示的一个严重问题。 第第2章章 前后文无关文法和语言前后文无关文法和语言解决二义性的基本方法有两个解决二义性的基本方法。其一是：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。这样的规则称作消除二义性规则。这样的规则的用处在于：它无需修改文法（可能会很复杂）就可消除二义性；它的缺点在于语言的语法结构再也不能由文法单独提供了。例如，我们强制规定else与最近的一个if匹配。另一种方法是通过重写文法而消除二义性，将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。 第第2章章 前后文无关文法和语言前后文无

52、关文法和语言 例如，可以把文法改写成下面无二义的文法。 stmt matched _stmt | unmatched_stmt matched_stmtif expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt 注意，unmatched_stmt的第二个产生式的右部if expr then matched_stmt else unmatched_stmt的matched_stmt 和和unm

53、atched_stmt是不能对调的，否则仍然是二义的。第第2章章 前后文无关文法和语言前后文无关文法和语言为什么文法中要保留二义性我们总希望一个文法是无二义性的，这样，句子的分析可以按惟一确定的方式进行。但是，文法的二义性是不可判定的，即不存在一种算法，能够在有限步内判定一个文法是否为二义性的。有时候，二义性文法也可带来一定的好处，如语法分析中二义性文法的应用，从而使文法保持了简洁性。定义语言语法的文法有二义并不可怕，只要有消除二义性的规则就可以了。第第2章章 前后文无关文法和语言前后文无关文法和语言句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型

54、句型，是某个，是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程程序序称为称为分析程序分析程序或或识别程序识别程序。分析算法又。分析算法又称称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识识别输入符号串别输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的一个符号，的一个符号，直直到分析结束到分析结束。第第2章章 前后文无关文法和语言前后文无关文法和语言句型的分析算法分类自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号

55、出发，反复使用文法的，反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。 第第2章章 前后文无关文法和语言前后文无关文法和语言两种方法反映了两种语法树的构造过程。两种方法反映了两种语法树的构造过程。自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树第第2章章 前后文无关文法

56、和语言前后文无关文法和语言自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd第第2章章 前后文无关文法和语言前后文无关文法和语言自下而上的语法分析自下而上的语法分析例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd第第2章章 前后文无

57、关文法和语言前后文无关文法和语言(1)S cAd (2) A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自上而下的语法分析自上而下的语法分析若S cAd 后选择(3)扩展A，S cAd cad那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配，宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。 S c A d a第第2章章 前后文无关文法和语言前后文无关文法和语言(1)S cAd (2) A ab (3)A a识别输入串识

58、别输入串w=cabd是否为该文法的是否为该文法的句子句子自下而上的语法分析自下而上的语法分析 对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子c a b d c A b d a第第2章章 前后文无关文法和语言前后文无关文法和语言句型分析的有关问题1 1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式产生式进行推导进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B B，且有，且有n n条规则：条规则：BA1|A2|BA1|A2|

59、An|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B B？2 2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约串识别可归约串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一选择一个个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约串可归约串”第第2章章 前后文无关文法和语言前后文无关文法和语言刻画刻画“可归约串可归约串”文法文法GSGS句型的短语句型的短语S S = A A且且 A A = ，则称，则称是是句型句型相对相对于非终结符于非终结符A A的的短语短语句型的直接短语句

60、型的直接短语若若有有A A ，则称，则称是句型是句型相对于非终结符相对于非终结符A A 的的直接短语直接短语句型的句柄句型的句柄一个句型的一个句型的最左直接短语最左直接短语称为称为该句型该句型的的句柄句柄*+第第2章章 前后文无关文法和语言前后文无关文法和语言一个有用的定理一个有用的定理n 定义：定义：由某一结点及其所属分支组成的部分树称为由某一结点及其所属分支组成的部分树称为原树的一颗子树。只有单层分支的子树称为简单子原树的一颗子树。只有单层分支的子树称为简单子树。树。n 定理：定理： 1.1.每个句型都有一颗语法树，每个语法树的叶组成每个句型都有一颗语法树，每个语法树的叶组成一句型。一句型