第三章语法分析 复习习题 优质课件

1、上下文无关文法 自上而下 自下而上 LL(1) 文法 2个函数 递归下降 预测分析 非递归的 预测分析 最左推导 最右推导 ！ ！ LR文法 输 入 LR分析程序 输 出 栈 LR分析器的模型 action goto sm Xm sm-1 Xm-1 s0 a1 ai an $ 移进-归约分析 归约 移进-归约冲突 规约-归约冲 突 句柄 活前缀 右句型的前缀， 该前缀不超过最 右句柄的右端 1。句柄与某个产生式的右部 符号串相同 2。句柄是句型的一个子串 3。把句柄归约成非终结符代 表了最右推导逆过程的 一步 简单的LR方法（SLR ） 规范的LR方法 向前看的LR方法(LALR ） 温故知新

2、 2 语法分析部分回顾 自上而下分析的知识点 ? LL(1)文法的判定 FIRST、FOLLOW集的计算（重点） LL(1)文法判定方法 ? LL(1)分析的实现方法 递归函数实现 非递归的预测分析实现 ?先求先求FIRSTFIRST、FOLLOW集集 ?画预测分析表 3 语法分析部分回顾 应用LL(1)分析方法的步骤 ? 判定文法是否是LL(1)文法 如果不是，则改写文法 ? 消除左递归 ? 提取左因子 如果改写后的文法是LL(1)的，那么进行 LL(1)分析 ? 构造LL(1)分析算法 可以采用递归函数实现，也可以采用非递归的栈 式分析方法实现 4 文法G: S-aSb | P P-bPc

3、 | bQc Q-Qa | a （1）它是chomsky 哪一型文法？ （2）它生成的语言是什么？ （3）给出提取左因子、消除左递归之后的文法 （4）求出每个非终结符的 First 集和Follow 集 （5）构建LL（1）预测分析表 （6）文法G是否是LL（1）文法 （7）利用非递归预测分析程序，验证 abacb 是否是 文法G描述的语言的句子 5 文法G: S-aSb | P P-bPc | bQc Q-Qa | a （1）它是chomsky 哪一型文法？ 答：它是2型文法，即上下文无关文法。 （2）它生成的语言是什么？ 答：a ibjakcjbi | i=0; j,k=1 6 文法G:

4、S-aSb | P P-bPc | bQc Q-Qa | a （3）给出提取左因子、消除左递归之后的文法 答： S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | ? 7 S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | ? First(S)=a,b First(P)=b First(P )=a,b First(Q)=a First(Q )=a, ? Follow(S)=$,b Follow(P)=$,b,c Follow(P )=$,b,c Follow(Q)=c Follow(Q )=c （4）求出每个非终结符的First 集和Follow 集

5、 8 （5）构建LL（1）预测分析表 输入符号 非终结符 a b c $ S S-aSb S-P P P-bP P P-Qc P-Pc Q Q-aQ Q Q-aQ Q-? 9 （6）文法G是否是LL（1）文法 答：构建出的LL（1）分析表不含有多重定 义的条目，因此文法G是LL（1）文法。 10 （7）利用非递归预测分析程序，验证 abacb 是 否是文法G描述的语言的句子 栈 输入 输出 $S abacb$ $bSa abacb$ S-aSb $bS bacb$ $bP bacb$ S-P $bPb bacb$ P-bP $bP acb$ 11 栈 输入 输出 $bcQ acb$ P-Qc

6、$bcQa acb$ Q-aQ $bcQ cb$ $bc cb$ Q- ? $b b$ $ $ 接上表接上表 12 语法分析部分回顾 例2 文法GE: E- T T- TE | F F- a | aF (1) 判断这个文法是不是LL(1)的？ (2) 消除左递归、提取左因子之后的文法G是否 是LL(1)的？ 13 例1 解答： 提取左因子，消除左递归后 文法变为GE: E- T T-F T T-ET | ? F-aF F-F | ? GS: E- T T- TE | F F- a | aF 语法分析部分回顾 14 FIRST(E) = FIRST(T) = a FIRST(T)= , ? FI

7、RST(F) = a FIRST(F)= a, ? FOLLOW(E)=,$ FOLLOW(T)=,$ FOLLOW(T)=,$ FOLLOW(F)= FOLLOW(F)= GE: E- T T-F T T-ET | ? F-aF F-F | ? 不是LL(1)文法！ 通过提取左因子和 消除左递归的方法， 并不一定能够把文 法改写为一个 LL(1) 文法 语法分析部分回顾 15 左递归的消除 ? GS: S-Qc|c Q-Sa|a 这是一类间接左递归 S-Sac|ac|c Q-Sa|a 语法分析部分回顾 16 左递归的消除 ? GS: S-Qc|c Q-Sa|a 这是一类间接左递归 S-acS

8、| cS S-acS| ? Q-Sa|a 语法分析部分回顾 S-Sac|ac|c Q-Sa|a 17 语法分析部分回顾 LR分析部分的知识点 ? 活前缀 ? 识别活前缀的DFA ? 分析表 ? 分析算法 18 语法分析内容总结 自下而上分析部分知识点 ? SLR的DFA的构造及分析表的构成 初始项目集合的产生（拓广文法） 能够识别同一符号的项目都转移到同一集合中 求闭包过程中每一个“ .” 后面的非终结符都要重 新考虑是否已经在状态中列出 对产生式A- ? 归约，“ ri” 写在FOLLOW(A)集合 中元素对应的位置。 19 语法分析内容总结 自下而上分析部分知识点 ? LR,LALR的构造

9、方法（在SLR的基础上加上搜 索符） 搜索符的求法，根据造成目前项目出现的那个父 项目来求。 求闭包的过程中可能出现要添加的项目已经存在求闭包的过程中可能出现要添加的项目已经存在 ，但是搜索符不同的情况，相当于其父项目已经 改变，此时需要再求一遍搜索符。 20 语法分析内容总结 自下而上分析部分知识点 ? SLR,LR,LALR的区别及判别方法 通过构造DFA，看其中的状态是否有冲突（“移 进归约” 或 “归约归约”）若有冲突则不 属于该文法类型。 通过构造分析表，看其中某项是否有冲突。 21 文法类的层次图 22 语法分析部分回顾 例2 文法GS: S-AaS | bAe | BeS | b

10、Ba A-d B-d 判断这个文法是SLR(1)的，还是LR(1)的，抑 或是LALR(1)的 23 例2 解答: I2=goto(I 0,d) I 0 : S?S S?AaS S ? bAe S?BeS S? bBa A? d B? d I 2 : A? ? d B? ? d d S-AaS | bAe | BeS | bBa A-d B-d e属于FOLLOW(A),同 时也属于 FOLLOW(B), I2里存 在归约-归约冲突 语法分析部分回顾 24 LR(1)分析练习题目 基于LR(1)项目来构造识别G?活前缀的DFA，并基于DFA构建 分析表. S ? V = E S ? E V ?

11、 * E V ? id E ? V 25 LR(1)分析练习解答过程 ? 答： ? Step 1. 对原文法进行拓广 (添加产生式S-S) S ? V = E S ? E V ? * E V ? id E ? V S ? S S ? V = E S ? E V ? * * E V ? id E ? V 26 id S? S S ? ? V=E S ? ? E V ? ? *E V ? ? id E ? ? V V ? id ? S ? V ?=E E ? V ? S? S ? I0 I1 I2 I5 S ? E ? I3 V ? *? E E ? ? V V ? ? id V ? ? * E

12、I4 S V * id E S ? V = ? E E ? ? V V ? ? *E V ? ? id I6 = E S ? V=E ? E ? V ? V V I8 id I3 * * V ? *E ? E I7 I9 识别产生式文法活前缀的DFA 27 ? Step 2: 构建识别（拓广）文法活前缀的DFA I 0: S-S, $ S- V=E, $ S- E, $ V- *E, =/$ V- id, =/$ E- V, $ I 1: S-S , $ S I 2: S-V =E, $ E-V , $ V E I 3: S-E , $ * I 4: V-* E, =/$ E- V, =/$

13、V- *E, =/$ V- id, =/$ id I 5: V-id , =/$ = I 6: S-V= E, $ E- V, $ V- *E, $ V- id, $ E I 8: S-*E , =/$ V I 9: E-V , =/$ * id 指向I 5 E I 10: S-V=E , $ * I 12 : V-* E, $ E- V, $ V- *E, $ V- id, $ I 7: E-V , $ V 指向I 7 id I 11: V-id , $ E I 13: S-*E , $ V 指向I 7 * id 指向I 11 LR(1)分析练习解答过程 28 ? 构建分析表 首先，为表达式编号 然后，计算action表和goto表 0 S ? S 1 S ? V = E 2 S ? E 3 V ? * * E 4 V ? id 5 E ? V LR(1)分析练习解答过程