句型/句子/语言 句型(Sentential form) 如果S±>，那么x就是文法S的句型 可能既包含非终结符号，又包含终结符号，也可以是 空串 0 句子(Sentence) 文法的句子就是不包含非终结符号的句型 语言 文法G的语言就是G的句子的集合，记为L(G) 0在L(G)中当且仅当0是G的句子，即S±>0 12
句型/句子/语言 • 句型 (Sentential form) – 如果S α，那么α就是文法S的句型 – 可能既包含非终结符号，又包含终结符号，也可以是 空串 • 句子 (Sentence) – 文法的句子就是不包含非终结符号的句型 • 语言 – 文法G的语言就是G的句子的集合，记为L(G) – w在L(G)中当且仅当w是G的句子，即S w 12 南大编译许畅
语法分析树 。推导的图形表示形式 根结点的标号是文法的开始符号 每个叶子结点的标号是非终结符号、终结符号或ε 每个内部结点的标号是非终结符号 每个内部结点表示某个产生式的一次应用 结点的标号为产生式头，其子结点从左到右是产生式的体 树的叶子组成的序列是根的文法符号的一个句型 。一棵语法分析树可对应多个推导序列 但只有唯一的最左推导及最右推导 13
语法分析树 • 推导的图形表示形式 – 根结点的标号是文法的开始符号 – 每个叶子结点的标号是非终结符号、终结符号或ε – 每个内部结点的标号是非终结符号 – 每个内部结点表示某个产生式的一次应用 • 结点的标号为产生式头，其子结点从左到右是产生式的体 • 树的叶子组成的序列是根的文法符号的一个句型 • 一棵语法分析树可对应多个推导序列 – 但只有唯一的最左推导及最右推导 13 南大编译许畅
语法分析树的例子 文法：E→-EIE+EIE*EI(E)Iid 。句子：-(id+id) E X E 入/ id id 图4-3-(id+id)的 语法分析树 14
语法分析树的例子 • 文法：E → – E | E + E | E * E | ( E ) | id • 句子：– ( id + id ) 14 南大编译许畅
从推导序列构造分析树的例子 ，推导序列 E=>-E=>-(E)=>-(E+E)=>-(id+E) =>-(id+id) E E E → E E ② E E E E E E E id id id 图4-4推导(4.8)的语法分析树序列 16
从推导序列构造分析树的例子 • 推导序列 – E => – E => – ( E ) => – ( E + E ) => – ( id + E ) => – ( id + id ) 16 南大编译许畅
二义性(1) 。 二义性(Ambiguity):如果一个文法可以为某个 句子生成多棵语法分析树，这个文法就是二义的 例子 E=>E+E=>id+E=>id+E*E=>id+id*E =>id +idid E=>E*E=>E+E*E=>id+E*E=>id+id*E =>id +id *id E E E E E id E E E E id 都是最左推导 id id id id a) b) 图4-5id+id*id的两棵语法树 17
二义性 (1) • 二义性 (Ambiguity)：如果一个文法可以为某个 句子生成多棵语法分析树，这个文法就是二义的 • 例子 – E => E + E => id + E => id + E * E => id + id * E => id + id * id – E => E * E => E + E * E => id + E * E => id + id * E => id + id * id 17 都是最左推导 南大编译许畅