Chapt23形式语言讲义.ppt

语法树是句型推导过程的图形表示。 例如，设句子bd0的最右推导或规范推导为： 标识符 ? 标识符数字 ? 标识符0 ? 标识符字母0 ? 标识符d0 ? 字母d0 ? bd0 标识符 数字 标识符 标识符 字母 字母 b d 0 图23.1 句子bd0的语法树 定义1.9 如果一个文法存在某个句子对应两棵以上的不同的语法树，或有两个以上的不同的最左(右)推导，则称该文法是二义性文法（程序设计语言不能有二义性 ）。 定义1.10 如果一个语言L的任何文法都是二义性文法，则称该语言L是二义性语言。 在理论上已经证明了，存在着这种二义性的语言。 文法的二义性与语言的二义性是两个不同的概念。 Chomsky于1956年把文法分成四种类型，即：0型文法、1型文法、2型文法和3型文法。这种文法的分类称作Chomsky分类。 文法所生成的语言，根据四种类型文法，也分为四种，即：0型语言、1型语言、2型语言和3型语言。 Chomsky建立的形式语言理论对计算机科学的发展规律有着深刻的影响，特别是对计算机程序设计语言的设计、编译方法和计算复杂性等方面具有更大的作用。 定义1.12 设文法G = (V, T, P, S)，如果对于?????P，满足|?|≥|?|(除S??外)，则文法G称为1型文法或上下文有关文法，简记为CSG。 1型文法的产生式的形式也被描述为：?1A?2??1??2，其中： ?1、?2 、??(V∪T)+，A?V。它更能体现“上下文有关”这一含义，因为，只有A出现在?1和?2之间（?1为A的上文， ?2为A的下文），才允许用?来取代A。 1型文法所产生的语言称作1型语言或上下文有关语言(简记为CSL)。 定义1.13 设文法G = (V, T, P, S)，如果，对于?????P，满足??V，??(V∪T)*，则称G为2型文法或上下文无关文法，简记为CFG。 上下文无关文法取名为“上下文无关”的原因就是因为字符 ? 总可以被字串 ? 自由替换，而无需考虑字符 ? 出现的上下文。 2型文法所产生的语言称作2型语言或上下文无关语言(简记为CFL)。 一个简单的上下文无关文法的例子是：S - aSb | ε。由于这个文法的产生式的左边都是单个的非终结符S，右边是由终结符或非终结符构成的符号串aSb和ε，因此符合上下文无关语法产生式的要求。该文法产生的语言为 {anbn : n ≥ 0} 。 定义1.14：设文法G = (V, T, P, S)，如果P中的每一条产生式都是A?aB或A?a形式，其中：A、B?V ，a?T ，则称G为3型文法或正规文法, 简记为RG。 3型文法所产生的语言称作3型语言或正规语言(简记为RL)。3型语言与有限自动机等价，即有限自动机恰能识别3型语言。 在忽略句子ε的情况下，由Chomsky分类定义可知，任何3型语言都是2型语言，任何2型语言都是1型语言，任何1型语言都是0型语言。 0型语言 1型语言 2型语言 3型语言 图23.3 形式语言的Chomsky层级 正规式是按照一组定义规则，由较简单的正规式构成的，每个正规式e表示一个语言L(e)（正规集合）。 定义1.15 字母表∑上的正规表达式和正规集递归定义如下： 1、任意a∈?，a是?上的一个正规表达式，它所表示的正规集为{a}。 2、空串ε是∑上的一个正规表达式，它所表示的正规集为{ε}。 3、符号φ是∑上的一个正规表达式，它所表示的正规集为?。 4、设e1与e2都是∑上的正规表达式，它们所表示的正规集分别为L(e1)与L(e2)，则 （1）e1 + e2也是正规表达式，它所表示的正规集为L(e1 + e2) = L(e1)∪L(e2) （2）e1·e2也是正规表达式，它所表示的正规集为 L(e1·e2) = L(e1)L(e2) （3）(e1)*也是正规表达式，它所表示的正规集为 L((e1)*) = (L(e1))* 例23.14 令∑ = {a, b}，下面表列出了∑上的一些正规表达和相应的正规集： 正规表达式 正规集 a + b {a, b} a* {?, a, aa, aaa, aaaa,…} aa* {a, aa, aaa, aaaa,…} (a + b)(a + b) {aa, ab, ba, bb} (a + b)* {ε, a, b, aa, ab, ba, bb,…}即所有含a和b的符号串 (aa + ab + ba + bb)* 空串?或任何长度为偶数的a,b串 (a + b)(a + b)(a + b)*) 任何长度大于等于2的a, b串 公理 说明 r + s = s + r 运算+是可交换的 r + (s + t) = (r + s)+t 运算+是