下载文档原格式
第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。
上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。
所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。
上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。
类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。
CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。
有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。
分析不是一定需要下推自动机来完成。
CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。
采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。
6 上下文无关文法6.1 上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。
文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。
问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。
例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述：1.Λ, a, b∈pal2.对每个S∈pal，aSa和bSb也属于pal3.pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal 的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1.S的值可以是Λ, a, b2.每个S可以写成aSa或bSb的形式如果我们用→表示“可以取值为”，则可以写出下面的式子：S→aSa→abSba→abΛba=abba上面的产生过程可以总结成下面的两组产生式（或称规则）：S→a | b | ΛS→aSa | bSb符号“|”表示“或”的含义。
编译原理第二章前后文无关文法和语言winniewan@本章目的▪为语言的语法描述寻求工具▪掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一---文法▪熟练使用文法定义程序设计语言的单词和语法成分▪对形式语言的理论有一个初步基础问题的提出▪如何描述定义一种语言？▪如何识别 & 分析之？用一组数学规则来描述语言的方式：形式描述形式语言本章内容▪文法和语言的表示▪文法和语言的定义▪句型的分析▪文法的化简和改造▪文法和语言的Chomsky分类2.1 文法和语言的表示▪“What is language?”符号串▪语言是由句子组成的集合，是由一组符号所构成的集合。
▪语言的表示方法：▪枚举句子▪制定有限的规则▪建立一种装置（自动机），以检验/识别句子2.2 文法和语言的定义▪基本概念和术语▪文法和语言▪符号：可以相互区别的记号（元素）。
▪字母表∑：符号（元素）的非空有穷集合。
▪符号串：由字母表∑中的符号组成的任何有穷序列称为该字母表上的符号串。
▪定义：1.空符号串ε(没有符号的符号串)是∑上的符号串2.若x是∑上的符号串，a是∑的元素,则xa是∑上的符号串3.y是∑上的符号串，当且仅当它可以由1和2导出▪区分ε，{ε}和φ▪前缀：移走符号串s尾部的零个或多于零个符号得到的符号串▪真前缀▪后缀：删去符号串s头部的零个或多于零个符号得到的符号串▪真后缀▪子串：从s中删去一个前缀和一个后缀得到的符号串▪符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。
ε的长度为0▪连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy▪方幂：符号串自身连接n次得到的符号串a n 定义为 aa…aa n个a a1=a, a2=aa则a0=ε▪符号串集合：若集合A中所有元素都是某字母表∑上的符号串，则称A为字母表∑上的符号串集合。
▪两个符号串集合A 和B 的乘积定义为 AB ={xy|x ∈A 且y ∈B }▪使用 ∑*表示∑上的一切符号串（包括ε）组成的集合。
