上下文无关语言（精）

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

1、1形式语言与自动机第6章上下文无关语言2文法的乔姆斯基体系0型文法或短语结构文法αβ1型文法或上下文相关文法

2、β

3、≥

4、α

5、2型文法或上下文无关文法α∈V3型文法或正则文法Aw

6、wB3引言上下文无关文法和它所描述的上下文无关语言，在定义程序设计语言、语法分析、简化程序设计语言的翻译等方面有重要意义。高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。近年来，上下文无关文法也被用来描述文档格式：XML中使用的DTD(文档类型定义)就是用来描述Web上的信息交换格式的。4主要内容关于CFL的分析派生和归约、派生树CFG的化简无用符、单一产生式、空产生式CFG

7、的范式CNF、GNFCFG的自嵌套特性56.1上下文无关文法文法G=(V,T,P,S)被称为是上下文无关的，如果除了形如Aε的产生式之外，对于αβ∈P，均有

8、β

9、≥

10、α

11、，并且α∈V成立。关键：对于A∈V，如果Aβ∈P，则无论A出现在句型的任何位置，都可以将A替换成β，而不考虑A的上下文。例如：G：S→ABA→aA

12、aB→bB

13、b可以产生形如anbn或anbm的句子。6符号的使用约定回忆符号的使用约定A,B,C,…表示语法变量；a,b,c,…表示终极符号；X,Y,Z,…表示该符号是语法变量或者终极符号；x,y,z,…表示由终极符号组成的行；α,β,γ…表示由语法

14、变量和终极符号组成的行。7算术表达式的文法算术表达式的文法Gexp1：EE+T

15、E-T

16、TTT*F

17、T/F

18、FFF↑P

19、PP(E)

20、N(L)

21、idNsin

22、cos

23、exp

24、abs

25、log

26、intLL,E

27、E语法变量的含义E—表达式(expression)T—项(term)F—因子(factor)P—初等量(primary)N—函数名(nameoffunction)L—列表(list)id—标识符(identifier)↑—幂运算8算术表达式的文法算术表达式x+x/y↑2的不同派生EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x

28、/Fx+x/F↑Px+x/P↑Px+x/y↑Px+x/y↑2EE+TE+T/FE+T/F↑PE+T/F↑2E+T/P↑2E+T/y↑2E+F/y↑2E+P/y↑2E+x/y↑2T+x/y↑2F+x/y↑2P+x/y↑2x+x/y↑2EE+TT+TT+T/FF+T/FF+T/F↑PP+T/F↑Px+T/F↑Px+F/F↑Px+F/F↑2x+F/P↑2x+P/P↑2x+P/y↑2x+x/y↑29算术表达式的文法文法Gexp1句子x+x/y↑2的结构。10派生树(derivationtree)设有CFGG=(V,T,P,S)，G的

29、派生树是满足如下条件的(有序)树(orderedtree)：(1)树的每个顶点有一个标记X，且X∈V∪T∪{ε}。(2)树根的标记为S。(3)如果一个非叶子顶点v标记为A，v的儿子从左到右依次为v1,v2,…,vn，并且它们分别标记为X1,X2,…,Xn，则AX1X2…Xn∈P。(4)如果X是一个非叶子顶点的标记，则X∈V。(5)如果顶点v标记为ε，则v是该树的叶子，并且v是其父顶点的惟一儿子。11上下文无关文法的派生树别称生成树(derivationtree)、分析树(parsetree)、语法树(syntaxtree)顺序v1,v2是派生树T的两个不同顶点，如果存在顶点

30、v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。结果(yield)派生树T的所有叶子顶点从左到右依次标记为X1,X2,…,Xn，则称符号串X1X2…Xn是T的结果。一个文法可以有多棵派生树，它们可以有不同的结果。称“G的结果为α的派生树”为G的对应于句型α的派生树，简称句型α的派生树。12上下文无关文法的派生树派生子树(subtree)满足派生树定义中除了对根结点的标记的要求以外各条的树叫派生子树(subtree)。如果这个子树的根标记为A，则称之为A子树。惟一差别是根结点可以标记非开始符号

31、。13定理6-1定理6-1设CFGG=(V,T,P,S)，S*α的充分必要条件为G有一棵结果为α的派生树。先证一个更为一般的结论：对于任意A∈V，A*α的充分必要条件为G有一棵结果为α的A子树。充分性：设G有一棵结果为α的A子树，非叶子顶点的个数n施归纳，证明A*α成立。14定理6-1当n=0时，结论显然成立。当n=1时，该A子树是一个二级子树。假设此树的叶子顶点的标记从左到右依次为X1,X2,…,Xm，由定义6-1的第(3)条，必有AX1X2…Xm∈P。注意到该子树的结果为α，所以，X1X2…