第3章文法和语言.ppt

例：给定文法G： E→T | E+T | E－T T→F | T*F | T／F F→i | (E) 符号串（T+i）*i－F是文法G的一个句型，求其短语、简单短语和句柄。 E ? E－T ? T－T ? T－F ? T*F－F ? F*F－F ? (E) *F－F ? (T +T) *F－F ? (T +F) *F－F ? (T +i) *F－F ? (T +i) *i－F ? (T +i) *i－F 解：短语有8个： 1. E? E，E?（T+i）*i－F 则有：（T+i）*i－F 2. E? T－F，T?（T+i）*i 则有：（T+i）*i 3. E? T *i－F，T?（T+i） 则有：（T+i） 4. E? (E) *i－F，E?T+i 则有： T+i 5. E? (E +i) *i－F，E?T 则有： T 6. E? (T +F) *i－F，F?i 则有： 第一个i 7. E? (T +i) *F－F，F?i 则有： 第二个i 8. E? (T +i) *F－T，T?F 则有： F * + * + * + * + * + * + * + * + 定义: 给定文法G[Z], w=xuy∈V+，为该文法的句型, 若 Z?xUy, 且U ? u, 则u是句型w相对于U的短语； 若 Z?xUy, 且U ? u, 则u是句型w相对于U的简单短语。 其中U ∈VN，u ∈V+，x,y ∈V* * * ＋ U 其简单短语有4个： 1. E? (E +i) *i－F,E?T 则有： T 2. E? (T +F) *i－F,F?i 则有： 第一个i 3. E? (T +i) *F－F,F?i 则有： 第二个i 4. E? (T +i) *F－T,T?F 则有：F 句柄有1个： T E E － T T T * F F ( E ) F i E + T T F i 用语法树求短语、简单短语和句柄的方法： 1）每个句型都有一棵语法树； 2）每棵语法树的叶（从左到右）组成一句型； 3）每个子树 的叶（从左到右）组成一短语； 4）每个简单子树 的叶（从左到右）组成一简单短语； 5）最左简单子树 的叶（从左到右）组成一句柄。 只需画出句型的语法树，然后根据子树找短语→简单短语→句柄。 3.7 有关文法的实用限制 在实用中，我们将限制文法中不得含有有害产生式和多余产生式。 有害产生式： 若文法中有如U::=U的产生式，则这就是有害产生式，它会引起二义性。 例如存在U::=U， U::= a | b,则有两棵语法树： U a U U a 多余产生式： （1）在推导文法的所有句子中，始终用不到的产生式。即该产生式的左部非终结符不出现在任何句型中。 （2）在推导句子的过程中，一旦使用了该产生式，将推不出任何终结符号串。即该产生式中含有推不出任何终结符号串的非终结符。 例如给定G[Z]，若其中关于U的产生式只有如下一条： U::=xUy 该产生式是多余产生式。 若还有U::=a，则此产生式并非多余 若某文法中无有害产生式或多余产生式，则称该文法是压缩过的。 小 结 掌握符号串和符号串集合的运算、文法、句型、句子和语言的定义 几个重要概念：推导、归约、递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。 掌握文法的表示 掌握利用语法树找句型的语法单元 了解文法分类。 思考题 问题1：*闭包与正则闭包有什么区别，二则是否可能相等？ 问题2：语法树与推导是否一一对应？ 本 章 作 业 P48： 5#，7#， 13(3) # 设有文法G(S)为： S→(B)a B →Bb│b│ε 下列叙述错误的是： A.G是2型文法 B.L(G) = {(bn)a │n≥0} C.L(G) = {(b)na │n≥0} D.有文法G’为S→ ( )a│(B)a B →bB│b,则G=G’ * A＝{u,v},B={m,n}, AB={um,un,vm,vn} 因为εx＝xε＝x，所以{ε}A={ε}A=A 3.3.2 推导与归约 定义2： 直接推导：文法G：