ch3-1语法分析概述.pptVIP

习题二 xy2z=xxyz yxzyz yxxxyxz yxxyxzxz yxyxzxzxz yyxzxzxzxz S→AB2C S→BMC|BA3BAC|BA2B(AC)2|BAB(AC)3 |BB(AC)4 M→ACB 习题二 2.4 1型文法 习题二 2.6 (1)最左：N ? ND ?NDD ?NDDD ?DDDD ?3DDD ?32DD ?327D ? 3274 最右：N ? ND ?N4 ?ND4 ?N74 ?ND74 ?N274 ?D274 ? 3274 (2)最左：N ? ND ?NDD ?NDDD ?NDDDD ?6DDDD ?65DDD ?651DD ? 6517D? 65173 最右：N ? ND ?N3 ?ND3 ?N73 ?ND73 ?N173 ?ND173 ? N5173 ? D5173 ? 65173 习题二 2.7 （1）考察句子abc，文法是二义的。 S A B a b c S A B c a b 习题二 （2）考察句子123，文法是二义的。 U D D D 1 D D 2 3 U D D D 3 D D 1 2 习题二 2.8 （1）去掉：无用非终结符：F、P、G 不可到达非终结符：Q、S 多余产生式E→ E 剩余： Z→E+T E →T T→T*i|i （2）不用改变 典型例题及解答 例： 文法G[S]: S ? Be B ? Ce | Af A ? Ae | e C ? Cf D ? f 请判断其中是否有多余规则 化简文法: 1）文法中某些非终结符不在任何规则的右部出现； 2）文法中某些非终结符，由它不能推出终结符号串。 化简文法 例：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）为多余规则应去掉。 典型例题及解答 1.证明文法G=({E,O},{(,),+,*,v,d},P,E)是二义的 E →EOE|(E)|v|d O →+|* 典型例题及解答 1.证明文法G=({E,O},{(,),+,*,v,d},P,E)是二义的 E →EOE|(E)|v|d O →+|* 只要存在一个句型，其语法树不只一棵，则可证明文法的二义性 v*v+v 2. 考虑以下的两个语言，给出其文法，并证明它们都是上下文无关的。 L1={anb2ncm|n,m=0} L2={anbmc2m| n,m=0} 2. 考虑以下的两个语言，给出其文法，并证明它们都是上下文无关的。 L1={anb2ncm|n,m=0} L2={anbmc2m| n,m=0} L1: S →AB A → ε|aAbb B → ε|cB L2: S →AB A → ε|aA B → ε|bBcc 推导树/分析树 推导树的理解： 推导树表示了在推导过程中用到什么样的产生式和用到哪些非终结符。 并没有表明采用的顺序。 只表示推导的结果，不表示推导的过程。 推导树/分析树 推导树与语言和文法的关系： ① 每一直接推导（每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子； ② 分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。 推导树/分析树 说明： 推导树的叶子从左向右的连接是句子。 推导树生成过程中的叶子从左向右的连接是句型。 语法树 语法树 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树： （1） 根与内部节点由表达式中的操作符标记； （2） 叶子由表达式中的操作数标记； （3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。 例3.6 句子-(i+i)和句型if C then s1 else s2 ： S → if C then S1 else S2 分析树：左部非终结符“产生”右部文法符号序列； 语法树：操作符（运算）“作用于”操作数（运算对象）； 习惯上：和语法树被分别称为具体语法树和抽象语法树。 推导树与语法树 语法树 语法树 推导树/分析树 推导树/分析树 推导树 例：已知文法：G[E] E→E+T|T T→T*F|F F→(E)|i 句子：i+i*i的推导有： 最右推导: E?E+T ?E+T*F ?E+T*i ?E+F*I ?E+i*I T+i*i ?F+i*i ?i+i*i 混合推导： E?E+T