第四章文法和语言精选文档.ppt

《第四章文法和语言精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章文法和语言精选文档.ppt（105页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章文法和语言1本讲稿第一页，共一百零五页本章知识点本章知识点(内容内容)引言和预备知识文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法的句型分析上下文无关文法的句型分析有关文法实用中的一些说明有关文法实用中的一些说明2本讲稿第二页，共一百零五页文法的直观概念和语言概述语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来

2、说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：3本讲稿第三页，共一百零五页“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 4本讲稿第四页，共一百零五页有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子 主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词

3、，那么得到：主语谓语 代词谓语，重复做下去，句子：“我是大学生”的全部动作过程是：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 5本讲稿第五页，共一百零五页“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。6本讲稿第六页，共一百零五页英语句子sentencesubjectThis|Computers|Iverb-phrase|adverbneververbis|run|

4、am|tellobjectthe|a|noununiversity|world|cheese|liesThisisauniversity.Computersruntheworld.Iamthecheese.Inevertelllies.7本讲稿第七页，共一百零五页语言概述语言概述语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规

5、律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系8本讲稿第八页，共一百零五页研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics9本讲稿第九页，共一百零五页语法语法-表示构成语言句子的各个记号之间的表示构成语言句子的各个记号之间的组合规律组合规律语义语义-表示各个记号的特定含义。（各个记表示各个记号的特定含义。（各个记

6、号和记号所表示的对象之间的关系）号和记号所表示的对象之间的关系）语用语用-表示在各个记号所出现的行为中，它表示在各个记号所出现的行为中，它们的来源、使用和影响。们的来源、使用和影响。10本讲稿第十页，共一百零五页每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言言的的形式和该形式相关联的意义。形式和该形式相关联的意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个

7、个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用这两方面意义间的差异。用这两方面意义间的差异。11本讲稿第十一页，共一百零五页如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能能出出现现的的方方式式来来陈陈述述。形形式

8、式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析析研研究的基础。究的基础。12本讲稿第十二页，共一百零五页有关定义和记号有关定义和记号回顾回顾符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。符号串：由字母表符号串：由字母表 中的符号组成的任何有穷序中的符号组成的任何有穷序列称为该字母表上的符号串。列称为该字母表上的符号串。1.空符号串空符号串(没没有有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.

9、若若x是是 上的上的符号串符号串,a是是 的元素的元素,则则xa是是 上的符号串上的符号串 3.y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导出。导出。例如：例如：=a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串13本讲稿第十三页，共一百零五页有关定义和记号有关定义和记号回顾回顾 符号串符号串s的头（前缀）：移走符号串的头（前缀）：移走符号串s尾部的零尾部的零个或多于零个符号得到的符号串个或多于零个符号得到的符号串.如：如：b是符号串是符号串banana的一个前缀的一个前缀.符号串符号串s的尾（后缀）：

10、删去符号串的尾（后缀）：删去符号串s头部的零头部的零个或多于零个符号得到的符号串个或多于零个符号得到的符号串.如如:nana是符号串是符号串banana的一个后缀的一个后缀.符号串符号串s的子串：从的子串：从s中删去一个前缀和一个后中删去一个前缀和一个后缀得到的符号串缀得到的符号串.如如:ana是符号串是符号串banana的一个子串的一个子串.14本讲稿第十四页，共一百零五页对于每个符号串对于每个符号串s，s和和两者都两者都是符号串是符号串s的前的前缀，后缀和子串。缀，后缀和子串。符号串符号串s的真前缀，真后缀，真子串：任何非空的真前缀，真后缀，真子串：任何非空符号串符号串 x,相应地，是相应

11、地，是s的前缀，后缀或子串，的前缀，后缀或子串，并且并且 s x 符号串的运算符号串的运算符号串的长度：符号串中符号的个数符号串的长度：符号串中符号的个数.符号串符号串s的长度的长度记为记为|s|。的长度为的长度为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 naa n个个

12、a aa a1 1=a,a=a,a2 2=aa=aa则则a a0 0=15本讲稿第十五页，共一百零五页符号串集合：若集合符号串集合：若集合A中所有元素都是某字母中所有元素都是某字母表表 上的符号串，则称上的符号串，则称A为字母表为字母表 上的符号上的符号串集合。串集合。两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 AB=xy|xxy|x A A且且y y B B 若若 集合集合A=ab,cdeab,cde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使用 *表示表示 上的一切符号串（包括上的一切符号串（包括）组）组成的

13、集合。成的集合。*称为称为的闭包的闭包。上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。16本讲稿第十六页，共一百零五页例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,17本讲稿第十七页，共一百零五页有关定义和记号有关定义和记号语言语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个

14、子集)。例如：字母表=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 为字母表上的一个语言。是一个语言。即 是一个语言。18本讲稿第十八页，共一百零五页给出语言给出语言上上的有关运算的有关运算 设设L是（是（上的）一个语言上的）一个语言,M是（是（上的）一个语上的）一个语言言,语言语言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w is w|

