上下文无关文法34003

上下文无关文法34003第三部分 上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法(CFL)是一种简单的描述语法规则的递归方法

上下文无关文法34003 第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级 模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法(CFL)是 一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。所有的正 规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文法描 述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法 和其他一些形式语言。类似正则语言对应的抽象机模型是有限自动机，CFL也有对 应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增加存储空间得 到，并被设想成无限空间(对应有限自动机的有限空间)，采用了一种简单的管理模 式，栈(stack)，这种新的计算模型(或抽象机)称为下推自动机(pushdown automata)，下推是栈最典型的操作。有必要在下推自动机中保留非确定性，确定 型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定 型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称 为分析(parse)。分析不是一定需要下推自动机来完成。CFL仍然不够通用，不能 包括所有有意义的、或有用的形式语言。采用类似第五章的技术，我们将给出一些 不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。6上下文无 关文法6.1上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包 括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。文法与我们熟 悉的语言的语法描述相近，是描述语言和分析语言的有力工具。问题:文法的形式 化定义似乎可以模仿有限自动机，比如5元组或6元组之类。例子6.1正如我 们在例子2.16中所见，字母表ab上的回文语言pal可以用下面的递归方法描 述:1.abpal2.对每个Spal，aSa和bSb也属于pal3.pal中不包含其他 字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算(比如某种