第三章语法分析ppt课件.ppt

3 3已知文法G S 为S aSb Sb b 试证明文法G S 为二义文法 解答 由文法G S S aSb Sb b 对句子aabbbb可对应如图所示的两棵语法树 因此 文法G S 为二义文法 对句子abbb也可画出两棵不同语法树 3 3已知文法G S 为S aSb Sb b 试证明文法G S 为二义文法 解答1 由文法G S S aSb Sb b 对句子abbb可对应如图所示的两棵语法树 因此 文法G S 为二义文法 3 3已知文法G S 为S aSb Sb b 试证明文法G S 为二义文法 解答2 由文法G S S aSb Sb b 对句子abbb存在两种不同的最右推导 S aSb aSbb abbbS Sb aSbb abbb 因此 文法G S 为二义文法 3 4已知文法G S 为S SaS 试证明文法G S 为二义文法 解答1 由文法G S S SaS 句子aa的语法树如图所示 因此 文法G S 为二义文法 3 4已知文法G S 为S SaS 试证明文法G S 为二义文法 解答2 由文法G S S SaS 句子aa存在两种不同的最右推导 S SaS Sa SaSa Saa aaS SaS SaSaS SaSa Saa aa 因此 文法G S 为二义文法 3 6有文法G S S aAcB BdA AaB cB bScA b 1 试求句型aAaBcbbdcc和aAcbBdcc的句柄 2 写出句子acabcbbdcc的最左推导过程 3 6有文法G S S aAcB BdA AaB cB bScA b 解答 1 句型aAaBcbbdcc的最右推导S aAcB aAcbScA aAcbScc aAcbBdcc aAcbbdcc aAaBcbbdcc 退六步 aAaBcbbdcc退五步 AaB bbdcc退四步 AaB bd c退三步 AaB bd退两步 AaB b退一步 AaB 句型aAaBcbbdcc的短语 AaB b bd c bbdcc aAaBcbbdcc句型aAaBcbbdcc的直接短语 AaB b c句型aAaBcbbdcc的句柄 AaB 3 6有文法G S S aAcB BdA AaB cB bScA b 解答 1 句型aAcbBdcc的最右推导S aAcB aAcbScA aAcbScc aAcbBdcc 退四步 aAcbBdcc退三步 bBdcc退两步 Bd c退一步 Bd 句型aAcbBdcc的短语 Bd c bBdcc aAcbBdcc句型aAcbBdcc的直接短语 Bd c句型aAcbBdcc的句柄 Bd 图3 4习题3 6的语法树 a aAaBcbbdcc b aAcbBdcc 3 6有文法G S S aAcB BdA AaB cB bScA b 解答 1 分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3 4的 a b 所示 对树 a 直接短语有3个 AaB b和c 而AaB为最左直接短语 即为句柄 对树 b 直接短语有两个 Bd和c 而Bd为最左直接短语 3 6有文法G S S aAcB BdA AaB cB bScA b S aAcB aAaBcB acaBcB acabcB acabcbScA acabcbBdcA acabcbbdcA acabcbbdcc 解答 2 句子acabcbbdcc的最左推导如下 3 7对于文法G S S L aS aL L S S 1 画出句型 S a 的语法树 2 写出上述句型的所有短语 直接短语 句柄 素短语和最左素短语 图3 5句型 S a 的语法树 3 7对于文法G S S L aS aL L S S 解答 1 句型 S a 的语法树如图3 5所示 3 7对于文法G S S L aS aL L S S 解答 2 由语法树可知 短语 S a a S a S a 直接短语 a S 句柄 S 素短语 a 3 9考虑文法G S S T a S aT T S S消除文法的左递归及提取公共左因子 然后对每个非终结符写出不带回溯的递归子程序 解答 消除文法G S 的左递归 S T a S aT ST T ST 提取公共左因子 S T aS S S T ST T ST 不带回溯的递归子程序如下 voidmatch tokent if lookahead t lookahead nexttoken elseerror voidS if lookahead a match a S elseif lookahead match T if lookahead match elseerror elseerror G S S T aS S S T ST T ST voidS if lookahead match S voidT if lookahead match S T voidT S T 3 10已知文法G A A aABl aB Bb d 1 试给出与G A 等价的LL 1 文法G A 2 构造G A 的LL 1 分析表 3 给出输入串aadl 的分析过程 解答 1 文法G A 存在左递归和回溯 故其不是LL 1 文法 要将G A 改造为LL 1 文法 首先要消除文法的左递归 将产生式B Bb d改造为B dB B bB 其次 应通过提取公共左因子的方法来消除G A 中的回溯 即将产生式A aABl a改造为A aA A ABl 最后得到改造后的文法为G A A aA A ABl B dB B bB 对A ABl 来说 FIRST ABl FOLLOW A a d 对B bB 来说 FIRST bB FOLLOW B b l 所以文法G A 为所求等价的LL 1 文法 LL 1 文法的判定条件 对A 若 则有FIRST FOLLOW A G A A aA A ABl B dB B bB 2 构造G A 的LL 1 分析表 构造FIRST集FIRST A a FIRST A a FIRST B d FIRST B b 构造FOLLOW集对文法开始符号A 有FOLLOW A 由A ABl得FIRST B FOLLOW A 即FOLLOW A d 由A ABl得FIRST l FOLLOW B 即FOLLOW B l 由A aA 得FOLLOW A FOLLOW A 即FOLLOW A d 由B dB 得FOLLOW B FOLLOW B 即FOLLOW B l 2 构造预测分析表的方法如下 对文法G A 的每个产生式A 执行 步 对每个终结符a FIRST A 把A 加入到M A a 中 其中 为含有首字符a的候选式或为唯一的候选式 若 FIRST A 则对任何属于FOLLOW A 的终结符b 将A 加入到M A b 中 把所有无定义的M A a 标记上 出错 由此得到G A 的预测分析表 见表3 1 得到文法G A 的预测分析表 G A A aA A ABl B dB B bB FIRST A a FRIST A a FIRST B d FRIST B b FOLLOW A d FOLLOW A d FOLLOW B l FOLLOW B l A aA A ABl A A B dB B bB B 3 给出输入串aadl 的分析过程 3 19试构造下述文法的SLR 1 分析表 G S S bASB bAA dSa eB cAa c 解答 首先将文法G S 拓广为G S G S 0 S S 1 S bASB 2 S bA 3 A dSa 4 A e 5 B cAa 6 B c 构造文法G S 的LR 0 项目集规范族如下 I0 S SS bASBS bAI1 S S I2 S b ASBS b AA dSaA e I3 S bA SBS bA S bASBS bAI4 A d SaS bASBS bA I5 A e I6 S bAS BB cAaB cI7 A dS aI8 S bASB 文法G S 的DFA如图3 11所示 I9 B c AaB c A dSaA eI10 A dSa I11 B cA aI12 B cAa 图3 11文法G S 的DFA 注意 在比较熟练的情况下 也可以不构造LR 0 项目集规范族而直接画出文法G S 的DFA 由于I3和I9既含有移进项目又含有归约项目 故文法G S 不是LR 0 文法 构造文法G S 的FOLLOW集如下 1 FOLLOW S 2 由S AS 得FIRST S FOLLOW A 即FOLLOW A b 由S SB得FIRST B FOLLOW S 即FOLLOW S c 由A Sa得FIRST a FOLLOW S 即FOLLOW S a c 3 由S S得FOLLOW S FOLLOW S 即FOLLOW S a c 由S B得FOLLOW S FOLLOW B 即FOLLOW B a c 由S A得FOLLOW S FOLLOW A 即FOLLOW A a b c 对I3有 b FOLLOW S b a c 对I9有 d e FOLLOW B d e a c 故文法G S 是SLR 1 文法 最后得到SLR 1 分析表见表3 9 G S 0 S S 1 S Basb 2 S bA 3 A dSa 4 A e 5 B cAa 6 B c FOLLOW S a c FOLLOW A a b c FOLLOW B a c s2 1 acc 3 s4 s5 6 s2 r2 r2 r2 s2 7 r4 r4 r