《上下文无关语法》PPT课件

《《上下文无关语法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1计算理论2主要内容2.1上下文无关文法概述2.1.1上下文无关文法的形式化定义2.1.2上下文无关文法举例2.1.3设计上下文无关文法2.1.4歧义性2.1.5乔姆斯基范式2.2下推自动机2.2.1下推自动机的形式化定义2.2.2下推自动机举例2.2.1与上下文无关文法的等价性2.3非上下文无关语言3上下文无关文法(CFG)概述A0A1ABB#替换规则变量(Variables)A,B终止符(Terminals)0,1,#起始变元(StartVariable)A箭头的左侧只有一个变量替换规则又称为产生式4

2、如何利用CFG产生字符串A0A1ABA#获取一个字符串的替换过程叫派生。例如字符串000#111的过程如下：A0A100A11000A111000B111000#111(1)写下起始变元——第一条规则左边的变元。(2)取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3)重复步骤2，直到写下的字符串没有变元。5如何利用CFG产生字符串A0A1ABA#可以用语法生成树形象地表示派生过程。AAAB#000111A6文法的语言A0A1ABA#文法G1可以产生

3、的字符串包括：#,0#1,00#11,000#111,…用文法生成的所有字符串的集合称为文法的语言。L(G1)表示文法G1产生的语言。L(G1)={0n#1n

4、n0}用上下文无关文法产生的语言叫上下文无关语言。文法G1的简写：A0A1

5、BB#7上下文无关文法的形式化定义定义2.1上下文无关文法是一个4元组(V,,R,S)，且(1)V是一个有穷集合，称为变元集。(2)是一个与V不相交的有穷集合，称为终结符集。(3)R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4)SV是

6、起始变元。8CFG的术语假设u与v由变元及终结符构成的字符串，Aw是文法的一条规则，称uAv生成uwv，记作uAvuwv。如果u=v，或者存在u1,u2,…,uk,k0使得uu1u2…ukv，则称u派生v，记作u*v。文法G=(V,,R,S)的语言为L(G)={w*

7、S*w}9上下文无关文法举例例2.1考虑文法G=({S},{a,b},R,S)，其中规则集R为：SaSb

8、SS

9、。该文法生成abab，aaabbb，aababb，…如果将a看作(，将b看作)，L(G)是所有正常嵌套的括

10、号字符串构成的语言。10设计上下文无关文法设计如下语言的上下文无关文法{0n1n

11、n0}∪{1n0n

12、n0}{0n1n

13、n0}{1n0n

14、n0}设计技巧化繁为简，利用正则，考察子串，利用递归。11设计上下文无关文法CFGforL1={0n1n

15、n0}S0S1

16、CFGforL2={1n0n

17、n0}S1S0

18、CFGforL1∪L2SS1

19、S2S10S11

20、S21S20

21、CFGforL3={02n13n

22、n0}?S00S111

23、12上下文无关文法与正则语言任何正则语言可以由CFG描

24、述。如果(qi,a)=qj，则增加规则VjaVi如果qi是接受状态，则增加规则Vi如果q0是起始状态，则V0是起始变元。q0q110start01DFACFGG=({V0,V1},{0,1},R,V0)V00V0

25、1V1

26、V11V1

27、0V013最左派生对于文法G中的一个字符串w的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。例如G=({S},{(,)},R,S)，其中规则为S(S)

28、SS

29、SSS(S)S()S()(S)()()SSSS(S)(S)(S)()

30、(S)()()14歧义性一个串可能有两个甚至更多的最左派生。例如CFGG=({S},{+,*,a},R,S)，其中规则为SS+S

31、S*S

32、a产生串a+a*aSS+Sa+Sa+S*Sa+a*Sa+a*aSS*SS+S*Sa+S*Sa+a*Sa+a*aSSSSS+aaaxSSSSSx+aaa15歧义性定义2.4如果字符串w在上下文无关文法G中有两个或两个以上不同的最左派生，则称G歧义地(ambiguously)产生字符串w，如果文法G歧义地产生某个字符串，则称G是歧义的。某些上下文无关语言只

33、能用歧义文法产生，这样的语言是固有二义的。16乔姆斯基范式定义2.5称一个上下文无关文法是为乔姆斯基范式(Chomskynormalform)，如果它的每一个规则具有如下形式：ABCAa其中a是任意的终结符，A、B和C是任意的变元，且B和C不能同时是起始变元。此外，允许规则S，其中S是起始变元。17乔姆斯基范式定理2.6任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法