资源描述：
《上下文无关文法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、语言与计算理论导引上下文无关文法第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增
2、加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdownautomata），下推是栈最典型的操作。有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。分析不是一定需要下推自动机来完成。CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。采用类似第五
3、章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。1陶晓鹏Copyright2003语言与计算理论导引上下文无关文法1陶晓鹏Copyright2003语言与计算理论导引上下文无关文法6上下文无关文法6.1上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。例子6.1正如我们在例子
4、2.16中所见，字母表{a,b}上的回文语言pal可以用下面的递归方法描述：1.L,a,bÎpal2.对每个SÎpal，aSa和bSb也属于pal3.pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1.S的值可以是L,a,b2.每个S可以写成aSa或bSb的形式如果我们用®表示“可以取值为”，则可以写出下面的式子：S®aSa®abSba®abLba=abba上面的产生过程可以总结成下面的两组产生式（或称规
5、则）：S®a
6、b
7、LS®aSa
8、bSb符号“
9、”表示“或”的含义。上式的含义是aSa或bSb，而不是a或b，即连接运算的优先级高于“
10、”。我们使用的这套术语中，小写字母a和b表示终结符，大写字母S表示非终结符，或称变量。总共有5条规则，或产生式（production）。符号S18陶晓鹏Copyright2003语言与计算理论导引上下文无关文法是非终结符，也是起始终结符，即我们生成字符串的起始符号是S，然后不断利用规则替换符号串中的非终结符，直到最终得到一个不含非终结符的符号串，就生成了规则所定义的语言的一个字符串。例子
11、2中的产生式具有除起始符S外的多个非终结符，我们设想S表示了语言中任意的字符串，其他非终结符表示了其他辅助性的字符串类型，他们可用来方便地生成S表示的字符串。例子6.2我们要构造一个生成所有在字母表{a,b}上的非回文字符串的文法，那样的字符串可以描述如下：从字符串的两端开始比较，也许能够发现一些相同的字符对，但最终能够发现一对不同的字符。对于前一种情况，我们可以借用回文语言的产生式：S®aSa
12、bSb如果加入产生式S®a
13、b
14、L则这种左右匹配的形式将体现在整个字符串上，为了中断这种左右匹配的情况，即体现上面提到的第二
15、种情况，我们引入新的非终结符，比如D，表示那些左右两个端点上的字符不同的字符串。且所有符合D的字符串也符合S，因此有S®D。非终结符的定义比较简单，它唯一的条件是左右两个端点的字符不相同，中间的字符串可以是任意的，我们用非终结符A表示任意的字符串，则有D®aAb
16、bAa。A表示任意的字符串，因此A的产生式更简单了，不用添加新的非终结符来简化问题，它的产生式是，A®L
17、aA
18、bA。我们把上面三个非终结符的产生式写在一起，就得到了描述所规定语言的产生式集：S®aSa
19、bSb
20、DD®aAb
21、bAaA®L
22、aA
23、bA因此一个完
24、整的非回文字符串“abbaaba”的产生过程是，S®aSa®abSba®abDba®abbAaba®abbaAaba®abbaLaba®abbaaba定义6.1上下文无关文法（context-freegrammar,CFG）是一个4元组G=(V,å,S,P)，其中，V和å是不相交的有限集，SÎV，P是一组有限的产生式规则，形如A®
