编译原理清华大学第3章 文法和语言.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 小 结 掌握符号串和符号串集合的运算、文法、句型、句子和语言的定义 几个重要概念：推导、归约、递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。 掌握文法的表示：BNF、扩充的BNF范式、语法图。 了解文法分类。 本 章 作 业 48页：3题，4题，5题，7题， 11题 * * * * * * * * * * A＝{u,v},B={m,n}, AB={um,un,vm,vn} 因为εx＝xε＝x，所以{ε}A={ε}A=A * * * * * * * * * * * * * * * * * * * * 3.3.3 语言的形式定义 文法G[Z]所产生的 所有句子的集合 定义7：文法G[Z] （1）句型：x是句型 ? Z ? x,且x∈V*； * * （2）句子：x是句子 ? Z ? x, 且x∈VT*； * （3）语言：L（G[Z]）={x| Z ? x， x∈VT* }； 即：句型是由文法开始符号推导出来的 由终结符和非终结符组成的符号串。 即：句子是由文法开始符号推导出来的 由终结符组成的符号串。 例：{abna|n≥1}，构造其文法 G1[Z]： Z→aBa B→b|bB G2[Z]： Z→aBa, B→b|Bb 定义8: G和G是两个不同的文法，若 L(G) = L(G) , 则G和G’为等价文法。 编译感兴趣的问题是: 给定x, G, 求x ? L(G) ? x 算法1 算法2 x ? L(G) ? G y n 出错处理 停机 3.3.4 递归文法 1.递归产生式：产生式右部有与左部相同的符号 对于 U::= xUy 若x=ε,即U::= Uy，左递归； 若y=ε,即U::= xU，右递归； 2.递归文法：文法G，存在U ∈VN if U==…U…, 则G为递归文法； if U==U…, 则G为左递归文法； if U==…U, 则G为右递归文法； + + + 4. 递归文法的优点：可用有穷条产生式，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？ ! 3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析 会造成死循环（后面将详细论述） 3.4 文法分类 形式语言：用文法和自动机所描述的没有语义的语言。 文法定义：乔姆斯基将所有文法都定义为一个四元组： G=（VN，VT，P，Z） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（开始符号） Z∈VN 语言定义： L（G[Z]）={x| Z==x , x∈VT*, } * 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。 定义9：0型文法： P： u::=v 其中u∈V* ，v∈V* 0型语言：L0 这种语言可以用图灵机(Turing)接受. 0型文法称为短语结构文法。产生式的左部和右部都可 以是符号串，一个短语可以产生另一个短语。 定义10： 1型文法： P： xUy::= xuy ︱ 其中 U∈VN， x、y、u∈V* 1型语言：L1 这种语言可以由一种线性界限自动机接受. 称为上下文敏感或上下文有关。也即只有在x、y这样的 上下文中才能把U改写为u 定义10： 1型文法： P： u::= v ︱u ︱≥ ︱v ︱ u, v ∈V* 定义11：2型文法： P： U::= u 其中 U∈VN， u∈V* 2型语言：L2 这种语言可以由下推自动机接受. 称为上下文无关文法。也即把U