15、w is in L or is in M in L or is in M 如：如：L1=a,b,=a,b,y,z My,z M1 1=1,2=1,28,9 8,9 L1 M1 1=a,b,=a,b,y,z y,z，1,21,28,9 8,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=st|sst|sL且且 t tM 如：如：L1M1=a1,b1,=a1,b1,y1,z1,a2,b2y1,z1,a2,b2a9a9z9 z9 有有L =L=L。L的的n次连接次连接Ln=LL.L 19本讲稿第十九页，共一百零五页语言语言上上的运算的运算 语言语言L的的 闭包闭包记记为

16、为 L*，L*=L0 L1 L2 .L0=，Ln=L Ln-1=Ln-1 L,n 1 语言语言L的正的正 闭包闭包记记为为 L+，L+=L1 L2 L3.L+=LL*=L*L L*=L+如：如：L1 =a,b,=a,b,y,z My,z M1 1=1,2=1,28,9 8,9 （L1 M1 1）=a,b,=a,b,y,z y,z，1,21,28,98,9 （L1 M1 1）*=a,b,=a,b,y,z y,z，1,21,28,98,9，aa,1a,xyz,6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符号所有字母打头的字母和数字符号串串 20本讲稿第二十页，共一百零五页文法和

17、语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：穷表示有两个途经：生成方式生成方式（文法）：语言中的每个句子可以用严格（文法）：语言中的每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式识别方式（自动机）：用一个过程，当输入的一任（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时

18、，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止并回答，若不属于，要麽能停止并回答“不不是是”，（要麽永远继续下去。），（要麽永远继续下去。）21本讲稿第二十一页，共一百零五页文法即是生成方式描述语言的：语言中的每文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造个句子可以用严格定义的规则来构造.下面下面给出文法的定义给出文法的定义.进而在进而在文法的定义的基础文法的定义的基础上上,给出给出推导的概念推导的概念,句型、句子和语言的定句型、句子和语言的定义义.22本讲稿第二十二页，共一百零五页定义定义文法G定义为四元组(VN，VT，P，S)其中VN为非

19、终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是 非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字汇表规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。23本讲稿第二十三页，共一百零五页Define a grammarDefine a grammarA A grammar G grammar G

20、is defined as a 4-tuple is defined as a 4-tuple(VN，VT，P，S)VN is a set of nonterminals VT is a set of terminals P is a set of productions，each production consists of a left side,an arrow(or:=),and a right side S is a designation of one of the nonterminals as the start symbolV=VN VT is the alphabet of

21、 G24本讲稿第二十四页，共一百零五页文法的定义文法的定义例例 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号25本讲稿第二十五页，共一百零五页例例 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=本讲稿第二十六页，共一百零五页文法的写法文法的写法 1 G1 G：SaASaAb Aab Aab AaA AaAb A A 2 GS 2 GS：Aab AaAAab AaAb A A SaSSaSb 3 GSGS：Aab|aAAab|aAb|Sa

22、S|SaSb27本讲稿第二十七页，共一百零五页元元符号:=|习惯表示习惯表示 大写字母：终结符大写字母：终结符 小写字母：非终结符小写字母：非终结符SABAAx|yBz本讲稿第二十八页，共一百零五页推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=,其中其中VV*,V,V*则称则称v v直接直接推导推导到到w,w,记作记作 v v w w 也称也称w w直接直接归约归约到到v v例：例：G G：S0S1，S01 0S100S1100S11000S111000S11100001111 S 0S129本讲稿第二十九页

23、，共一百零五页.VAR;BEGINREAD()END.VARA;BEGINREAD()END.30本讲稿第三十页，共一百零五页推导的定义推导的定义若存在若存在vw0w1.wn=w,(n0)则记为则记为v=+w，v推导出推导出w，或，或w归约到归约到v若有若有v=+w，或，或v=w，则记为则记为v=*w31本讲稿第三十一页，共一百零五页例：例：G G：S0S1，S010S100S1100S11000S111000S11100001111 S 0S100S11000S11100001111 S=+00001111 S=*S 00S11=*00S1132本讲稿第三十二页，共一百零五页What are

