[第四章语法分析.5..ppt

第四章 语法分析(5) 4.8~4.9 LR Parsing LR(0)项目 在产生式右部加上‘·’，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。 A ? X·YZ 由X推导出的子串已经分析过， X出现在栈中，下一步希望看到YZ推导出的子串。 闭包运算closure 若项目集I中有项目A ? ?·B? ，且有产生式B ? ? ，则下一步希望看到由B?推导出的子串，那么等同于希望看到?? ，因此将项目B ? ·? 加入 closure(I) 有效项目 有效项目：如果存在规范推导 S ?*?Aw ? ??1?2w，则说项目A??1 · ?2对活前缀 ??1 是有效的。 代表某一时刻，栈中的内容是??1 （活前缀）。 一个活前缀?的有效项目集就是从DFA的初态出发，沿着标记为?的路径到达的那个项目集（状态） 。 项目决定了动作：移进或归约 希望同一个项目集中的若干个项目没有动作冲突 SLR(1)分析方法 若有[A?? · ]在Ii中，那么对FOLLOW(A)中的所有a， action[i, a]为rj 更好的避免冲突的方法 LR(1)分析法 需要更多的信息，指出[A?? · ]句柄?之后紧跟哪个终结符才能归约 S ?*??Aaw ? ??aw， 让项目带上有哪些信誉好的足球投注网站符，LR(1)项目由LR(0)项目和一个lookahead符号组成： [A?? · , a] 有哪些信誉好的足球投注网站符a的集合总是Follow(A)的子集。 活前缀的有效LR(1)项目 LR(1)项目[A??·?, a]对活前缀?有效，如果存在着推导 S ?*rm ?Aw ?rm ???w，其中： ? = ??； a是w的第一个符号，或者w为?且a是$。 构造有效的LR(1)项目集 项目[A?? ·B?, a]对活前缀?有效，必定存在S ?*rm ?Aax ?rm ??B?ax，其中? = ??。 假设?ax能推出by，那么， [B? ·?, b]对?有效，b是从? 能推出的开始符号，或当? 可空时，b就是a。b?FIRST(?a)。 LL分析方法和LR分析方法的比较 A ? ?，LL(1) 向前看下一个输入根据FIRST(?)确定使用哪条产生式推导；而LR(1)是在识别出整个?后，再往前看1个符号，然后确定使用哪条产生式归约。 LL分析方法和LR分析方法的比较 非LR结构 例：L={wwR ? w?{a, b}*} S ? aSa ?bSb ? ? LL分析方法和LR分析方法的比较 LL(k)文法都是LR(k)文法。 LR文法比LL文法描述的语言更多。 LR分析方法和LL分析方法的比较 CFG classification 4·8 二义文法的应用 任何二义性的文法都不是LR文法。 二义文法的特点：简洁、自然 例如，表达式文法 二义文法：E ? E + E | E * E | (E) | id 非二义的文法： E ? E + T | T T ? T * F | F F ? (E) | id 语法分析的效率高（基于消除二义后得到的分析表） 4.8.1 使用文法以外信息解决分析动作冲突 优先级和结合规则 例： 规定： *优先级高于+，两者都是左结合 E ? E + E | E * E | (E) | id 拓广文法的LR(0)项目集 SLR分析表（存在冲突） 使用文法以外信息来解决分析动作冲突 4.8.2 悬空else的二义性 S? ? S S ? iSeS | iS | a 图4-49 LR分析表 4.8.4 LR分析的错误恢复 LR分析器在什么情况下发现错误 访问动作表时若遇到出错条目，就检测到一个错误 访问转移表时它决不会遇到出错条目 SLR和LALR分析可能会在报错之前执行几步归约，但决不会把不正确的后继移进栈规范的LR分析器甚至在报告错误之前决不做任何无效归约 紧急方式错误恢复 退栈，直至出现状态s, 它有预先确定的A的转移； 抛弃若干个输入符号，直至找到a, 它是A的合法后继； 再把A和状态goto[s, A]压进栈，恢复正常分析。 例4.50 E ? E + E | E * E | (E) | id 输入id+)的分析和出错恢复 4.9 语法分析器的生成器 Yacc：yet another compiler-compiler 基于LALR(1)的语法分析程序的生成器 Yacc 的 GNU 版叫做 Bison。 Yacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF, Backus Naur Form)来书写。 4·9·1 分析器的生成器Yacc 按照惯例，Yacc 文件有 ·y 后缀。 调用 Yacc 编译器： yacc options filename ending w