计算理论课件第三章.ppt

《计算理论课件第三章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章上下文无关文法与下推自动机ContextFreeGrammar(CFG)andPushDownAutomaton(PDA)上下文无关文法（CFG）在程序设计语言和编译原理中有着重要的应用，因为上下文无关文法可以用来阐述绝大多数的程序设计语言的句法结构。此外上下文无关语言也可以作为描述语言翻译方案的基础。本章重点讨论:CFG的简化CFG的两种范式下推自动机（PDA）的概念PDA与CFG之间的等价转换上下文无关语言运算的封闭性以及CFL的有关判定问题。3.1上下文无关文法的派生树(推导树)一个上下文无关文法中的一个句型的派生过程可以用—棵树来描述。【例3-1.1】给定文法G=({S,A

2、},{a,b},P,S)，其中P：SaAS

3、a,ASbA

4、ba

5、SS。句型aabbaa的派生过程就可以用一棵树来描述，如图3-1.1所示。将此树的叶结点符号从左到右读取下来构成的符号串就是aabbaa。S๐a๐A๐๐SS๐b๐๐Aa๐b๐๐a๐a图3-.11aabbaa的派生树1．派生树的定义设文法G=(ＶＮ,ＶＴ,Ｐ,S)是上下文无关文法,如果一棵有序树满足下面四个条件，则它是棵派生树：(1)它的每个结点标记的符号是(ＶＮ∪ＶＴ∪{ε})中的符号；(2)根结点标记开始变元S；(3)内结点标记的符号是变元，即是ＶＮ中的符号。(4)如果一个内结点标记为A，且X1,X2,…,Xk是A的从

6、左到右的所有子结点,则AX1X2…Xk是P中一个产生式。(5)如果一个结点标记符号是ε，则它是其父结点的唯一儿子结点。其中第(5)条是为了防止下面情况发生：如产生式Aa(a是个终极符)被误认为是Aaε或Aεa，而在派生树中被画成如图3-2形式。2．派生树的结果设T是棵派生树，将此树的叶结点符号从左到右依次读取下来构成的符号串就是此派生树的结果。例如，图3-1.1派生树的结果就是aabbaa。3．派生树与句型的派生关系设G=(ＶＮ,ＶＴ,Ｐ,S)是CFG，如果G中有派生S*α，则在G中必有一棵以α为结果的派生树。反之，如果G中有一棵以α为结果的派生树，则G中也必有派生S*α。可

7、以说派生与派生树是一一对应的。A๐๐ε๐Aa๐ε๐๐a图3-1.24．最左派生与最右派生所谓最左派生，就是在一个派生的每一步都是对句型中最左边的变元进行替换。例如，例3-1中aabbaa的派生：SaASaSbASaabASaabbaSaabbaa，此派生是最左派生。所谓最右派生，就是在一个派生的每一步都是对句型中最右边的变元进行替换。SaASaAaaSbAaaSbbaaaabbaa,此派生是最右派生。5．上下文无关文法的二义性设G是个CFG，如果它的某个句子有两棵不同构的派生树，则称G是二义性的上下文无关文法。【例3-1.2】给定CFGG=({S},{a,b},P,S

8、)，其中P：SaSbS

9、bSaS

10、ε。句子abab的两棵不同构的派生树，如图3-1.3所示。图3-1.3abab的两棵不同构的派生树S๐a๐S๐๐Sb๐S๐๐aε๐๐ε๐ε๐S๐bS๐a๐S๐๐Sb๐๐Sa๐ε๐๐εε๐S๐๐b这说明此CFGG是有二义性的。3.2上下文无关文法的简化一个上下文无关文法有时可以去掉一些符号，或者去掉一些产生式以后，仍然和原来的文法等价，这就是所谓文法的简化。这里简化文法主要是指：去掉无用符号、去掉ε产生式和去掉单一产生式。1．去掉无用符号定义：给定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，如果在G中存在派生S*αXβ*w，其中w∈ＶＴ*，X∈ＶＮ∪ＶＴ，则称

11、符号X是有用的，否则X是无用的。简单地说，无用符号就是G中对任何w∈L(G)的派生中都不会出现的符号。【例3-2.1】给定文法G=({S,A,B,C},{a,b},P,S)，其中P：SAB

12、a,ABC

13、a,Cb。G中有派生：可见再往下就无法推导了，因而由S只能推出a，不能推出其他符号串。所以此文法中，A、B、C、b都是无用的符号，只有S和a是有用符号。如何去掉无用符号？分两步走，使用两个引理，就可以做到这一点。下面介绍这两个引理。引理3-2.1给定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，且L(G)≠Φ，可以找到一个与G等价的CFGG’=(ＶＮ’,ＶＴ,Ｐ’,S)，使得每个A∈ＶＮ’，都有

14、w∈ＶＴ*，且在G’中有A*w。证明：1）求ＶＮ’的算法：begin⑴OLDＶＮ:=Φ⑵NEWＶＮ:={A

15、Aw∈P且w∈ＶＴ*}⑶WhileOLDＶＮ≠NEWＶＮdobegin⑷OLDＶＮ:=NEWＶＮ⑸NEWＶＮ:=OLDＶＮ∪{A

16、Aα∈P,且α∈(ＶＴ∪OLDＶＮ)*}end⑹ＶＮ’:=NEWＶＮ,end下面证明此算法的有效性。显然对任何变元A∈NEWＶＮ,不论A是在第⑵步还是在第⑸步加入到NEWＶＮ中的,都有派生A