24、 DerivationsDerivation is a way that a grammar defines a language.In the process of derivation a production is treated as a rewriting rule in which the nonterminal on the left side is replaced by the string on the right side of the productionA production uvis used by replacing an occurrence of uby v

25、.Formally,if we apply a production p Pto a string of symbols win Vto yield a new string of symbols zin V,we say that zderived from wusing p,written as follows:w=p z.We also use:w=zzderives from w(production unspecified)w=*zzderives from wusing zero or more productionsw=+zzderives from wusing one or

26、more productions33本讲稿第三十三页，共一百零五页句型、句子的定义句型、句子的定义句型句型有文法有文法G，若，若S=*x，则称，则称x是文法是文法G的句型。的句型。句子句子有文法有文法G，若，若S=*x，且，且xVVT T*，则称，则称x是文法是文法G的句子。的句子。例：例：G G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,0134本讲稿第三十四页，共一百零五页例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE

27、 EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式35本讲稿第三十五页，共一百零五页文法，语言的定义文法，语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合:L(G)=x|S=*x，其中，其中S为文法的开始为文法的开始符号，且符号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n136本讲稿第三十六页，共一百零五页例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEb

28、e（7）eEeeL（G）=anbnen|n1 本讲稿第三十七页，共一百零五页S aSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成38本讲稿第三十八页，共一百零五页使用产生式(1)n-1次，得到推导序列：S=*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=*an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替

29、换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有：S=*anBnEn接着，使用产生式(4)一次，得到S=*anbBn-1En，然后使用产生式(5)n-1次得到：S=*anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=*anbnen 也能证明，对于n1，串anbnen是唯一形式的终结符号串 39本讲稿第三十九页，共一百零五页文法的等价文法的等价z若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G

30、 G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA140本讲稿第四十页，共一百零五页文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将将文法分为四种类型：文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T)+，(V(VN NVVT T)*1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|，仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N ，(V(VN NVVT T)*3 3型文法：型文法：任一产生式任一产生式的形式都为的形

31、式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T41本讲稿第四十一页，共一百零五页AhierarchyofgrammarsType0:free or unrestricted grammarsThese are the most general.Productions are of the form uvwhere both uand vare arbitrary strings of symbols in V,with unon-null.There are no restrictions on what appears on the left o

32、r right-hand side other than the left-hand side must be non-empty.Type1:context-sensitive grammarsProductions are of the form uXwuvwwhere u,vand ware arbitrary strings of symbols in V,with vnon-null,and Xa single nonterminal.In other words,Xmay bereplaced by vbut only when it is surrounded by uand w

33、.(i.e.in a particular context).42本讲稿第四十二页，共一百零五页Type2:context-free grammarsProductions are of the form Xvwhere vis an arbitrary string of symbols in V,and Xis a single nonterminal.Wherever you find X,you can replace with v(regardless of context).Type3:regular grammarsProductions are of the form Xaor

34、 XaYwhere Xand Yare nonterminals and ais a terminal.That is the left-hand side must be a single nonterminal and the right-hand side can be either a single terminal by itself or with a single nonterminal.These grammars are the most limited in terms of expressive power.43本讲稿第四十三页，共一百零五页文法的类型文法的类型例：例：1

35、 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD44本讲稿第四十四页，共一百零五页文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|145本讲稿第四十五页，共一百零五页3 3型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT

36、dTT l lT d d46本讲稿第四十六页，共一百零五页文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法47本讲稿第四十七页，共一百零五页文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（CF

37、 L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）48本讲稿第四十八页，共一百零五页文法和语言文法和语言 四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式做进一步限制而定义的。限制而定义的。语言之间的关系依次：有不是上下文有关语言之间的关系依次：有不是上下文有关语言的语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语型语言，有不是正则语言的上下文无关语言。言。49本讲稿第四十九页，共一百零五页根据形式语言理论根据形式语

38、言理论,文法和识别系文法和识别系统间有这样的关系统间有这样的关系 0型文法（短语结构文法）的能力相当于图型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且灵机，可以表征任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识。其识别系统是线性界限自动机。别系统是线性界限自动机。50本讲稿第五十页，共一百零五页带带a0a1a2a3a4a

39、5a6a7a8an-1an有限控制器有限控制器磁头磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述机上实现的计算都能用图灵机描述51本讲稿第五十一页，共一百零五页 2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生式）：产生式的形式为的形式为AA，取代取代A A时与时与A A的上下文无的上下文无关。其识别系统是不确定的下推自动机。关。其识别系统是不确定的下推自动机。3型文法（正规文法型文法（正规文法RG）：产生的语言是有）：产生的语言是有穷自动机（穷自动机（FA）所接受的集合）所接受的集合5

40、2本讲稿第五十二页，共一百零五页 3型文法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FA）所接受的）所接受的集合集合.定理定理 设设G=（VN，VT，P，S）是3 3型文法，则存在一个有穷自型文法，则存在一个有穷自 动机动机 M=(K,f,A,Z)M=(K,f,A,Z)，使得，使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造：=VT K=K=VN N,NN,N为一个新状态为一个新状态,它不在它不在VN中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DtBDtB的产生式的产生式,t,t为终结符或为终结符或,有有f(

41、D,t)=Bf(D,t)=B；对对G G中形如中形如DtDt的产生式，的产生式，t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=N;对对VT中的每一个a,有有f(N,a)=f(N,a)=53本讲稿第五十三页，共一百零五页G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab54本讲稿第五十四页，共一百零五页定理定理 已知一有穷自动机M=(K,f,A,Z),存在有一个3型文法G=（VN，VT，P，S）,使得L(G)=L(M)G 的定义：VT=VN=K S=A 若 f(D,t)=B，则DtB在P中 若 f(D,t)=B，且B在

42、Z中，则Dt在P中55本讲稿第五十五页，共一百零五页G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb56本讲稿第五十六页，共一百零五页正规文法和正规式 对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)初始，VT=,S VN，生成正规产生式 Sr (R.1)对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R 2)对形如Arr1的正规产生式：ArB Ar1 BrB Br1 BVN (R 3)对形如Ar1r2的正规产生式:Ar1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VN57本讲稿第五十七页，共

