第二章形式语言与自动机理论报告.ppt

第二章 形式语言与自动机理论 主要内容： 文法及文法二义性 文法等价变换 DFA与NFA等价性 DFA化简 正则表达式 2.1 语言和文法 字母表 符号串 符号串的连接 符号串的方幂 前缀和后缀 子字符串 符号串集合 符号串集合的乘积 符号串集合的方幂 符号串集合的正闭包 符号串集合的星闭包 语言 给定字母表∑，则 ∑上任一字符串集合就是∑上的一个语言 文法 之 概述 文法能清晰地描述程序设计语言的语法构成 易于理解。 文法能自动地构造有效的语法分析器，检 查源程序是否符合语言规定的语法形式。 文法定义可以了解程序设计语言的结构，有 利于将源程序转化为目标代码，以及检查出 语法错误。 基于文法实现的语言易于扩展 文法 之 定义 文法G定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S? VN P是产生式的集合，且具有下面的形式： ? ??，其中?，??(VT?VN )* 文法 之 分类 O型文法: 也称为短语文法，其产生式具有形式: ?→?，其中?,??(VT?VN)*，并且?至少含一个非终极符 。 1型文法: 也称为上下文有关文法。它是0型文法的特例，要求|?| ? |?| (S→?例外，但S不得出现于产生式右部)。 2型文法: 也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符: A→? 。 3型文法: 也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一: A →a ，A →a B 其中A,B?VN ，a?VT 。 上下文无关文法（CFG） 定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S? VN P是产生式的集合，且具有下面的形式： A?X1X2…Xn 其中A?VN，Xi? (VT?VN) ，右部可空。 推导：如果A??是一个产生式，则有?A????? ,其中?表示一步推导(用A →?)。这时称???是由?A?直接推导的。 ?的含义是，使用一条规则，代替?左边的某个符号，产生?右端的符号串 ? ?+ ?: 表示?通过一步或多步可推导出? ? ?* ? : 表示?通过0步或多步可推导出? 句型： 如果有S?* ? ，则称符号串?为CFG的 句型 。我们用SF(G)表示文法G的所有句型的集合 句子： 如果?只包含终极符，则称?为CFG的句子，其中S是文法的开始符 语言： L(G)={ u| S ?+ u ,u ? VT* }。 文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。 最左（右）推导： 如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号?lm（?rm）表示最左（右）推导。 左（右）句型： 用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。 结论： 每个句子都有相应的最右和最左推导（但对句型此结论不成立） 短语：设S是文法的开始符，???是句型(即有S ?*???），如果满足条件： S ?* ?A? A ?+ ? 则称?是句型???的一个短语。 直接短语（简单短语）：如果满足条件： S ?* ?A? A ? ? 则称?是句型???的一个简单短语。 句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。 语法分析树与文法二义性 语法分析树(简称分析树)用来描述句型的结构，是句型推导的一种树型表示。文法 G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵分析树： 1. 每个节点都有G的一个文法符号，并且根节点标 有初始符S，非叶节点标有非终极符，叶节点标有 终极符或非终极符或?。 2.如果一个非叶节点A有n个儿子结点(从左到右）为 X1,X2,...,Xn，则G一定有产生式 A→X1X2 ...Xn 。 线性推导：我们称用?符号进行的推导为线性推导 。 树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树(如果无二义性)，而线性推导则可很多。 二义性文法 二义性文法：如果一个句型有两棵不同的语法分析树，则称其文法具有二义性 文法G=( {+,*,I,(,)}, {E}, E, P),其中P为： E ? i E ? E + E E ? E * E E ? ( E ) 文法等价变换 增加拓广产生式 定理：对任一文法G1都可以构造文法G2，使