第五章语法分析——自底向上.ppt

定义5.16 按照LALR(1)的项目集规范族构造的文法G的LALR (1)分析表，如果每个入口不含多重定义，则称它为G的LALR(1)分析表。 具有LALR(1)分析表的文法G称为LALR(1)文法。 使用LALR(1) 分析表的语法分析器称作LALR(1)分析器。 CompilerPrinciples * 判断G是LR四类文法的哪一类 CompilerPrinciples * 例5.18 设有下列文法 S→Aa| bAc| Bc|bBa A→d B→d 判断该文法是哪类LR文法？ CompilerPrinciples * LR(0)?SLR(1)?LR(1)?LALR(1)? CompilerPrinciples * I0 S→?S S→?Aa| ?bAc| ?Bc| ?bBa A→?d B→?d A→d ? B→d ? I1 d 归约—归约 冲突 G为非LR(0) 用SLR(1)方法 FOLLOW(A) = {a,c} FOLLOW(B) = {a,c}∩≠? G为非SLR(1) 构造LR(1)的C S →?S, # S→?Aa| ?bAc| ?Bc| ?bBa, # A→?d , c B→?d , a CompilerPrinciples * A→d ?，a B→d ?,c d S→b?Ac | b ?Ba,# A→?d ,c B→?d ,a b G为LR(1) A→d ?，c B→d ?,a d 同心项目集 S →?S, # S→?Aa| ?bAc| ?Bc| ?bBa, # A→?d , c B→?d , a CompilerPrinciples * A→d ?，a\c B→d ?,a\c d S→b?Ac | b ?Ba,# A→?d ,cB→?d ,a d b 归约—归约冲突。非LALR(1) G为LR(1) 5.8 LR分析对二义文法的应用 结论 任何二义文法都不是LR文法，因而也决不是SLR或LALR文法。 例5.17 设有文法G(E) : E→E+E ① E→E*E ② E→(E) ③ E→i ④ 等价文法 G2: E→E+T∣T T→T*F∣F F→(E)∣i CompilerPrinciples * CompilerPrinciples * I0:E→?E E→?E+E E→?E*E E→?(E) E→?i I1:E→E? E→E?+E E→E?*E I4:E→E+?E E→?E+E E→?E*E E→?(E) E→?i I3:E→i? I2:E→(?E) E→?E+E E→?E*E E→?(E) E→?i I7:E→E+E? E→E?+E E→E?*E I5:E→E*?E E→?E+E E→?E*E E→?(E) E→?i I8:E→E*E? E→E?+E E→E?*E I6:E→(E?) E→E?+E E→E?*E I9:E→(E)? E + i ( ( i E * i E + E * i ( * ) + * + 5.9 LR分析的错误处理与恢复 错误存在的必然性 问题复杂性、程序员素质、输入错、系统环境生疏… 编译中的错误种类 词法错误； 语法错误； 语义错误(静态、动态) ； 违反环境限制的错误； CompilerPrinciples * 5.9 LR分析的错误处理与恢复 错误处理基本目标 1. 清晰准确地报告错误（错误的定性和定位）； 2. 迅速从每个错误中恢复过来，以便诊断后面的错误； 3. 不使正确程序的处理效率降低。 CompilerPrinciples * 5.9 LR分析的错误处理与恢复 错误处理与恢复策略 1. 紧急恢复方式 编译器每次发现错误时，抛弃一个输入符号，直到输入符号属于某个指定的同步符号集合为止。 CompilerPrinciples * 例如，界限符：；、}、end … 5.9 LR分析的错误处理与恢复 2. 短语级恢复 发现错误时，对剩余符号串作局部校正。 即使用可以是编译器继续工作的输入串代替剩余输入的前缀。 CompilerPrinciples * 5.9 LR分析的错误处理与恢复 3. 出错产生式 扩充语言的文法，增加产生错误结构的产生式。分析中可以直接识别处理错误。 4. 全局纠正 获取全局最小代价纠正。 CompilerPrinciples * 5.9 LR分析的错误处理与恢复