《形式语言概论》PPT课件.ppt

第二章形式语言概论 编译程序使得高级语言源程序所描述的功能得以在计算机上实现 编译程序的设计者就是高级语言的实现者 源程序的编写者就是高级语言的使用者 他们必须遵循同样的准则 高级语言程序的构成规则 才能使写出的源程序能够被成功地翻译 构造一个编译程序 首先要了解被编译的源程序的结构及其含义 要搞清楚源语言的词法规则 语法规则和语义规则是如何描述的 文法描述的就是高级语言程序的构成规则 第二章形式语言概论 本章主要介绍形式语言理论中的一些最基本的概念和基础知识 它是学习以后各章节的基础 大多数程序设计语言的单词和语句是由正规文法和上下文无关文法来描述的 有穷自动机是词法分析的理论基础 2 1语言成分 一个语言的成分包括字母表 Alphabet 文法 Grammar 以及它的语义 本节将主要讨论字母表和符号串的一些基本概念 字母表与符号 字母表是元素的非空有穷集合 字母表中的元素称为符号 举例说明 符号串及其运算 符号串的概念 符号串的长度 符号串的连接 符号串集合的乘积 符号串的方幂 符号串集合的方幂 符号串集合的正闭包 符号串集合的自反闭包 形式语言 形式语言是字母表上按某种规则构成的所有串的集合 这些串称为句子或字 对于一个具体的语言 都有语法和语义两个方面 形式语言是指不考虑语言的具体意义 形式语言的表示方法有穷语言 枚举法无穷语言 文法 2 2产生式文法和语言 文法 Grammar 是对语言结构的定义和描述 换句话说 在形式上用来描述语言语法结构的就是文法 通常是由一组规则构成的 一个程序语言的文法的就是用适当条数的规则把该程序语言全部成分描述出来 2 2 1产生式文法 定义2 1产生式文法定义成一个四元组G VN VT S P VT 非空有限的终结符号集 符号表 VN 非空有限的非终结符号集 变量表 S 开始符号 识别符号 是文法G规定的最终目标 P 产生式 规则 的集合 其中VN VT S VN 我们令V VN VT 则P中产生式的一般形式为A A VN且 V 或A 本书中统一采用 A 的表示方法 2 2 2上下文无关文法 定义2 2文法G是一个四元组 G VN VT P S 其中 VN VT分别是非空有限的非终结符号集和终结符号集 VN VT P是产生式集 S VN称为文法的识别符号或开始符号 开始符号S必须至少在某个产生式的左部出现一次 程序设计语言表达式的文法 G1 VN VT S P VN E VT i S EP E i E E E E E E E E 2 2 3上下文无关文法定义的语言 定义2 3设文法G VN VT P S A 是其中的产生式 若有符号串 VN VT 使得U A w 则称w为U应用产生式A 所得到的直接推导 DirectDeriavtion 也称w可直接归约到U 记为U w 即 A 特别的 当 时 有A 即每个产生式的右部都是它左部的直接推导 符号 仅指 推导一步 的意思 举例说明 2 2 3上下文无关文法定义的语言 定义2 4如果存在一个直接推导的序列v 0 1 2 n w n 0 则称符号串w为符号串u的一个推导 或称 w可归约到v 记为推导举例 2 3文法的分类 2 3 1文法分类乔姆斯基根据产生式的形式把文法分为4类 0型文法 短语文法 无限制文法 1型文法 上下文有关文法 2型文法 上下文无关文法 3型文法 左 右线性文法和正规文法 0型文法 产生式具有以下形式 其中 VN VT VN VT 1型文法 上下文有关文法 1型文法G的产生式具有以下形式 要求 1 其中 1A 2 1 2 1 2 VN VT A VN VN VT 例1型文法G6 VN VT P S 其中 VN S X Y Z VT x y z P S xSYZ xYZ xY xy yY yy yZ yzZY YZ zZ zz 2型文法 上下文无关文法 在1型文法的产生式中上下文 1和 2用空符号串 代替 则有以下形式的产生式称为2型文法 A 其中 A VN VN VT 例2型文法G3 VN VT P E 其中 VN E T F VT i P E E T T T T F F F E i 3型文法 右线性文法和正规文法 如果P中的产生式只含有下面的两种形式 A A B则称该文法为右线性文法 其中 A B VN VT 例右线性文法G4 VN VT P S 其中 VN S A B VT 0 1 P S 0 1 1A 0B A 1A 0B B 0 1 0B 3型文法 右线性文法和正规文法 在正规文法中 P中的每个产生式 S 例外 S为文法的开始符号 只有两种形式 A a A aB 其中A B VN a VT 此外 如果S 是P中的一个产生式 那么S不能出现在任何产生式的右边 例正规文法G5 S 十进制实数 S dB A A GA dB GB dB H dG dHH dH d其中d代表十进制数字 2 3 2文法分类的意义 1 0型文法 0型语言 递归可枚举语言 使用图灵机来识别1型文法 1型语言 上下文有关语言 使用空间线性界限自动机来识别2型文法 2型语言 上下文无关语言 使用下推自动机来识别3型文法 3型语言 正规语言 正则语言 使用有穷自动机来识别 2 3 2文法分类的意义 2 程序设计语言的词法规则 单词 属于正规文法 使用有穷自动机来识别 程序设计语言的语法和语义描述属于上下文无关文法和上下文有关文法范畴 为降低语法分析的难度 大部分语法规则使用上下文无关文法来描述 使用下推自动机来识别 2 4语言和语法 2 4 1句型 句子和语言 1 定义2 6设S是文法G的识别符号 如果 则称符号串u为文法G的句型 举例说明 2 4 1句型 句子和语言 2 定义2 7设S是文法G的识别符号 若 u VT 则称符号串u为文法G的子 定义2 8设S是文法G的识别符号 文法G的语言L G u 且u VT 即文法的语言是文法的所有句子构成的集合 文法和语言综述 1 给定一个文法 就能从结构上唯一地确定其语言 即G L G 给定一种语言 能确定其文法 但这种文法不是唯一的 例如 标识符文法 G1 I I L IL IDL a b c x y z A B C X Y ZD 0 1 2 3 9G2 I 右线性文法 I aB aB aB dB a dG3 I 左线性文法 I a Ia Ida代表字母 d代表数字 文法和语言综述 2 给定文法 如何确定该文法的语言 从已知文法确定语言的中心思想是 从文法的开始符号出发 反复连续地使用规则 对非终结符施行替换和展开 找出句子的规律 用式子或自然语言描述出来 举例说明 文法和语言综述 3 给定语言 如何构造其文法 例 设字母表 a b 试设计一个文法 使其描述的语言为L a2n b2n n 1 G VN VT P S 其中VN A B D VT a b P A aa aaB bb bbDB aa aaBD bb bbD S A 例 设字母表 a b 试设计一个文法 使其描述的语言L abna n 0 2 4 2语法树 1 在自然语言中 可通过树型表示直观地分析句子结构 在形式语言中 则是通过语法树直观地分析文法的句型结构 句子结构 2 4 2语法树 设文法G VN VT P S 对于文法G的任意一个句型都存在一个相应的语法树 树的根结点标记是文法的识别符号S 每个结点上的标记都是文法字汇表中的符号 若一棵子树的标记为A 且所有直接后结点从左向右排列的顺序为B1 B2 Bn 则 A B1B2 Bn P 如果T1是根结点的唯一子树 且标记为 则一定有S 在P中 若树的所有末端结点上的标记从左向右排列为字符串w 则w是G的句型 若w仅含终结符号 则w是G所产生的句子 举例 2 4 3语法树的生成过程 也称为推导树 是对句子或句型推导过程的图形表示法 从文法的开始符号出发 每推导一步 语法树向下伸展一层 例1 设有文法G E E E T E T TT T F T F FF E i给出句型 T i2 i1 F的语法树 2 5文法和语言的一些特性 2 5 1无用非终结符号如果文法的某个非终结符不出现在文法的任何一个句型中 并且不能从它推导出终结符号串 则称该非终结符为无用非终结符号 P30 例2 13 2 5 2不可达文法符号如果一个非终结符 非识别符号 不出现在文法的任何一条产生式的右部 则称该非终结符为不可达文法符号 文法中的任意非终结符A应满足如下两个条件 1 A必须在文法的某个句型中出现 2 必须能从A推导出终结符号串 2 5 3可空非终结符 2型文法的产生式要求以下形式 A 其中 A VN VN VT 对2型文法可进行扩充 令 VN VT 允许有以下形式的产生式 A 此产生式称为空产生式 A称为可空非终结符 2 5 4最左 最右推导和规范推导 1 定义2 9在xUy xuy直接推导中 若x VT U VN即U是符号串xUy中最左非终结符 则称此直接推导为最左直接推导 若一个推导的每一步直接推导都是最左直接推导 那么此推导称为最左推导 定义2 10在xUy xuy直接推导中 y VT U VN 即U是符号串xUy中最右非终结符 则称此直接推导为最右直接推导 若一个推导的每一步直接推导都是最右直接推导 则称此推导为最右推导 最右直接推导又称为规范直接推导 最右推导又称为规范推导 2 5 4最左 最右推导和规范推导 2 定义2 11假定x1 x2 xn是一个最左推导 我们称序列Xn Xn 1 X1是一个最右归约 定义2 12假定x1 x2 xn是一个最右推导 我们称序列Xn Xn 1 X1是一个最左归约 最左推导的逆过程是最右归约 最右推导的逆过程是最左归约 2 5 5二义性 1 定义2 13一个文法 如果它的一个句子有两棵或两棵以上的语法树 则称此句子具有二义性 如果一个文法含有二义性的句子 则该文法具有二义性 例如 表达式的文法 二义性的文法将给编译程序的执行带来问题 对于二义性文法的句子 当编译程序对它的结构进行语法分析时 就会产生两种甚至更多种不同的解释 由于语法结构上的不确定性 将必然会导致语义处理上的不确定性 对于二义性的文法我们可以利用文法的等价性来消除文法的二义性 以利于语法分析的进行 2 5 5二义性 2 例 定义某种程序设计语言语句的文法 证明是否有二义性并消除之 S ifbS ifbSelseS A 其他语句 分析该文法的句子ifbifbAelseA对应两棵不同的语法树 改写文法 1 不改变现有的规则 加进一项语法规定 else与前面最近的不带else的if相对应 2 改写文法G为G S S1 S2S1 ifbS1elseS2 AS2 ifbS ifbS1elseS2规定if和else之间只能是if else语句或其他语句 2 5 5二义性 3 文法的二义性和语言的二义性是两个不同的概念 文法的二义性不能用算法来判定 2 6分析方法简介 一个分析器或分析自动机是这样一种系统 它能够根据给定的文法G 构造语言L G 的任意推导 分析也可看作是语法树的构造过程 分析的方法很多 可归纳为两类 一类是自上而下分析方法 另一类是自下而上分析方法 2 6 1自上而下分析方法 自上而下分析方法的基本思想是从文法的开始符号出发 利用其中的产生式 逐步推导出待分析的符号串 如果能推导出这个符号串 则表明此符号串是该文法的一个句型或句子 否则便不是 2 6 2确定的自上而下分析方法 1 当文法的某一个非终结符有几条产生式 而且每条产生式右部首符号都是终结符时 应保证它们是互不相同的终结符 例设文法G18 S S aBc bCdB eB fC dC c试检查符号串aefc是不是该文法的句子 2 6 2确定的自上而下分析方法 2 上例推导过程 S aBc S aBc B eB S aBc aeBc