编译原理-第2章-文法和语言.ppt

* * * 2.7 短语、简单短语和句柄 求一个句型的短语、简单短语和句柄的方法: 语法树（建议用该方法）：由文法的开始符号开始，通过产生式来构造与该句型相对应的语法树。 推导法：由文法的开始符号开始，找出该句型的所有推导。 2.9 子树和短语 例 已知文法： E::=E+T|T T::=T*F|F F::=(E)|i 句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的短语、简单短语和句柄。 2.9 子树和短语 句型E+(E+T)*i的短语为： E+(E+T)*i、 (E+T)*i 、 (E+T)、 E+T 、 i 句型E+(E+T)*i的简单短语为： E+T 、 i 句型E+(E+T)*i的句柄为： E+T 2.9 子树和短语 例 G[S]: S→aAS A→SbA A→SS S→a A→ba 求句型aabbaa的短语、简单短语和句柄。 句型aabbaa的短语为： aabbaa 、 abba、 a(左起第2个) 、 ba 、 a(最后1个) 句型aabbaa的简单短语为： a(左起第2个) 、 ba 、 a(最后1个) 句型aabbaa的句柄为： a(左起第2个) 2.11 文法的二义性 二义性文法：如果一个文法所定义的某个句子或句型，它存在两棵（或两棵以上）不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。 例2-11(P23) 有文法G[E]：E∷= E+E | E*E |（E）| i，分析该文法是否为二义性文法。 E E + E E * E i i i E E * E E E i i i + 解：句子i+i*i存在两棵不同的语法树，因此文法G 是二义性文法。 2.11 文法的二义性 E E + E E * E i i i E E * E E E i i i + 语法树1 在语法树1中， i+i*i的规范推导为： E?E+E?E+E*E?E+E*i?E+i*i?i+i*i 即，在语法树1中的*先作为句柄归约，表示*优先于+进行运算。 语法树2 二义性产生的后果会导致分析结果不同，导致对句子的理解不同。因此，在算术表达式中规定乘除高于加减，从而避免二义性。 在语法树2中， i+i*i的规范推导为： E?E*E?E*i?E+E*i?E+i*i?i+i*i 即，在语法树2中的+先作为句柄归约，表示+优先于*进行运算。 × √ 2.11 文法的二义性 例2-12 if语句文法如下： 语句∷= if布尔表达式then语句 |if布尔表达式then语句else语句 |其它 说明该文法是二义性文法。 解：假设有一个if语句嵌套的句型为： if布尔表达式then if布尔表达式then语句else 语句 该句型存在两棵不同的语法树，所以该文法是二义性文法。 2.11 文法的二义性 语句 布尔表达式 if then 语句 布尔表达式 if then 语句 else 语句 语句 布尔表达式 if then 语句 布尔表达式 if then 语句 else 语句 语法树1 语法树2 语法树1意味着else和第2个if配对（就近配对），语法树2表示else和第1个if配对。 因此，在if语句中规定else与最近的if配对(即就近配对)。 × √ 2.11 文法的二义性 文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内确切地判定一个文法是否是二义性的。 例2-13 改写文法G[E]： E∷= E+E | E*E |（E）| i，使其无二义性。 解： 新添非终结符号T和F，将文法改写成： E∷= T |E+T，T∷=F |T*F，F∷= (E) | i 这样，就避免了二义性。用改写后的文法给出句i+i*i的语法树如右图所示。此时的语法树是唯一的。 E T + E F * T T i F F i i 2.12 有关文法的实用限制 文法的实用限制：就是从实用的观点出发，对文法做一些必要的限制。以下是对文法的实用限制： 文法不能是二义性的。 不能有U∷=U这样的有害规则。 不能有多余规则 推导中始终用不到的规则。(不可达规则) 一旦使用某规则后无法推出终结符号串的规则。(无用规则) 2.12 有关文法的实用限制 检查多余规则的方法：检查文法中每一条规则左部的每个非终结符号U是否满足下述两个条件： (1) U必须在某个句型中出现，即有：Z xUy