chapter2文法和语言.ppt

语法树子树的末端结点符号串即是语法树所描述句型的短语； 简单子树（只有父子两代）的末端节点符号串即是简单短语； 最左简单子树的末端节点符号串即为句柄。 语法树与短语的关系 【例】给定文法G[S] S-aAcBe A-b A-Ab B-d （1）若有句型aAbcde，试问b是它的直接短语吗？ （2）它的短语是什么？句柄是什么？ （3）写出句子abbcbe的最左推导过程 句型aAbcde对应的语法分析树如下： 句型aAbcde的短语为aAbcde、Ab、d，简单短语为Ab、d，句柄为Ab e S a A c b B d A 【例】文法G[E]： E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i 的短语、直接短语、句柄。 句型i*i+i对应的语法分析树如下： E T T E i1 + F * T F F i3 i2 短语： i1,i2,i3,i1*i2,i1*i2+i3直接短语： i1,i2,i3 句柄： i1 有关文法实用中的一些说明 限制化简文法 文法中不含有有害规则和多余规则 有害规则：形如U→U的产生式,会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则。 文法中不含有不可到达和不可终止的非终结符 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。 对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1. A必须在某句型中出现 即有S =* αAβ，其中α，β属于V* 2. 必须能够从A推出终结符号串t来 即A =* t，其中t∈VT* 化简文法 例：G[S] ： 1) S→Be 2) B→Ce D为不可到达 3) B→Af C为不可终止 4) A→Ae 5) A→e 6) C→Cf 7) D→f 产生式 2），6），7）为多余规则应去掉。 2、上下文无关文法中的ε规则 具有形式A→ε的规则称为ε规则，其中A∈VN 。 某些著作和讲义中限制这种规则的出现。因为ε规则会使有关文法的一些讨论和证明变得复杂。 两种定义的唯一差别是ε句子在不在语言中。 如果语言L有一个有穷的描述，则L∪{ε}也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有关语言、上下文无关语言和正规语言。 定理3.1 文法G，P中的每一个产生式的形式均为A→α，其中A∈VN，α∈(VN ∪VT)*(即α可能为ε)，则L(G)也能由这样一种文法产生：每一个产生式或者为A→β形式，其中A∈VN，β ∈(VN ∪VT)+(即β≠ε)，或者 S→ε且 S不出现在任何产生式右边。 定理3.2G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法，类似结论成立。 【例】试写一文法，使其描述的语言L(G) 是能被5整除的整数集合。 解： G(Z): Z ?(+|- )A(0|5) A ?0|1|2|3|4|5|6|7|8|9|AA 解： G(Z)： Z ?aZa|bZb|cZc|a|b|c|? 【例】 已知语言L={x | x?{a,b,c}*,且x重复排列是 对称的（aabcbaa,aabbaa,等) 写出该语言的文法。 首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。 文法的类型 语言学家乔姆斯基把文法分为四种类型： 0型、1型、2型、3型。0行强于1型，1行强于2型，2型强于3型。这几种文法的差别在于对产生式施加不同的限制。 0型文法 对文法的生成规则没有任何限制。在计算机语言应用中很少见。 1型文法（上下文有关文法） 在推导过程中，要依据上下文才能作相应替换。实际程序设计语言可能包含这种上下文有关的成分，但不是主要的。 2型文法（上下文无关文法） 是描述程序