第四章_语法分析(5).ppt

2020 2 19 1 第四章语法分析 5 4 8 4 9 2020 2 19 编译原理 2 LRParsing 2020 2 19 编译原理 3 LR 0 项目 在产生式右部加上 表示分析过程中的状态 指示产生式右部符号已经被识别了多少 A X YZ由X推导出的子串已经分析过 X出现在栈中 下一步希望看到YZ推导出的子串 2020 2 19 编译原理 4 闭包运算closure 若项目集I中有项目A B 且有产生式B 则下一步希望看到由B 推导出的子串 那么等同于希望看到 因此将项目B 加入closure I 2020 2 19 编译原理 5 有效项目 有效项目 如果存在规范推导S Aw 1 2w 则说项目A 1 2对活前缀 1是有效的 代表某一时刻 栈中的内容是 1 活前缀 一个活前缀 的有效项目集就是从DFA的初态出发 沿着标记为 的路径到达的那个项目集 状态 2020 2 19 编译原理 6 项目决定了动作 移进或归约希望同一个项目集中的若干个项目没有动作冲突SLR 1 分析方法若有 A 在Ii中 那么对FOLLOW A 中的所有a action i a 为rj更好的避免冲突的方法 2020 2 19 编译原理 7 LR 1 分析法 需要更多的信息 指出 A 句柄 之后紧跟哪个终结符才能归约S Aaw aw 让项目带上搜索符 LR 1 项目由LR 0 项目和一个lookahead符号组成 A a 搜索符a的集合总是Follow A 的子集 2020 2 19 编译原理 8 活前缀的有效LR 1 项目 LR 1 项目 A a 对活前缀 有效 如果存在着推导S rm Aw rm w 其中 a是w的第一个符号 或者w为 且a是 2020 2 19 编译原理 9 构造有效的LR 1 项目集 项目 A B a 对活前缀 有效 必定存在S rm Aax rm B ax 其中 假设 ax能推出by 那么 B b 对 有效 b是从 能推出的开始符号 或当 可空时 b就是a b FIRST a 2020 2 19 编译原理 10 w A w A LL分析方法和LR分析方法的比较 A LL 1 向前看下一个输入根据FIRST 确定使用哪条产生式推导 而LR 1 是在识别出整个 后 再往前看1个符号 然后确定使用哪条产生式归约 S S 2020 2 19 编译原理 11 在下面的推导中 最后一步用的是A LL 1 决定用该产生式的位置是First LR 1 决定用该产生式的位置 LL分析方法和LR分析方法的比较 2020 2 19 编译原理 12 非LR结构 例 L wwR w a b S aSa bSb 2020 2 19 编译原理 13 LL分析方法和LR分析方法的比较 LL k 文法都是LR k 文法 LR文法比LL文法描述的语言更多 2020 2 19 编译原理 14 LR分析方法和LL分析方法的比较 2020 2 19 编译原理 15 LR分析方法和LL分析方法的比较 2020 2 19 编译原理 16 LR分析方法和LL分析方法的比较 2020 2 19 编译原理 17 2020 2 19 编译原理 18 CFGclassification LL 1 LR 0 SLR LALR 1 LR 1 2020 2 19 编译原理 19 4 8二义文法的应用 任何二义性的文法都不是LR文法 二义文法的特点 简洁 自然例如 表达式文法二义文法 E E E E E E id非二义的文法 E E T TT T F FF E id语法分析的效率高 基于消除二义后得到的分析表 2020 2 19 编译原理 20 4 8 1使用文法以外信息解决分析动作冲突 优先级和结合规则例 规定 优先级高于 两者都是左结合E E E E E E id 2020 2 19 编译原理 21 拓广文法的LR 0 项目集 I0 E EE E EE E EE E E idI1 E E E E EE E E I2 E E E E EE E EE E E idI3 E id I4 E E EE E EE E EE E E id I5 E E EE E EE E EE E E idI6 E E E E EE E E I7 E E E E E EE E EI8 E E E E E EE E EI9 E E FOLLOW E 移进 归约冲突 2020 2 19 编译原理 22 2020 2 19 编译原理 23 SLR分析表 存在冲突 2020 2 19 编译原理 24 使用文法以外信息来解决分析动作冲突 考虑id id id和id id id形成格局栈输入0E1 4E7 id 面临 归约面临 移进面临 和 归约 I7 E E E E E EE E E 2020 2 19 编译原理 25 4 8 2悬空else的二义性 S SS iSeS iS a 2020 2 19 编译原理 26 I0 S SS iSeSS iSS aI1 S S I2 S i SeSS i SS iSeSS iSS a I3 S a I4 S iS eSS iS I5 S iSe SS iSeSS iSS aI6 S iSeS FOLLOW S i e 移进 归约冲突根据最近匹配原则选择移进动作 2020 2 19 编译原理 27 2020 2 19 编译原理 28 I0 S SS iSeSS iSS aI1 S S I2 S i SeSS i SS iSeSS iSS a I3 S a I4 S iS eSS iS I5 S iSe SS iSeSS iSS aI6 S iSeS FOLLOW S i e 移进 归约冲突根据最近匹配原则选择移进动作 2020 2 19 编译原理 29 根据最近匹配原则选择移进动作 图4 49LR分析表 2020 2 19 编译原理 30 4 8 4LR分析的错误恢复 LR分析器在什么情况下发现错误访问动作表时若遇到出错条目 就检测到一个错误访问转移表时它决不会遇到出错条目SLR和LALR分析可能会在报错之前执行几步归约 但决不会把不正确的后继移进栈规范的LR分析器甚至在报告错误之前决不做任何无效归约 2020 2 19 编译原理 31 紧急方式错误恢复 退栈 直至出现状态s 它有预先确定的A的转移 抛弃若干个输入符号 直至找到a 它是A的合法后继 再把A和状态goto s A 压进栈 恢复正常分析 2020 2 19 编译原理 32 栈 a A 发现错误 s C A A b C A A A b b 2020 2 19 编译原理 33 2020 2 19 编译原理 34 2020 2 19 编译原理 35 例4 50E E E E E E id e1 id 状态 3进栈 缺少运算对象e2 从输入删除 右括号不匹配e3 状态 4进栈 缺少操作符e4 状态 9进栈 缺少右括号 2020 2 19 编译原理 36 输入id 的分析和出错恢复 分析栈输入串动作和错误信息0id 移进0id3 归约 E id0E1 移进0E1 4 e2右括号不匹配 从输入删除 0E1 4 e1缺少运算对象 假想的id进栈0E1 4id3 归约 E id0E1 4E7 归约 E E E0E1 accetp 2020 2 19 编译原理 37 4 9语法分析器的生成器 Yacc yetanothercompiler compiler基于LALR 1 的语法分析程序的生成器Yacc的GNU版叫做Bison Yacc是一种工具 根据编程语言的语法生成针对该语言的Yacc语法分析器 它用巴科斯范式 BNF BackusNaurForm 来书写 2020 2 19 编译原理 38 4 9 1分析器的生成器Yacc 按照惯例 Yacc文件有 y后缀 调用Yacc编译器 yacc 2020 2 19 编译原理 39 语法规则 y文件 2020 2 19 编译原理 40 用Yacc创建语法分析器包括四个步骤 通过在语法文件上运行Yacc生成一个解析器 说明语法 编写一个 y的语法文件 同时说明C在这里要进行的动作 写一个词法分析器来处理输入并将标记传递给解析器 这可以使用Lex来完成 编写一个函数 通过调用yyparse 来开始解析 编写错误处理例程 如yyerror 编译Yacc生成的代码以及其他相关的源文件 将目标文件链接到适当的可执行解析器库 2020 2 19 编译原理 41 Yacc源程序的组成部分 C声明 文法规则及翻译规则 用C语言编写的支持例程 2020 2 19 编译原理 42 例4 50台式计算器 E E T TT T F FF E digit读入一个算术表达式 计算它的值并输出 2020 2 19 编译原理 43 include tokenDIGIT line expr n printf d n 1 expr expr term 1 3 term 所声明的token可用于第二 三部分 表示左部非终结符的属性值 i表示右部第i个文法符号关联的属性值 默认动作是 1 2020 2 19 编译原理 44 term term factor 1 3 factor factor expr 2 DIGIT yylex intc c getchar if isdigit c yylval c 0 returnDIGIT returnc 辅助的简单词法分析程序 2020 2 19 编译原理 45 4 9 2用Yacc处理二义文法 采用简单的二义文法 E E E E E E E E E E E number输入一个表达式并回车 显示计算结果 也可以输入一个空白行 2020 2 19 编译原理 46 声明部分 include include defineYYSTYPEdouble 将栈定义为double类型 tokenNUMBER left left rightUMINUS 2020 2 19 编译原理 47 翻译规则 lines linesexpr n printf g n 2 lines n expr expr expr 1 3 expr expr 1 3 expr expr 1 3 expr expr 1 3 expr 2 expr precUMINUS 2 NUMBER 2020 2 19 编译原理 48 支持例程 yylex intc while c getchar if c isdigit c ungetc c stdin scanf lf 2020 2 19 编译原理 49 Yacc文件格式中的几个问题 TOKEN的定义 tokenNUM tokenIDENT语法规则与语义动作 2020 2 19 编译原理 50 Yacc文件格式中的几个问题 为算符指定优先级与结合率 left left leftNEG negation unaryminus right exponentiation 二义性及冲突的解决归约 归约冲突 选择Yacc说明中先出现的产生式移进 归约冲突 移近优先出错处理 2020 2 19 编译原理 51 将Lex与Yacc结合起来 一个程序通常在每次返回一个标记时都要调用yylex 函数 只有在文件结束或者出现错误标记时才会终止 一个由Yacc生成的解析器调用yylex 函数来获得标记 yylex 可以由Lex来生成或完全由自己来编写 对于由Lex生成的lexer来说 要和Yacc结合使用 每当Lex中匹配一个模式时都必须返回一个标记 因此Lex中匹配模式时的动作一般格式为 pattern dosomething returnTOKEN NAME 2020 2 19 编译原理 52 于是Yacc就会获得返回的标记 当Yacc编译一个带有 d标记的 y文件时 会生成一个头文件 它对每个标记都有 define的定义 如果Lex和Yacc一起使用的话 头文件必须在相应的Lex文件 lex中的C声明段中包括 include lex yy c 2020 2 19 编译原理 53 Yacc的错误恢复 编译器设计者的工作决定哪些 主要的 非终符将有错误恢复与它们相关联 加入A error 的错误产生式 其中