短语直接短语和句柄ppt课件

2 4短语 直接短语和句柄 短语 令G是一个文法 S是文法的开始符号 假定 是文法G的一个句型 如果有 则称 是相对于非终结符A的 句型 的短语 1 2 4短语 直接短语和句柄 则称 是直接短语 直接短语 且A 令G是一个文法 S是文法的开始符号 假定 是文法G的一个句型 如果有 2 2 4短语 直接短语和句柄 注意 短语和直接短语的区别在于第二个条件 直接短语中的第二个条件表示有文法规则A 因此 每个直接短语都是某规则右部 3 2 4短语 直接短语和句柄 句柄 一个句型的最左直接短语称为该句型的句柄 句柄特征 1 它是直接短语 即某规则右部 2 它具有最左性 4 2 4短语 直接短语和句柄 注意 短语 直接短语和句柄都是针对某一句型的 都是指句型中的哪些符号串能构成短语和直接短语 离开具体的句型 来谈短语 直接短语和句柄是无意义的 5 2 4短语 直接短语和句柄 例如设有文法G S S A B a b P S 其中P为 求句型baSb的全部短语 直接短语和句柄 S AB A Aa bB B a Sb 6 2 4短语 直接短语和句柄 对文法 首先建立该句型的推导过程 最左推导 最右推导 分析根据短语定义 可以从句型的推导过程中找出其全部短语 直接短语和句柄 句型baSb 7 2 4短语 直接短语和句柄 句型baSb中的子串Sb 是 相对于非终结符B 句型baSb的短语 且为直接短语 B Sb 句型本身是 相对于非终结符S 句型baSb的短语 根据最左推导 8 2 4短语 直接短语和句柄 句型baSb中的子串a 是 相对于非终结符B 句型baSb的短语 且为直接短语 句柄 句型baSb中的子串ba 是 相对于非终结符A 句型baSb的短语 B a 根据最右推导 9 2 5语法树与文法的二义性 推导和语法树 1 语法树 对句型的推导过程给出一种图形表示 这种表示称为语法树 也称推导树 10 2 5 1推导和语法树 例如设有文法G E 构造句型i i i的语法树 首先给出句型的推导过程 最左推导 E E T E T T T T F T F F F E i E E T T T T F T F F T i F T i i T i i F i i i 11 2 5 1推导和语法树 根据推导过程构造句型i i i的语法树如下 E E T E E T T T T T F T T F F F T F i F T i i i T i i i F F i i i i 12 2 5 1推导和语法树 由例可知 语法树的构造过程是从文法的开始符号出发 构造一个推导的过程 因为文法的每一个句型 句子 都存在一个推导 所以文法的每个句型 句子 都存在一棵对应的语法树 13 E E T E F E i T i T F i T i i F i i i i i 2 5 1推导和语法树 对句型i i i 还可给出最右推导 14 2 5 1推导和语法树 这也就是说 一棵语法树表示了一个句型的种种可能的 但未必是所有的 不同推导过程 包括最左 最右 推导 15 3 5 1推导和语法树 2 子树 语法树的子树是由某一结点连同所有分枝组成的部分 16 3 5 1推导和语法树 3 简单子树 语法树的简单子树是指只有单层分枝的子树 17 2 5 1推导和语法树 句型的短语 直接短语和句柄的直观解释是 短语 子树的末端结点形成的符号串是相对于子树根的短语 直接短语 简单子树的末端结点形成的符号串是相对于简单子树根的直接短语 句柄 最左简单子树的末端结点形成的符号串是句柄 18 2 5 1推导和语法树 短语 i i i i i 第一个i 第二个i 第三个i 三个i都是直接短语 第一个i是句柄 注意 i i不是句型的短语 句子i i i 19 2 5 1推导和语法树 前例对文法G S S A B a b P S 其中P为 可用语法树非常直观地求出句型baSb的全部短语 直接短语和句柄 S AB A Aa bB B a Sb 20 2 5 1推导和语法树 分析首先根据句型baSb的推导过程画出对应的语法树如下 Sb为句型的相对于B的短语 直接短语 baSb为句型的相对于S的短语 ba为句型的相对于A的短语 a句型的相对于B的短语 直接短语和句柄 S AB bBB baB baSb S AB ASb bBSb baSb 由语法树可知 21 2 5 2文法的二义性 从前面的讨论可以看出 对于文法G中任一句型的推导序列 我们总能为它构造一棵语法树 现在我们提出一个问题 文法的某个句型是否只对应唯一的一棵语法树呢 也就是 它是否只有唯一的一个最左 最右 推导呢 22 2 5 2文法的二义性 例如设有文法G E 句子i i i有两个不同的最左推导 对应两棵不同的语法树 E E E E E E i 23 2 5 2文法的二义性 最左推导1E E E E E E i E E i i E i i i 最左推导2E E E i E i E E i i E i i i 24 2 5 2文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树 则说这个文法是二义性的 或者说 若一个文法中存在某个句子 它有两个不同的最左 最右 推导 则这个文法是二义性的 E E E E E E i 25 2 5 3文法二义性的消除 1 不改变文法中原有的语法规则 仅加进一些非形式的语法规定 26 2 5 3文法二义性的消除 2 构造一个等价的无二义性文法 即把排除二义性的规则合并到原有文法中 改写原有的文法 例如 对于上例文法G E 将运算符的优先顺序和结合规则 优先于 左结合加到原有文法中 可构造出无二义性文法如下 27 2 5 3文法二义性的消除 则句子i i i只有唯一一棵语法树 E E T T T T F F F E i 28 2 5 3文法二义性的消除 例2定义某程序语言条件语句的文法G为 试证明该文法是二义性的并消除之 分析该文法的句子ifbifbAelseA对应下面两棵不同的语法树 S ifbS ifbSelseS A 其它语句 29 2 5 3文法二义性的消除 所以该文法是二义的 S ifbS ifbSelseS A 句子ifbifbAelseA 30 2 5 3文法二义性的消除 消除文法的二义性可采用下面两种方法 不改变已有规则 仅加进一非形式的语法规定 else与前面最接近的不带else的if相对 文法G的句子ifbifbAelseA只对应唯一的一棵语法树 消除了二义性 31 2 5 3文法二义性的消除 2 改写文法G为G S S1 S2 S1 ifbS1elseS1 A S2 ifbS ifbS1elseS2 G S ifbS ifbSelseS A 其它语句 G 32 2 5 3文法二义性的消除 这是因为通过分析 得知引起二义性的原因是 if else语句的if后可以是if型 因此改写文法时规定 if else之间只能是if else语句或其他语句 33 2 5 3文法二义性的消除 S S1 S2 S1 ifbS1elseS1 A S2 ifbS ifbS1elseS2 对改写后的文法 句子ifbifbAelseA只对应唯一的一棵语法树 34 通常我们只说文法的二义性 而不说语言的二义性 这是因为可能有两个不同的文法G和G 而且其中一个是二义性的 另一个是无二义性的 但却有L G L G 即这两个文法所产生的语言是相同的 2 5 3文法二义性的消除 应该指出的是文法的二义性和语言的二义性是两个不同的概念 35 2 5 3文法二义性的消除 将一个语言说成是二义性的 是指对它不存在无二义性的文法 这样的语言称为先天二义性的语言 例如L aibjck i j或j k且i j k 1 便是这种语言 36 2 6文法和语言的分类 著名的语言学家乔姆斯基 Chomsky 将文法和语言分为四大类 即0型 1型 2型 3型 划分的依据是对文法中的规则施加不同的限制 37 2 6文法和语言的分类 0型文法 无限制文法 若文法G VN VT P S 中的每条规则 是这样一种结构 而且 中至少含一个非终结符 则称G是0型文法 VN VT VN VT 0型文法描述的语言是0型语言 0型文法没有加任何限制条件 又称为无限制性文法 相应的语言称为无限制性语言 0型语言由图灵机识别 38 39 40 41 2 6文法和语言的分类 例如 有0型文法G VN VT P S 其中 VN A B S VT 0 1 其描述的0型语言为L0 G S P S 0AB 1B 0 B SA 01 A1 SB1 A0 S0BSTOP 42 2 6文法和语言的分类 1型文法 上下文有关文法 1型文法也称为上下文有关文法 相应的语言又称为上下文有关语言 若文法G VN VT P S 中的每一条规则的形式为 A 其中 VN VT A VN 则称G是1型文法 1型文法描述的语言是1型语言 1型语言由线性界限自动机识别 VN VT 43 2 6文法和语言的分类 例如 有1型文法G VN VT P S 其中 VN S A B VT a b c P S aSAB abB BA BA BA AA AA AB bA bb bB bc cB cc 其描述的1型语言为L1 G S anbncn n 1 44 2 6文法和语言的分类 2型文法 上下文无关文法 2型文法又称上下文无关文法 其产生的语言又称为上下文无关的语言 若文法G VN VT P S 中的每一条规则的形式为A 其中 A VN VN VT 则称G是2型文法 2型文法描述的语言是2型语言 2型语言由下推自动机识别 45 例如前面描述算术表达式的文法G E E E E E E E i 2 6文法和语言的分类 46 其描述的语言为L2 G S x x a b 且x中a和b的个数相同 例如 有2型文法G VN VT P S 其中 VN S A B VT a b P S aB bA A a aS bAA B b bS aBB 2 6文法和语言的分类 47 2 6文法和语言的分类 3型文法 正规文法 右线性文法和左线性文法都称为3型文法 若文法G VN VT P S 中的每一条规则的形式为A aB或A a 其中 A B VN a VT 则称G是右线性文法 若文法G VN VT P S 中的每一条规则的形式为A Ba或A a 其中 A B VN a VT 则称G是左线性文法 3型文法描述的语言是3型语言 3型语言由有穷自动机识别 3型文法也称正规文法 正规文法产生的语言称为正规语言 48 例如 用左线性正规文法和右线性正规文法定义标识符 2 6文法和语言的分类 用I代表标识符 l代表任意一个字母 d代表任意一个数字 则定义标识符的文法为 左线性文法 P I l Il Id 右线性文法 P I l lTT l d lT dT 49 例如 用左线性正规文法和右线性正规文法定义无符号整数 2 6文法和语言的分类 用N代表无符号整数 d代表任意一个数字 则定义的无符号整数文法为 左线性文法 P N Nd d 右线性文法 P N dN d 50 2 6文法和语言的分类 由上述四类文法的定义可知 从0型文法到3型文法 是逐渐增加对规则的限制条件而得到的 因此每一种正规文法都是上下文无关的文法 每一种上下文无关的文法都是上下文有关的文法 而每一种上下文有关的文法都是0型文法 而由它们所定义的语言类是依次缩小的 有L0 L1 L2 L3 51 2 7有关文法的实用限制和变换 文法是用来描述程序设计语言的 在实际应用中需要对文法加一些限制条件 1 文法中不能含有形如A A的规则 这种规则我们称之为有害规则 对文法的实用限制有以下两点 52 2 7有关文法的实用限制和变换 2 文法中不能有多余规则 所谓多余规则是指文法中出现以下两种规则 1 某条规则A 的左部符号A不在所属文法的任何其他规则右部出现 即在推导文法的所有句子中始终都不可能用到的规则 2 对文法中的某个非终结符A 无法从它推出任何终结符号串来 53 2 7有关文法的实用限制和变换 例如设有文法G S P S Bd A Ad d B Cd Ae C Ce D e 删除多余规则后的文法变换为 P S Bd A Ad d B Ae 54 2 7有关文法的实用限制和变换 若程序设计语言的文法含有多余规则 其中必定有错误存在 因此检查文法中是否含有多余规则对我们来说是很重要的 55 作业 P262 12 2 2 2 3L1 L2 L32 72 82 92 112 12 56 本章重点介绍了语言的语法结构的形式描述 语法树以及文法的二义性 主要内容有 1 设计一个文法定义一个已知的语言 1 文法是一个四元组G VN VT P S 文法四大要素中 关键是一组规则 它定义 或描述 了一个语言的结构 从文法定义可知 文法对于程序设计者来说 文法给出了语言的精确定义和描述 本章小结 本小结花时45分钟2004 2 28 57 2 分析已知语言句子的结构特征 设计出相应的一组规则 但不唯一 4 若语言是无穷集合 设计该语言的文法一定是递归的 本章小结 3 设计的文法必须能定义已知的语言 不能超出或缩小所定义语言的范围 58 分析根据语言句子的结构特征 设计出相应规则 例1 给出语言L2 anbm m n 1 的文法 P2 S AB L2 ab abb abbb aabb aabbb aabbbb aaabbb aabbbb A aAb ab B bB 本章小结 59 分析根据语言句子的结构特征 设计出相应规则 例2 给出语言L1 a2n 1 n 0 的文法 P1 A aB a P1 A aAa a 或 L1 a aaa aaaaa aaaaaaa aaaaaaaaa B aa aBa 本章小结 60 本章小结 分析根据语言句子的结构特征 设计出相应规则 例3 给出语言L3 anbmck n m k 0 的文法 P3 A aA bB cC P3 A aA B 或 L3 a aa aaa b bb bbb c cc ccc ab abb bc bcc C cC B bB cC C cC B bB C 61 本章小结 L4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 例4 写一个文法 使其语言是正偶数的集合 每个偶数不以0开头 P4 N E AE N 0 2 4 6 8 BN 或 分析不以0开头的偶数集合中串的结构特征 A D AD E 0 2 4 6 8 D 1 2 3 9 D 0 1 2 3 9 B 1 2 3 9 B0 P4 62 本章小结 A 0A1 P S 1S0 0A1 例5 给出语言L 1n0m1m0n n m 0 的文法 分析根据语言句子的结构特征 设计出相应规则 L 01 0011 10 1100 1010 100110 110100 11001100 63 本章小结 P S a 0S0 1S1 例6 给出语言L WaWt W 0 1 Wt表示W的逆的文法 分析根据语言句子的结构特征 设计出相应规则 L a 0a0 1a1 01a10 10a01 00a00 11a11 101a101 110a011 100a001 W 0 1 01 10 00 11 101 110 100 111 64 本章小结 2 已知一个文法 确定该文法所定义的语言 2 给定一个文法 可根据语言和推导定义推导出文法的句子 从而确定出该文法所定义的语言 65 本章小结 自然语言描述 例如 L x x a b 且x中a b个数相同 式子描述 例如L a2nbb n 0 正规式描述 3 语言可用 66 本章小结 例1文法G A A a b A bA a A 所生成的语言是什么 分析 A bA bbA bbbA bnA bna L G A bna n 0 67 本章小结 例2文法G N 为 N ND DD 0 1 2 3 4 5 6 7 8 9 1 G N 所生成的语言是什么 2 给出句子0127的最左 最右推导 68 本章小结 L G N 0 1 2 9 为可带前导0的正整数 为数字串 最左推导 N ND N7 ND7 N27 ND27 N127 D127 0127 最右推导 N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 N ND DD 0 1 2 3 4 5 6 7 8 9 69 本章小结 例3 已知文法G S A B a b c d P S 其中P为 分析 S AB aAbB a2Ab2B an 1Abn 1B anbnB anbncBd anbnc2Bd2 anbncm 1Bdm 1 anbncmdm L G S anbncmdm n m 1 该文法所生成的语言是什么 A aAb ab B cBd cd S AB 70 本章小结 3 求句型的短语 直接短语和句柄 1 短语 直接短语和句柄是对某句型而言的 2 短语总是句型的某个子串 它对应子树未端结点形成的符号串 3 直接短语是某条规则右部 它对应简单子树未端结点形成的符号串 4 最左边的直接短语是句柄 71 本章小结 例1已知文法G E 证明E T F是它的一个句型 指出这个句型的短语 直接短语和句柄 E E T E T F 短语 E T F T F E T F是它的一个句型 画出该句型的语法树 句柄 T F 直接短语 T F E E T E T T T T F T F T T E i 2 9相似 72 本章小结 例2已知文法G S 试找出符号串 a 和 A SaA b 的短语 直接短语和句柄 如果有的话 S AS b A SaA a 符号串 a 不是文法的句型 因此它没有短语 直接短语和句柄 2 11 73 本章小结 S AS A AS A A b A SaA b 符号串 A SaA b 是文法的句型 画出该句型的语法树如下图 S AS b A SaA a 74 本章小结 从句型的语法树求短语 A SaA b SaA b SaA b 直接短语 SaA b 句柄 SaA S AS b A SaA a 对于句型 A SaA b 75 本章小结 4 文法二义性的判断 一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左 最右 推导 则该文法是二义性的 76 本章小结 例1设有文法G S S iSeS iS i 试证明文法G S 有二义性 分析因为对文法的句子iiiei有如下两棵不同的语法树与之对应 所以该文法是二义的 77 本章小结 S iSeS iS i 句子iiiei对应下面两颗语法树 78 本章小结 N SE ES SD DE 0 2 4 6 8 10D 0 1 2 3 4 5 6 7 8 9 1 试证明文法G N 有二义性 2 此文法所描述的语言是什么 3 试写出另一文法G 使L G L G 且G 是无二义性的 例2设有文法G N 79 本章小结 分析因为对文法的句子10有两棵不同的语法树与之对应 所以该文法是二义的 N SE ES SD DE 0 2 4 6 8 10D 0 1 2 3 4 5 6 7 8 9 80 本章小结 该文法所描述的语言是所有无符号偶数的集合 可以0开头 改写后的文法G S 为 N SE ES SD DE 0 2 4 6 8D 0 1 2 3 4 5 6 7 8 9 N SE ES SD DE 0 2 4 6 8 10D 0 1 2 3 4 5 6 7 8 9 本节完 81