02第2章文法和语言.pptVIP

* E?E+E ?E+E*E ?E+E*a ?E+a*a ?a+a*a E ?E*E?E*a ?E+E*a?E+a*a ?a+a*a E E + E E * E a a a E E * E + E E a a a 最右推导 * 2.11 文法的二义性 例2.10 IF语句文法如下： 语句 ? IF布尔表达式THEN语句 |IF布尔表达式THEN语句ELSE语句 |其它 说明该文法是二义性文法。 解：假设有一个IF语句嵌套的句型为： IF布尔表达式THEN IF布尔表达式THEN语句ELSE 语句 根据文法可构造两棵语法树： * * 2.11 文法的二义性 语句 布尔表达式 IF THEN 语句 布尔表达式 IF THEN 语句 ELSE 语句 语句 布尔表达式 IF THEN 语句 布尔表达式 IF THEN 语句 ELSE 语句 图2.3(a) IF语句语法树1 图2.3(b) IF语句语法树2 由于这两棵语法树不同，该文法是二义性文法。图2.3(a)IF语句的语法树意味着ELSE和第2个IF配对（就近配对），而图2.3(b)IF语句的语法树表示ELSE和第1个IF配对。 * * 可以采用两种途径来解决文法的二义性问题 不改变文法中原有的规则，仅加进一些语法的非形式规定。例如：规定“*”运算优先级高于“+”运算，且服从左结合 改写文法，把排除二义性的规则合并到原有文法中 例2.11，改写文法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这样的有害规则。 不能有多余规则：一是推导中始终用不到的规则。二是一旦使用某规则后无法推出终结符号的规则。 多余规则不满足以下两个条件： 1) U必须在某个句型中出现，即有：Z xUy 2) 必须能够从U推导出终结符号串，即U t，t∈Vt* * * * ? + ? 2.12 有关文法的实用限制 例：有文法：Z → Aa，A → Ca|Bb，B → Ba|a，C → Cb ，D →b ， 去掉有害规则和多余规则。 解：D → b，C → Cb，A → Ca是多余规则，应该去掉。最后得到的文法为： Z → Aa A → Bb B → Ba|a * * 2.13文法和语言分类 形式语言(乔姆斯基)：通过抽象，对语言进行形式化描述 用一组数学符号和规则来描述的语言称为形式语言 　　?*的任何子集称作?上的形式语言 L（G[S]）={α | α ∈VT*,S ? α } + 由文法定义语言 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。 * * 0型语言：L0 0型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。 0型：P： α → β 其中α∈V+且至少含有一个非终结符，β∈V* * * 0型文法 G[S]: S→ABS|AB AB→BA A→0 B→1 L(G[S])={x|x是由n个01或10组成的二进制数字串，n≥1} 该文法产生的语言为 * * S→ACaB Ca→aaC CB→DB aB→Ba CB→E aD→Da AD→AC aE→Ea AE→ε 例：0型 文法G[S]： * * 1型文法 ： P： αAβ → αγβ 其中 A∈VN，α，β ∈V*， γ ∈V＋ 1型语言：L1 称为上下文敏感或上下文有关。也即只有在α 、 β这样的 上下文中才能把A改写为γ * * S→aSBE S→aBE BE→bE aB→ab bB→bb bE→be eE→ee 例：1型（上下文有关）文法G[S]： * * 2型： P： A → β 其中 A∈ VN ， β ∈V* 2型语言：L2 称为上下文无关文法。也即把A改写为β时，不必考虑上下文。 * * 例：2型（上下文