编译原理2.3.3-文法类型.ppt

《编译原理2.3.3-文法类型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3.3形式语言鸟瞰一、文法的四种类型二、文法四种类型的包含关系三、文法四种类型的描述能力一、文法的四种类型乔姆斯基(Chomsky)产生式α→β,V=VN∪VTα∈V+,β∈V*对产生式施加不同的限制文法的四种类型:0型、1型、2型和3型文法0型文法1型文法2型文法3型文法0型文法(短语文法)－PSGPhraseStructureGrammarα→β,α∈V+,β∈V*α至少含有一个非终结符0型文法的能力相当于图灵机任何0型语言都是递归可枚举的；递归可枚举集必定是一个0型语言1型文法(上下文有关文法)CSGContext-SensitiveGrammar

2、定义1:每个产生式α→β均满足

3、α

4、≤

5、β

6、，(仅仅S→ε例外,但S不出现在其他产生式的右边)定义2:产生式的形式:αAβ→αγβ,γ≠ε即左部的一个非终结符在推导时,它左右的字符串必须保持原样.2型文法(上下文无关文法)Context-FreeGrammarCFG产生式的形式:A→βA∈VN，β∈V*2型文法一定满足1型文法的定义

7、A

8、≤

9、β

10、关于A→ε补充定理:有关上下文无关文法中的ε规则若L是由文法G产生的语言，G每个产生式的形式均为A→α，A∈VN，α∈V*,(α可为ε)则L能由这样的一种文法产生，即:每个产生式或者为A→β形式，β∈V＋或者为S→ε的

11、形式，且S不在任何产生式的右边3型文法(正规文法,正则文法)Aregulargrammar右线性文法:A→αB或A→α,αVT*左线性文法:A→Bα或A→α,αVT*3型文法的另一个定义右线性文法:A→aB或A→a,aVT左线性文法:A→Ba或A→a,aVT补充小结产生式:α→β,α∈V+,β∈V*0型:α→β,α∈V+,β∈V*α至少含有一个非终结符1型:α→β,α∈V+,β∈V*

12、α

13、≤

14、β

15、(仅S→ε例外,但S不出现在其他产生式的右边)2型:A→β,A∈VN，β∈V*3型:A→αB或A→α,αVT*二、文法四种类型的包含关系文法0型文法1型文法2

16、型文法3型文法G1:S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→aBD→bDD→bAa→bDG1是上下文有关文法请判断以下文法的类型补充例G2:S→aB,A→bAAS→bA,B→bA→a,B→bSA→aS,B→aBBG2是上下文无关文法补充例G3:S→0AA→1BS→1BB→1BS→0B→1A→0AB→0A→0SG3是正规文法补充例G4：I→lT

17、lT→lT

18、dT

19、l

20、d其中l表示a～z中的任何一英文字母，d表示0～9中的任一数字。G4是正规文法补充例三、文法四种类型的描述能力L(T3)L(T2)L(T1)L(T0)0型语言L(

21、T0)1型语言L(T1)上下文有关语言上下文无关语言正规语言3型语言举例L(T3)L={anbam

22、n,m≥1}G:S→aS,S→aB,B→bC,C→aC,C→a_____型文法补充例3L(T3)L(T2)存在一个语言是2型语言而非3型语言L(G)={anbn

23、n≥1}无法用正则文法描述G:S→aSb

24、abp34以下语言是____型语言L={anban

25、n≥1}G:S→aAa,A→aAa,A→b2补充例L(T2)L(T1)存在一个语言是1型语言而非2型语言L={anbmanbmccc

26、n,m≥1}无法用上下文无关文法描述补充例L={anbnci

27、n≥1,i≥

28、1}是上下文无关语言L={anbncn

29、n≥1}无法用上下文无关文法产生P35L(T1)L(T0)存在一个语言是0型语言而非1型语言L={αcα

30、α∈(a

31、b)*}只能用0型文法产生.P35补充:DecisionproblemDecisionproblem－判断一个符号串是否是一个语言的句子FullyDecidable－存在一个算法在有限时间内给出答案Semi-decidable(RecursivelyEnumerable)－存在一个算法,如果符号串是该语言的句子,将在有限时间内回答“是”－如果符号串不是该语言的句子,可能无法在有限的时间内给出答案补充:文法和

32、识别系统0型文法-图灵机1型文法-线性界限自动机2型文法-不确定的下推自动机3型文法-有穷自动机