下载文档原格式
上下文无关文法与语言第5章上下文无关文法及语言现在我们将注意力从常规语言转向另一大类语言，即“上下文无关语言”。
这个语言类有一个自然的递归表示，称为“上下文无关语法”。
自1960年以来，上下文无关语法一直在编译技术中发挥着重要作用。
他们可以将analyzer（一种用于在编译过程中探索源程序结构的程序）的实现从耗时且非通用的设计工作转变为可以快速完成的工作。
近年来，上下文无关语法也被用来描述文档格式：XML（可扩展标记语言）中使用的DTD（文档类型定义）被用来描述web上的信息交换格式。
在本章中，我们将首先介绍上下文无关文法的表示方法，然后将介绍怎样用文法来定义语言。
我们将会讨论到“语法分析树”──对一个文法处在它所表示的语言的字符串中结构的图形描述。
语法分析树是对一个编程语言的语法分析器的产物，也是通常用来获得程序结构的途径。
上下文无关语言有另一种等价的自动机表示形式，称为“下推自动机”。
我们将在第6章介绍下推自动机。
虽然它没有有限自动机那么重要，但我们仍然需要引入它，因为作为一种语言定义机制，它相当于上下文无关语法。
当我们在第七章研究如何确定语境无关语言和语境无关语言的闭包时，这种等价性是非常有用的。
5.1上下文无关文法本章将从非正式介绍上下文无关语法的表达开始。
形式化的定义将在读者理解这些语法的一些重要能力之后给出。
届时，我们将解释如何正式定义语法，并引入一个称为“派生”的过程：它可以确定语法语言中的字符串。
5.1.1一个非形式化的例子让我们考虑一种“回文”语言。
“回文”指的是一个前后读相同的字符串，如Otto或MadamI Madama（“madam，我是madam”，引自伊甸园中伊芙听到的第一句话）。
换句话说，字符串W是回文的当且仅当W=WR。
考虑一个简单的例子——只需描述字母表{0,1}上的回文。
这种语言包括0111011等字符串和空字符串ε，但不包括011或0101等字符串。
很容易验证这个0,1上的回文语言lpal不是正则语言，要做到这点只需要使用泵引理即可：假设lpal是一个正则语言，令n是与其相关的常数，考虑回文串w=0n10n，如果lpal是正则的，那么我们就能够把w写为w=xyz，其中y由第一组0中的若干个（但至少一个）构成。
8 上下文无关语言和非上下文无关语言8.1 上下文无关语言的泵引理从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。
这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。
然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。
本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。
利用这个性质能够发现许多不是CFL的语言。
正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。
如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。
设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式，S⇒*vAz⇒*vwAyz⇒*vwxyz其中，v, w, x, y, z∈∑*。
推导过程中，出现了A⇒*wAy，我们可以多次重复这个推导过程，如S⇒*vAz⇒*vwAyz⇒*vw2Ay2z⇒*vw3Ay3z⇒*...⇒*vw m Ay m z又由于A⇒*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。
为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。
同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。
这类似于我们处理正则语言的泵引理。
在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。
第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。
上下文无关文法（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符号“|”表示“或”的含义。
第五章⾃上⽽下语法分析第五章⾃上⽽下语法分析1、教学⽬的及要求：本章介绍编译程序的第⼆个阶段语法分析的设计⽅法和实现原理，包括⾃上⽽下分析的⽆回朔的递归下降分析、 LL(1)分析法。
要求理解递归下降分析、LL(1)⽂法的基本概念；掌握⽆回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析⽅法。
◇能够对⼀个给定的⽂法判断是否是LL(1)⽂法；◇能构造预测分析表；◇能⽤预测分析⽅法判断给定的输⼊符号串是否是该⽂法的句⼦；◇能对某些⾮LL(1)⽂法做等价变换：①消除左递归②提取左公共因⼦可能会变成LL(1)⽂法。
这样可扩⼤⾃顶向下分析⽅法的应⽤。
2、教学内容：语法分析器的功能，⾃上⽽下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。
3、教学重点：递归下降⼦程序，预测分析表构造，LL(1)⽂法。
4、教学难点：对⼀个⽂法如何判断是否是LL(1)⽂法，由于在判断 LL(1)⽂法时⽤到⽂法符号串的开始符号集合（FIRST集）和⾮终结符后跟符号集合（FOLLOW集）的计算，⽽⼀般学⽣往往因概念不清或不够细⼼对这两个集合的计算常常出错，导致判断和分析结果的错误。
5、课前思考为了了解⾃顶向下（⾃上⽽下）分析的⼀般过程和问题，请学⽣⾸先回顾本章之前介绍的有关基本概念：◇句⼦、句型和语⾔的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的⾃顶向下语法分析？◇⾃顶向下语法分析是从⽂法的开始符号出发，反复使⽤各种产⽣式，寻找与输⼊符号匹配的推导。
◇确定的⾃顶向下语法分析中⽤的是哪种推导？◇在确定的⾃顶向下语法分析过程中，当以同⼀个⾮终结符为左部的产⽣式有多个不同右部时，如何选择⽤哪个产⽣式的右部替换当前的⾮终结符？◇确定的⾃顶向下语法分析对⽂法有何限制？6、章节内容第⼀节概述第⼆节 LL(1)分析⽅法第三节递归下降分析法5.1 概述LL分析法确定的⾃上⽽下分析⾃上⽽下分析递归下降分析法语法分析不确定的⾃上⽽下分析——即带回溯的分析⽅法算符优先分析⾃下⽽上分析LR分析⼀、带回溯的⾃顶向下分析⽅法是⾃顶向下分析的⼀般⽅法，即对任⼀输⼊符号串，试图⽤⼀切可能的办法，从树根结点（识别符号）出发，根据⽂法⾃上⽽下地为输⼊串建⽴⼀棵语法树，或者说，从识别符号开始，根据⽂法为输⼊串建⽴⼀个推导序列，这种分析过程本质上是⼀种试探过程，是反复使⽤不同规则谋求匹配输⼊串的过程。
