形式语言 第6章 上下文无关语言ppt课件.ppt

《形式语言 第6章 上下文无关语言ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章上下文无关语言主要内容关于CFL的分析派生和归约、派生树CFG的化简无用符、单一产生式、空产生式CFG的范式CNFGNFCFG的自嵌套特性2021/7/311第6章上下文无关语言重点CFG的化简。CFG到GNF的转换。难点CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。2021/7/3126.1上下文无关语言文法G=(V，T，P，S)被称为是上下文无关的。如果除了形如Aε的产生式之外，对于αβ∈P，均有

2、β

3、≥

4、α

5、，并且α∈V成立。关键：对于A∈V，如果Aβ∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。2021/7/3136

6、.1.1上下文无关文法的派生树算术表达式的文法Gexp1：EE+T

7、E-T

8、TTT*F

9、T/F

10、FFF↑P

11、PP(E)

12、N(L)

13、idNsin

14、cos

15、exp

16、abs

17、log

18、intLL,E

19、E2021/7/3146.1.1上下文无关文法的派生树算术表达式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/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↑2E+F/y↑2E+P/y↑2E+x/y↑2T+x/y↑

20、2F+x/y↑2P+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↑22021/7/3156.1.1上下文无关文法的派生树文法Gexp1句子x+x/y↑2的结构。2021/7/3166.1.1上下文无关文法的派生树派生树(derivationtree)一棵(有序)树(orderedtree)树的每个顶点有一个标记X，且X∈V∪T∪{ε}树根的标记为S；如果非叶子顶点v标记为A，v的儿子从左到右依次为v1，v2，…，vn，并且

21、它们分别标记为X1，X2，…，Xn，则AX1X2…Xn∈P；如果X是一个非叶子顶点的标记，则X∈V；如果顶点v标记为ε，则v是该树的叶子，并且v是其父顶点的惟一儿子。2021/7/3176.1.1上下文无关文法的派生树别称生成树分析树(parsetree)语法树(syntaxtree)顺序v1，v2是派生树T的两个不同顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。2021/7/3186.1.1上下文无关文法的派生树结果(yield)派生树T的所有叶子顶点从左到右依次标记为X1，X2

22、，…，Xn，则称符号串X1X2…Xn是T的结果。一个文法可以有多棵派生树，它们可以有不同的结果。句型α的派生树：“G的结果为α的派生树”。2021/7/3196.1.1上下文无关文法的派生树派生子树(subtree)满足派生树定义中除了对跟结点的标记的要求以外各条的树叫派生子树(subtree)。如果这个子树的根标记为A，则称之为A子树。惟一差别是根结点可以标记非开始符号。2021/7/31106.1.1上下文无关文法的派生树定理6-1设CFGG=(V，T，P，S)，S*α的充分必要条件为G有一棵结果为α的派生树。证明：证一个更为一般的结论：对于任意A∈V，A*α的充分必要条件为G有

23、一棵结果为α的A-子树。充分性：设G有一棵结果为α的A-子树，非叶子顶点的个数n施归纳，证明A*α成立。2021/7/31116.1.1上下文无关文法的派生树设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，…，vm，并且它们分别标记为X1，X2，…，Xm。AX1X2…Xm∈P。以X1，X2，…，Xm为根的子树的结果依次为α1，α2，…，αm。X1，X2，…，Xm为根的子树的非叶子顶点的个数均不大于k。2021/7/31126.1.1上下文无关文法的派生树X1*α1X2*α2…Xm*αm而且α=α1α2…αm2021/7/31136.1.1上下文无关文法的

24、派生树AX1X2…Xm*α1X2…Xm*α1α2…Xm…*α1α2…αm2021/7/31146.1.1上下文无关文法的派生树2021/7/31156.1.1上下文无关文法的派生树必要性设Anα，现施归纳于派生步数n，证明存在结果为α的A-子树。设n≤k(k≥1)时结论成立，往证当n=k+1时结论也成立：令Ak+1α，则有：AX1X2…Xm*α1X2…Xm*α1α2…Xm…*α1α2…αm2021/7/31166