[编译原理第2章..ppt

2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.4 短语、直接短语和句柄 2.5 语法树与文法的二义性 2.5.1 推导和语法树 例如 设有文法G[E]: 2.5.1 推导和语法树 根据推导过程构造句型i*i+i的语法树如下： 2.5.1 推导和语法树 2.5.1 推导和语法树 2.5.1 推导和语法树 3.5.1 推导和语法树 3.5.1 推导和语法树 2.5.1 推导和语法树 2.5.1 推导和语法树 2.5.1 推导和语法树 2.5.1 推导和语法树 2.5.2 文法的二义性 2.5.2 文法的二义性 2.5.2 文法的二义性 2.5.2 文法的二义性 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2. 构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中, 改写原有的文法。 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.5.3 文法二义性的消除 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 例如，用左线性正规文法和右线性正规文法定义标识符 2.6 文法和语言的分类 例如，用左线性正规文法和右线性正规文法定义无符号整数 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.6 文法和语言的分类 2.7 有关文法的实用限制和变换 2.7 有关文法的实用限制和变换 2.7 有关文法的实用限制和变换 2.7 有关文法的实用限制和变换 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 例1 文法G[A]=({A},{a,b},{A→bA | a}, A) 所生成的语言是什么？ 分析 ∵ A?bA?bbA?bbbA?…?bnA?bna ∴ L(G[A])={ bna | n≥0 } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 本章小结 例2 文法G[N]为: N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1) G[N]所生成的语言是什么？ (2) 给出句子0127的最左、最右推导。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 本章小结 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 | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例3. 已知文法G[S]=( {A,B},{a,b,c,d}, P, S ) , 其中 P 为: 分析 ∵ S?AB?aAbB?a2Ab2B?… ?an-1Abn-1B?anbnB?anbncBd ? anbnc2Bd2 ? … ? anbncm-1Bdn-1?