北大计算机系课件 词法分析2.pdf

北京大学信息科学技术学院 2014年春季学期 《编译技术》 第4 章 语法分析（2） Syntax Analysis 【对应教材2.4, 4.3, 4.4 】 内容提要  语法分析简介  上下文无关文法  文法的设计方法  自顶向下的语法分析  自底向上的语法分析  简单LR分析：LR(0), SLR  更强大的LR分析：LR(1), LALR  二义性文法的使用  语法分析器生成工具YACC 2 2014年春季学期 《编译技术》课程 北京大学信息科学技术学院 文法的设计方法  文法能够描述程序设计语言的大部分语法  但不是全部，比如：标识符的先声明后使用无 法用上下文无关文法描述。  因此：语法分析器接受的语言是程序设计语言 的超集。必须通过语义分析来剔除一些符合文 法、但不合法的程序。  常见的文法变换方法  消除二义性  消除左递归  提取左公因子 3 2014年春季学期 《编译技术》课程 北京大学信息科学技术学院 消除文法的二义性（1）  一些二义性文法可以被改成等价的无二义性文法  例子(dangling-else) ： stmt  if expr then stmt | if expr then stmt else stmt |other  if E then if E then S else S 有两棵语法树 1 2 1 2 4 2014年春季学期 《编译技术》课程 北京大学信息科学技术学院 消除文法的二义性（2）  为保证“else和最近未匹配的then 匹配”，我们 要求在then分支的语句必须是匹配好的。  引入matched_stmt表示匹配好的语句，有如下 文法： stmt matched_stmt | open_stmt matched_stmt if expr then matched_stmt else matched_stmt | other open_stmt if expr then stmt | if expr then matched_stmt else open_stmt  二义性的消除方法没有规律可循。 5 2014年春季学期 《编译技术》课程 北京大学信息科学技术学院 例：消除文法的二义性  文法G的产生式如下： S →aSb | bSa | SS | ab | ba  L(G) = ?  G是二义性的，比如ababab有两个不同的最 左推导。  S=SS = abS = abSS = ababS = ababab  S=SS = SSS = abSS = ababS = ababab 