二义性(1) 二义性( ambiguous) 个文法可以为某个 句子生成多棵语法分析树,这个文法就是二义 性的 ·例子: E=>EtE=>id+E=>id+EE=> id+id e=>id+id *id E=>EE=>E+EE=>id+EE=> id+id*E=> id+id id E E E E E id E EE+ E id 图4-5id+idid的两棵语法树
二义性（1） • 二义性（ambiguous）：一个文法可以为某个 句子生成多棵语法分析树，这个文法就是二义 性的 • 例子： – E => E+E => id+E=>id+E*E => id+id*E=>id+id*id – E => E*E => E+E*E=>id+E*E => id+id*E=> id+id*id
二义性(2) ·程序设计语言的文法通常都应该是无二义性的 否则就会导致一个程序有多种“正确”的解释。 比如文法:E→E|E+E|E*E|(E)id的旬子 a+b*c 但有些二义性的情况可以方便文法或语法分析 器的设讣 但是需要消二义性规则來剔除不要的语法分析树 比如:先乘除后加减
二义性（2） • 程序设计语言的文法通常都应该是无二义性的 – 否则就会导致一个程序有多种“正确”的解释。 – 比如文法：E → -E | E+E | E*E | (E) | id 的句子 a+b*c • 但有些二义性的情况可以方便文法或语法分析 器的设计。 – 但是需要消二义性规则来剔除不要的语法分析树 – 比如：先乘除后加减
证明文法生成的语言 ·证明文法G生成语言L可以帮助我们了解文法可以生 成什么样的语言, 基本步驟 首先证明L(G)∈L 然后证明L<L(G 般使用数学归纳法 证明L(G<L的方法之 构造L,使得L∩Vt*L;并证明S∈L,且对于L中的 任意α,=>β可推出β也在L中。 也可以按照推导序列长度进行数学归纳 证明LcLG时,通常可按照号串的长度来构造推 导序列
证明文法生成的语言 • 证明文法G生成语言L可以帮助我们了解文法可以生 成什么样的语言。 • 基本步骤： – 首先证明L(G)L – 然后证明LL(G) – 一般使用数学归纳法 • 证明L(G)L的方法之一： – 构造L’，使得L’Vt*=L；并证明S∈L’，且对于L’中的 任意α，α=>β可推出β也在L中。 – 也可以按照推导序列长度进行数学归纳 • 证明LL(G)时，通常可按照符号串的长度来构造推 导序列
文法生成语言的例子(1) 文法:S→(S)S|e 语言:所有具有对称括号对的串 L(G)<L的证明: 令L={删除S后括号对称的串},显然有L7∩Vt*=L 且S∈L 任意的删除S后括号对称的串,不管使用S→ε还是 (S)S推号出串β,删除β中的S后得到的串仍然是括 号对称的。 有上面两点可知:G的所有句型都属于L,.且L中 的终结符号串就是L。可知L(G)L
文法生成语言的例子（1） • 文法：S→(S)S | ε • 语言：所有具有对称括号对的串 • L(G)L的证明： – 令L’={删除S后括号对称的串}，显然有L’Vt*=L 且S ∈L’ – 任意的删除S后括号对称的串α，不管使用S→ε还是 (S)S 推导出串β，删除β中的S后得到的串仍然是括 号对称的。 – 有上面两点可知：G的所有句型都属于L’，且L’中 的终结符号串就是L。可知L(G)L
文法生成语言的倒子(2) LcL(G)的证明: 注意:括号对称的串的长度必然是偶数, 归纳基础:如果括号对称的串的长度为0,显 然它可以从S推导得到 归纳步骤:假设长度小于2n的括号对称的串都 能够由S推导得到。假设W是括号对称且长度 为2n的串 W必然以左括号开头,且w可以写成(x的形式,其 中也是括号对称的。因为X、y的长度都小于2n, 根据归纳假设,ⅹ和y都可以从S推导得到。 因此S=>(S)S=*=>(x)y
文法生成语言的例子（2） • LL(G)的证明： – 注意：括号对称的串的长度必然是偶数。 • 归纳基础：如果括号对称的串的长度为0，显 然它可以从S推导得到 • 归纳步骤：假设长度小于2n的括号对称的串都 能够由S推导得到。假设w是括号对称且长度 为2n的串 – w必然以左括号开头，且w可以写成(x)y的形式，其 中x也是括号对称的。因为x、y的长度都小于2n， 根据归纳假设，x和y都可以从S推导得到。 – 因此S=>(S)S=*=>(x)y