第二章语言的基本知识

第二章语言的基本知识内容摘要：

α n或者 α 0 α n +  +  *  二 . 定义 直接推导和推导的定义 22 例： E  E+T T+T F+T a+T a+F a+a  A     产生式  E  E+ T E  E+ T  E+ T  T+ T E  T  +TT+ T  F +T T  F  +TF +T  a +T F  a  +Ta +T  a +F T  F a+ a +F  a +a F  a a+ 23 设文法 G＝（ VT， VN， S,P）。 如果 S α ,则称 α 是一个句型。 仅含终结符号的句型是一个句子。 语言 L(G） 是由文法 G产生的所有句子所组成的集合： L(G)＝ {α |S α 且 α ∈V T*} 例 考虑一个文法 G＝ ({a,b},{S},S， P）其中 P： SaSb ab SaSb  aaSbb  a3Sb3  ……  an1Sbn1  anbn *  +  三 . 定义 ： 语言的定义 24 设 G=(VT={a,b},VN={S,A,B},S,P} P由下列产生式组成 :S→aB|bA A→a|aS|bAA B→b|bS|aBB L(G)={w|w∈{a,b} +,且 w中有相同个数的 a和 b}。 用归纳法证明下面结论（对 w的长度） ： (1)S w,当且仅当 w中含有相同个数的 a和 b。 (2)A w,当且仅当 w中 a的个数比 b的个数多一个。 (3)B w,当且仅当 w中 b的个数比 a的个数多一个。 归纳基础 当 |w|=1， Aa, B  b, 不能从 S导出长度 为 1的终极行 ,则上述结论显然成立。 * * * 例 25 设 (1),(2)和 (3)对于长度不超过 k1的所有 w都成立。 那么，证明对 |w|=k也成立。 对于（ 1），推导的第一步必是 SaB或 SbA, 对于第一种情形，必有 w=aw1且 B w1， |w1|=k1， 它含的 b个数比 a多一个，因此， w中 a,b的个数相等。 推导的第一步是 SbA,证明完全类似。 反之， |w|=k, w中 a,b的个数相等 ,要证 S w。 考虑的 S推导，推导出的开始符号，或为 a或为 b。 若 SaB,B w1, |w1|=k1, w1中 b的个数比 a多一个 ,w= aw1。 若 S bA， 证明和类 SaB类似。 （ 2）和（ 3）的证明留给同学们。 * * * 归纳步骤26 : 对于 w和 G, wL(G)  是 否存在 S w， 如何构造   例 如， G[E]（ 例 ）和 w=a+a  a EE+T T+T F+T a+T a+TF a+F F a+a F a+aa（ 最左） 特点： A   (A) ， VT* EE+T E+T F E+ T a E+Fa E+aa T+aa F+aa a+aa 特点： A   (A)，  VT*（ 最右） +  四 . 最左推导和最右推导 27 令 G[S]是一个文法，如果有 S α Aδ 且 A β 则称 β 是一个关于非终结符号 A的，句型αβδ 的短语。 其次如果有 S α Aδ 且 Aβ 则称 β 是直接短语。 一个句型的最左直接短语称为该句型的句柄。 文法（ 2． 1）的一个句型 a1*a2+a3 ， 尽管 有 E a2＋ a3 ， 但是 a2＋ a3 并不是该句型 的一个短语 ,因为不存在 E a1*E。 短语： a1,a2,a3， a1 *a2,a1*a2+a3 直接短语 :a1， a2 ,a3 句柄 :a1 +  *  *  +  +  定义 28 分析树和二义性 一 . 分析树的定义 二 . 如何画出分析树 三 . 子树 四 . 二义性文法的定义 五 . 在构造编译程序中如何处理 二义性文法 29 设 G=（ VT， VN， S， P） ,G的一棵分析树满足如下条件： 1. 每一个结点有一个标记，此标记是 VT∪V N∪{ ε }中的符号。 2．根的标记是 S。 3．如果一个结点是内部结点，且有标记 A,那么 A必在 VN中。 4．如果编号为 n的结点有标记 A,结点n1,n2,…,n k是点 n的从左到右的儿子，并分别有标记 X1,X2,… ,Xk， 则 AX1X2… Xk必须是 P中的产生式。 5. 如果结点 n有标记 ε ，那么结点 n是叶子，且是它父亲唯一的儿子。 一 .分析树的定义 30。