5-第五章—自下而上语法分析-3-4节.ppt

该文法的LR(0)项目集规范族为： I1、I2和I9都含有“移进－归约”冲突。 FOLLOW(E)＝ {#, ), +}， 作业： P133 第 3 题 说明：为简单起见，不加#号 LR分析器 = 总控程序（对所有的LR分析器，相同） + 分析表（ACTION表 + GOTO表） + 分析栈 （状态栈 + 符号栈） 输入串：a+b…# 输出 # S0 … … x1 S1 符 号 栈 状 态 栈 xm Sm 总控程序 ACTION 分析表 GOTO §5.4 LR分析法介绍 不同文法、不同LR分析器，分析表不同 ⑴ 动作部分ACTION —— 二维数组 ACTION[S,y]?当状态为S，向前看符号串y时，应该 采取的动作。( y的长度 = 1 或 k ) si：将状态 i 以及当前符号分别移入状态栈、符号栈； rj：按照第 j 个产生式，对栈顶的符号串进行归约； Acc：接受输入符号串，识别出是一个句子； 报错：输入符号串不是句子； ⑵ 状态转换部分GOTO —— 二维数组 GOTO[S,P] ? 当前状态S,面对非终结符号P时,转换 到的下一个状态。 LR分析表 书 P101, LR分析表 GOTO表 ACTION表 r3 r3 r3 r3 10 s4 s4 s4 s4 ( r5 r1 s11 r6 r4 r2 ) r5 r5 r5 11 r1 r1 9 s6 8 10 s5 7 3 9 s5 6 r6 r6 r6 5 3 2 8 s5 4 r4 r4 r4 3 r2 s7 r2 2 acc s6 1 3 2 1 s5 0 F T E # * + i 状态 G[E]： 1.E→E+T 2.E→T 3.T→T*F 4.T→F 5.F→(E) 6.F→ i Si:移入 i=状态栈 a=符号栈 输入前移 0 =状态栈，# =符号栈 LR分析器 标准分析算法 开始 S＝栈顶状态号；a ＝ 输入符号 执行ACTION[S,a] Accept 分析 成功 空白 出错 rj : 按第j条产生式归约 L=候选式长度; P=左部符号 状态栈弹出L个状态； 符号栈弹出L个符号； Go[新栈顶,P]=状态栈； P=符号栈 结束 Acc # #E 01 3 F→i r6 # #E+F 0163 9 T→F r4 # #E+T 0169 1 E→E+T r1 # #E 01 G[S,P] 规则 A[S,a] 输入 符号栈 状态栈 s5 # #E+i 0165 s6 i# #E+ 016 1 E→T r2 +i# #E 01 2 T→T*F r3 +i# #T 02 10 F→i r6 +i# #T*F 02710 s5 +i# #T*i 0275 s7 i+i# #T* 027 2 T→F r4 *i+i# #T 02 3 F→i r6 *i+i# #F 03 s5 *i+i# #i 05 预备 i*i+i# # 0 G[E]： 1.E→E+T 2.E→T 3.T→T*F 4.T→F 5.F→(E) 6.F→ i GOTO表 ACTION表 r3 r3 r3 r3 10 s4 s4 s4 s4 ( r5 r1 s11 r6 r4 r2 ) r5 r5 r5 11 r1 r1 9 s6 8 10 s5 7 3 9 s5 6 r6 r6 r6 5 3 2 8 s5 4 r4 r4 r4 3 r2 s7 r2 2 acc s6 1 3 2 1 s5 0 F T E # * + i LR分析表 例：i*i+i 最右推导：E=E+T=E+F=E+i=T+i=T*F+i=T*i+i=F*i+i=i*i+i LR分析法 — 优点 LR分析法 — 缺点 1)、手工实现工作量大 2)、分析表占用空间大 1)、适用于大多数上下文无关文法 2)、分析效率高 3)、报错及时 4)、可以自动生成，如：YACC 分析表种类的不同，对应不同的LR分析器。 LALR分析器 例：YACC 适用的文法、实现上难易 程度介于上述两者之间。 LALR (超前LR表) 适用文法类最大； 分析表体积太大，目前实 用价值小。 LR (规范LR表) SLR分析器 构造简单,最易实现； 具有较高的实用价值。 SLR (简单LR表) 语法分析器 特点 分析表 LR分析表种类 ⑴ 字的前缀：字的任意首部。 如：abc的前缀有：?，a，ab，abc。 ⑵ 可归前缀：是指规范句型的一个前缀，这种前缀不 含句柄之后的任何符号。 若： αδβ是句型，δ为句柄，则αδ为可归前缀。 ⑶ 活前缀