43、一百零五页例 r=a(ad)Sa(ad)SaA A(ad)A(ad)B A B(ad)B B Gs:SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B58本讲稿第五十八页，共一百零五页正规文法和正规式 对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)AxB,By A=xy AxAy A=xy Axy A=xy59本讲稿第五十九页，共一百零五页正规文法和正规式Gs:SaA|a AaAadAd A(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a(ad)(ad)=a(ad)R=a(ad)60本讲稿第六十页，共一百零五页上下文无关文

44、法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语上下文无关文法有足够的能力描述程序设计语言的语法结构法结构语法树语法树-句型推导句型推导的的直观表示直观表示61本讲稿第六十一页，共一百零五页例文法G=(E,+,*,i,(,),P,E)其中P为：Ei ,EE+E ,EE*E,E(E)E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：赋值语句i=E描述条件语句的产生式：条件语句if条件th

45、en语句 if条件then语句else语句62本讲稿第六十二页，共一百零五页句型、推导GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a63本讲稿第六十三页，共一百零五页规范推导规范推导规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非

46、终结符进行替换的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型64本讲稿第六十四页，共一百零五页语法树语法树设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：语法

47、树的结果：从左到右读出叶子的标记而构成的行谓之65本讲稿第六十五页，共一百零五页语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能构的任何句型都能构造与之关联的语法树造与之关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有，有S=*，当且仅当，当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)66本讲稿第六十六页，共一百零五页构造语法树构造语法树GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+T

48、a+Ta+T*Fa+F*Fa+a*Fa+a*a E EE+T E +T T E E +T T F67本讲稿第六十七页，共一百零五页E EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a E E E+T E+T T T*F T T*F F F a F F a a a a a 看不出句型中的符号被替代的看不出句型中的符号被替代的顺序顺序68本讲稿第六十八页，共一百零五页上下文无关文法的语法树的用处用于描述上下文无关文法用于描

49、述上下文无关文法句型推导句型推导的的直观方法直观方法例例:GS:SaASASbAASSSaAbaSaASSbAaaba句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符法符号号串串，为，为GS的的句型句型。也把该推导树称为该。也把该推导树称为该句型句型的的语法树语法树。69本讲稿第六十九页，共一百零五页上下文无关文法的语法树上下文无关文法的语法树z推导过程中推导过程中施用施用产生式产生式的的顺序顺序例例:GS:SaASASbAASSSaAbaSaASS

50、bAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa70本讲稿第七十页，共一百零五页一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的(但但未必是所有的未必是所有的)不同推不同推导过导过程，包括最左程，包括最左(最右最右)推推导导。但是，一个句型是否只。但是，一个句型是否只对应对应唯一的一棵唯一的一棵语语法法树树呢呢?一个句型是否只有唯一个句型是否只有唯一的一个最左一的一个最左(最右最右)推推导导呢呢?71本讲稿第七十一页，共一百零五页例：例：GE:GE:E iE