《编译方法》第2章形式语言和文法.ppt

2 1形式语言 第2章形式语言和文法 2 4文法的二义性 2 3文法的分类和化简 2 2文法 2 1形式语言 2 1 1语言的概念 2 1 2语言的定义方式 语言 符号串的集合 元素 符号串 该语言的一个句子 字母表 符号串中符号的来源 句子的构成 按一定规则 程序设计语言 程序的集合句子 程序 一个或长或短的字符串 字母表 固定的字符集 语言可以使用的所有符号 编程时必须遵循一定的规则 语法规则和语义规则 语言的描述工具 文法 2 1 1语言的概念 2 1语言 1 什么是语言 1 有穷字母表一个元素的非空有穷集合 其中的元素也称符号 每个语言均有一固定的字母表 例 C语言的字母表由基本字符集 字母 数字 括号 专用字符 保留字 int long if struct static typedef sizeof 等组成 2 1 1语言的概念 2 1语言 2 符号串的相关概念和术语 通常用V 或其他大写字母表示 例如V 0 1 a b c d e 等 2 符号串字母表中的符号组成的任何有穷序列 相关术语 长度 符号串中符号的个数 符号串x的长度表示为 x x m 0 空符号串 无任何符号的串 简称空串 用 表示 0省略写法 z x z xz x 2 1 1语言的概念 2 1语言 例2 1 a b c z x laugh 则 x 5 I you he am is are a student y Iamastudent 空格不计算长度 则 y 4 3 符号串的运算 连接 符号串x y的连接xy为一个新的符号串 该串的前面部分为x 后面部分为y 成立的等式 xy x y x x x 例2 2 若x home y work 则 x 4 y 4xy homework xy 4 4 8 2 1 1语言的概念 2 1语言 方幂 符号串x的方幂就是n个x自身连接次 表示为xn 规定x0 例2 3 若x ab 则x0 x1 ab x2 abab x3 ababab 成立的等式 x1 x x2 xx x3 xxx 若n 0 则有 xn xxn 1 xn 1xx 表示x的任意多次方幂 可以是0次 x 表示x的任意非0次方幂 2 1 1语言的概念 2 1语言 4 符号串的集合若集合A中的所有元素都是某字母表上的符号串 则称A为该字母表上的符号串集合 乘积 两符号串集U V的乘积为UV U V 成立的等式 U U UVn VV V n个V 规定 V0 V V0 V1 V2 V V1 V2 例2 4 若U a b V c d 则UV ac ad bc bd 2 1 1语言的概念 2 1语言 闭包 若指定字母表 则 表示 上的所有有穷长的串的集合 0 1 2 n 称为集合 的闭包 1 2 n 称为集合 的正闭包 成立的等式 0 若符号串x是 的元素 则表示为x 否则x 2 1 1语言的概念 2 1语言 语言的句子个数有限 枚举语言的句子有很多甚至是无穷多个 给出一些规则说明这个语言的句子的组成结构 规则 文法规则 2 1 2语言的定义方式 2 1语言 例2 5 文法规则 student English computer I you he am is are have study a an the 文法规则的作用 1 严格定义了一个语言的句子的结构 2 用适当条数的规则描述了一个语言的全部句子 2 1 2语言的定义方式 2 1语言 2 2文法 2 2 1文法的形式定义 2 2 2文法的表示方法 2 2 3相关概念 2 2文法 表示语言中的语法单位的符号 常用尖括号 括起 一个非终结符一般可以推导出终结符串 一个语言可使用的所有非终结符组成的集合称为非终结符集 用VN表示 1 终结符 不可分割的符号串 是组成句子的最基本的单位 一个语言允许使用的所有终结符组成的集合称为终结符集 用VT表示 2 非终结符 2 2 1文法的形式定义 2 2文法 3 规则 重写规则 产生式 生成式 形如 或 或 的有序对 其中 某字母表V的V 中的一个符号串 左部 V 中的一个符号串 右部 定义 一个文法是一个四元组G VN VT S P VN 非终结符集 非空 VT 终结符集 非空 VN VT S 识别符号或开始符号 S VN 且至少在一条规则中作为左部出现 P 规则 产生式 的集合 用V表示VN VT 称G的字母表或词汇表 4 文法 2 2 1文法的形式定义 2 2文法 G S 0S1或G S S 0S1或G S 0S1 01S 01S 01注意 左部相同的产生式可合并 用 表示 或 简化表示 只写出规则 产生式 且第一条规则的左部是开始符号 用 括起的或大写字母表示非终结符 不用 括起的或小写字母表示终结符 文法G也常写成G S 方括号中的S为开始符号 例2 6 有一文法G VN VT S P 其中 VN S VT 0 1 开始符号是SP S 0S1 S 01 2 2 1文法的形式定义 2 2文法 例2 7 文法G VN VT S P 为 VN VT student computer sister English I you he am is are have study a an the 开始符号是P student computer sister English I you he am is are have study a an the 2 2 1文法的形式定义 2 2文法 例2 8 FORTRAN语言中对标识符的规定是字母开头 长度小于等于8的字母数字串 则标识符的规则可以描述为 1 BNF表示法巴科斯 诺尔范式 巴科斯范式 采用四个元符号描述文法 或 2 扩展的BNF表示法增加三对元符号 1 表示符号串t的多次重复 n为重复的最小次数 m为重复的最大次数 省略n m表示t可以重复0到任意多次 2 2 2文法的表示方法 2 2文法 2 用于提取产生式的公共因子 从而可以简化产生式 若有文法规则A x 1 x 2 x n表示为A x 1 2 n 例2 9 文法规则S 0S1 01简化为S 0 S1 1 或S 0S 0 1或S 0 S 1 3 t 表示符号串t可选 即可有可无 例2 10 C程序设计语言的条件语句的文法规则BNF表示 if if else 扩展BNF表示 if else 2 2 2文法的表示方法 2 2文法 3 语法图表示法 例2 11 C语言条件语句的语法图 2 2 2文法的表示方法 2 2文法 终结符 非终结符 例2 13 对文法G S 0S1S 01有直接推导序列 S 0S1 00S11 000111 定义 如 是文法G VN VT S P 的一条规则 V 若有符号串v w满足v w 则称v 应用规则 直接产生w 或称w是v的直接推导 反过来称w直接归约到v 记作v w 1 推导和归约 2 2 3相关概念 2 2文法 定义 如果存在直接推导序列 v w0 w1 w2 wn w则称v推导 产生 出w 推导长度为n 反过来称w归约到v 记作v w 如果有v w 或v w 则记作v w 2 2 3相关概念 2 2文法 例2 15 推导S 0S1 00S11 000111 定义 文法G VN VT S P 若符号串x可由开始符号S推导出 S x 则称x是G的一个句型 若x仅由终结符组成 则称x为G的一个句子 2 句型和句子 句型 句子 2 2 3相关概念 2 2文法 注意 句型和句子都必须由开始符号S推出 定义 文法描述的语言是该文法的所有句子的集合 记作L G 集合形式表示 L G S VT 例2 16 文法G S 0S1S 01描述的语言 L G 0n1n n 1 3 形式语言 2 2 3相关概念 2 2文法 例2 17 有文法G A A 0RA 01R A1 定义 若有文法G1 G2 它们描述的语言相同 即L G1 L G2 则称两文法G1和G2等价 描述的语言L G 0n1n n 1 4 文法的等价性 2 2 3相关概念 2 2文法 2 2 3相关概念 2 2文法 5 递归规则和递归文法 递归文法 含有递归规则的文法称递归文法 递归规则 形如P 1P 2的规则称递归规则 若 1 则称左递归规则 若 2 则称右递归规则 P 1P 2的递归称间接递归 含间接递归的文法也是递归文法 2 3文法的分类和化简 2 3 1文法的分类 2 3 2两个定理 2 3 3文法的化简 2 3文法的分类和化简 1 0型文法 无限制文法或短语文法 2 3 1文法的分类 定义2 7设G VN VT P S 如果它的每个产生式 满足 VN VT 且 至少含有一个非终结符 则G是一个0型文法 结论0型文法的能力相当于图灵机 它所定义的语言为0型语言 任何0型语言都是递归可枚举的 反之 递归可枚举集也必定是一个0型语言 可由图灵机来识别 2 3文法的分类和化简 定义2 8设G VN VT P S 如果它的每个产生式 满足 仅S 除外 则G是一个1型文法 另一种描述 文法的产生式形如 1A 2 1 2其中A VN VN VT 且 例2 18 1型文法G S S xSYZ xYZyZ yzxY xyZY YZyY yyzZ zz 2 1型文法 上下文有关文法 2 3 1文法的分类 2 3文法的分类和化简 3 2型文法 上下文无关文法 例2 19 2型文法G S S ET P T PF i E E T E TP F F P 定义2 9设G VN VT P S 如果它的每个产生式 中的 是一个非终结符 则G是一个2型文法或上下文无关文法 2 3 1文法的分类 2 3文法的分类和化简 4 3型文法 正规文法或正则文法 例2 20 3型文法G S S aAA aAA aS aA dAA d 定义2 10设G VN VT P S 如果它的每个产生式均形如A aB或A a其中A B VN a VT 2 3 1文法的分类 2 3文法的分类和化简 描述句法 描述词法 VN aB a 2 3文法的分类和化简 2 3 1文法的分类 定理2 1 含有A 的文法产生的语言也可由不含A 的另一个文法产生 S 除外 定理2 2 若存在一个上下文有关文法G 则必存在另一个上下文有关文法G1 使得L G1 L G 且G1的开始符号不出现在任何产生式的右边 在使用上下文无关文法描述语言时不限制 产生式的使用 2 3文法的分类和化简 2 3 2两个定理 文法应没有多余的或有害的规则 化简 1 删除形如A A的产生式 2 删除不可到达的文法符号及其相应的产生式 3 删除不可终止的非终结符及其相应的产生式 例2 21 文法G S aS W UU aV bV acW aW W是不可终止的V是不可到达的 化简后的文法G S aS UU a 2 3 3文法的化简 2 3文法的分类和化简 1 语法树 2 4文法的二义性 2 3文法的二义性 定义 语法树是一棵数据结构意义上的 树 满足四个条件 1 每个结点都有一个标记 字母表V的一个符号 2 根的标记是S 文法的开始符号 3 若一个结点n至少有一个它自身除外的子孙 且有标记A 则A必在VN中 是非终结符 4 若标记为A的结点n的直接子孙从左到右的次序是结点n1 n2 nk 其标记分别为A1 A2 Ak 则A A1A2 Ak必是文法产生式集P中的一个产生式 对给定文法G 它的任何句型均能构造与之相关的语法树 2 4文法的二义性 2 3文法的二义性 i i i的语法树 例2 22 对算术表达式文G E iE E EE E EE E i i i 的推导过程可以是 1 E E E E E E i E E i i E i i i 2 E E E E i E E i E i i i i i 3 E E E E i E E i i E i i i i 2 4文法的二义性 2 3文法的二义性 可见 1 一棵语法树表示了一个句型的多种可能的不同推导过程 但未必是所有的 2 一个句型未必只有一棵语法树 最左推导 在推导的任何一步 是句型 都是对 中的最左非终结符进行替换 最右推导 在推导的任何一步 是句型 都是对 中的最右非终结符进行替换 也称规范推导 推出的句型称规范句型 例如最左推导 E E E i E i E E i i E i i i最右推导 E E E E E E E E i E i i i i I 显然 一棵语法树表示的最左 右 推导是唯一的 2 4文法的二义性 2 3文法的二义性 i i i的语法树 定义 若一个文法存在某个句子 它对应两棵 或以上 不同的语法树 或它有两个不同的最左 右 推导 则该文法是二义的 具有二义性 若产生某一上下文无关语言的每个文法均是二义的 则说该语言先天二义 例2 23 与例2 22等价的非二义文法G E T E TT F T FF E i 愿望 文法非二义 2 4文法的二义性 2 3文法的二义性 ThankYou