第四章_语法分析(5)精选文档.ppt

第四章第四章_语法分析语法分析(5)本讲稿第一页，共五十五页2022/10/1912022/10/19编译原理编译原理2LR Parsing本讲稿第二页，共五十五页2022/10/19编译原理编译原理3LR(0)项目项目q在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。A XYZq由X推导出的子串已经分析过，X出现在栈中，下一步希望看到YZ推导出的子串。本讲稿第三页，共五十五页2022/10/19编译原理编译原理4闭包运算闭包运算closureq若项目集I中有项目A B，且有产生式B ，则下一步希望看到由B推导出的子串，那么等同于希望看到，因此将项目B 加入 closure(I)本讲稿第四页，共五十五页2022/10/19编译原理编译原理5有效项目有效项目q有效项目：有效项目：如果存在规范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。代表某一时刻，栈中的内容是1（活前缀）。一个活前缀的有效项目集就是从DFA的初态出发，沿着标记为的路径到达的那个项目集（状态）。本讲稿第五页，共五十五页2022/10/19编译原理编译原理6q项目决定了动作：移进或归约q希望同一个项目集中的若干个项目没有动作冲突qSLR(1)分析方法若有A 在Ii中，那么对FOLLOW(A)中的所有a，actioni,a为rj更好的避免冲突的方法本讲稿第六页，共五十五页2022/10/19编译原理编译原理7LR(1)分析法分析法q需要更多的信息，指出A 句柄之后紧跟哪个终结符才能归约S*Aaw aw，q让项目带上搜索符，LR(1)项目由LR(0)项目和一个lookahead符号组成：A ,a搜索符a的集合总是Follow(A)的子集。本讲稿第七页，共五十五页2022/10/19编译原理编译原理8活前缀的有效活前缀的有效LR(1)项目项目qLR(1)项目A,a对活前缀有效，如果存在着推导S*rm Aw rm w，其中：1.=；2.a是w的第一个符号，或者w为且a是$。本讲稿第八页，共五十五页2022/10/19编译原理编译原理9构造有效的构造有效的LR(1)项目集项目集q项目A B,a对活前缀有效，必定存在S*rm Aax rm Bax，其中=。q假设ax能推出by，那么，B,b对有效，b是从 能推出的开始符号，或当 可空时，b就是a。bFIRST(a)。本讲稿第九页，共五十五页2022/10/19编译原理编译原理10wA wALL分析方法和分析方法和LR分析方法的比较分析方法的比较qA ，LL(1)向前看下一个输入根据FIRST()确定使用哪条产生式推导；而LR(1)是在识别出整个后，再往前看1个符号，然后确定使用哪条产生式归约。SS本讲稿第十页，共五十五页2022/10/19编译原理编译原理11在下面的推导中，最后一步用的是A LL(1)决定用该决定用该产生式的位置是产生式的位置是First()LR(1)决定用该决定用该产生式的位置产生式的位置LL分析方法和分析方法和LR分析方法的比较分析方法的比较本讲稿第十一页，共五十五页2022/10/19编译原理编译原理12非非LR结构结构q例：L=wwR wa,b*S aSa bSb 本讲稿第十二页，共五十五页2022/10/19编译原理编译原理13LL分析方法和LR分析方法的比较qLL(k)文法都是LR(k)文法。LR文法比LL文法描述的语言更多。本讲稿第十三页，共五十五页2022/10/19编译原理编译原理14LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规 范 归 约 最 左 推 导 决定使用产生式的时机 看见产生式整个右部推出的东西后才能决定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后便确定用哪个产生式进行推导 LR分析方法和LL分析方法的比较本讲稿第十四页，共五十五页2022/10/19编译原理编译原理15LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子 分析表比较 状态文法符号 分析表大 非终结符终结符分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 LR分析方法和分析方法和LL分析方法的比较分析方法的比较本讲稿第十五页，共五十五页2022/10/19编译原理编译原理16LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 不会将出错点后的符号移入分析栈 和LR一样，不会读过出错点而不报错 LR分析方法和分析方法和LL分析方法的比较分析方法的比较本讲稿第十六页，共五十五页2022/10/19编译原理编译原理17本讲稿第十七页，共五十五页2022/10/19编译原理编译原理18CFG classificationLL(1)LR(0)SLRLALR(1)LR(1)本讲稿第十八页，共五十五页2022/10/19编译原理编译原理1948 二义文法的应用二义文法的应用q任何二义性的文法都不是LR文法。q二义文法的特点：简洁、自然例如，表达式文法二义文法：E E+E|E*E|(E)|id非二义的文法：E E+T|TT T*F|FF (E)|idq语法分析的效率高（基于消除二义后得到的分析表）本讲稿第十九页，共五十五页2022/10/19编译原理编译原理204.8.1 使用文法以外信息解决分析动作使用文法以外信息解决分析动作冲突冲突优先级和结合规则例：规定：*优先级高于+，两者都是左结合E E+E|E*E|(E)|id本讲稿第二十页，共五十五页2022/10/19编译原理编译原理21拓广文法的拓广文法的LR(0)项目集项目集I0:E E E E+E E E*E E (E)E idI1:E E E E +E E E *EI2:E (E)E E+E E E*E E (E)E idI3:E idI4:E E+E E E+E E E*E E (E)E idI5:EE*E EE+E EE*E E(E)E idI6:E(E)EE+E EE*EI7:EE+E EE+E EE*EI8:EE*E EE+E EE*EI9:E(E)FOLLOW(E)=$,+,*,)移进移进-归约冲突归约冲突本讲稿第二十一页，共五十五页2022/10/19编译原理编译原理22本讲稿第二十二页，共五十五页2022/10/19编译原理编译原理23SLR分析表（存在冲突）分析表（存在冲突）本讲稿第二十三页，共五十五页2022/10/19编译原理编译原理24使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突考虑考虑id+id+id 和和id+id*id 形成格局形成格局 栈栈输入输入0E1+4E7*id$面临+，归约面临*，移进面临)和$，归约I7:EE+E EE+E EE*E本讲稿第二十四页，共五十五页2022/10/19编译原理编译原理254.8.2 悬空悬空else的二义性的二义性S SS iSeS|iS|a本讲稿第二十五页，共五十五页2022/10/19编译原理编译原理26I0:S S S iSeS S iS S aI1:S S I2:S i SeS S i S S iSeS S iS S aI3:S a I4:S iS eS S iS I5:S iSe S S iSeS S iS S aI6:S iSeS FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作本讲稿第二十六页，共五十五页2022/10/19编译原理编译原理27本讲稿第二十七页，共五十五页2022/10/19编译原理编译原理28I0:S S S iSeS S iS S aI1:S S I2:S i SeS S i S S iSeS S iS S aI3:S a I4:S iS eS S iS I5:S iSe S S iSeS S iS S aI6:S iSeS FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作本讲稿第二十八页，共五十五页2022/10/19编译原理编译原理29根据最近匹配原则选择移进动作 图图4-49 LR分析表分析表本讲稿第二十九页，共五十五页2022/10/19编译原理编译原理304.8.4LR分析的错误恢复qLR分析器在什么情况下发现错误访问动作表时若遇到出错条目，就检测到一个错误访问转移表时它决不会遇到出错条目SLR和LALR分析可能会在报错之前执行几步归约，但决不会把不正确的后继移进栈规范的LR分析器甚至在报告错误之前决不做任何无效归约本讲稿第三十页，共五十五页2022/10/19编译原理编译原理31紧急方式错误恢复q退栈，直至出现状态s,它有预先确定的A的转移；q抛弃若干个输入符号，直至找到a,它是A的合法后继；q再把A和状态gotos,A压进栈，恢复正常分析。本讲稿第三十一页，共五十五页2022/10/19编译原理编译原理32s.栈栈.a.A发现错误发现错误s:C A A b.C A.AAb.b本讲稿第三十二页，共五十五页2022/10/19编译原理编译原理33本讲稿第三十三页，共五十五页2022/10/19编译原理编译原理34本讲稿第三十四页，共五十五页2022/10/19编译原理编译原理35例4.50E E+E|E*E|(E)|ide1:id(状态)3进栈，缺少运算对象e2:从输入删除“)”，右括号不匹配e3:+(状态)4进栈，缺少操作符e4:)(状态)9进栈，缺少右括号本讲稿第三十五页，共五十五页2022/10/19编译原理编译原理36输入id+)的分析和出错恢复分析栈 输入串 动作和错误信息 0 id+)$移进 0id3 +)$归约,E id 0E1 +)$移进 0E1+4 )$e2右括号不匹配，从输入删除“)”0E1+4$e1缺少运算对象，假想的id进栈 0E1+4id3$归约,E id 0E1+4E7$归约,E E+E 0E1$accetp本讲稿第三十六页，共五十五页2022/10/19编译原理编译原理374.9 语法分析器的生成器语法分析器的生成器qYacc：yet another compiler-compiler基于LALR(1)的语法分析程序的生成器qYacc 的 GNU 版叫做 Bison。qYacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF,Backus Naur Form)来书写。本讲稿第三十七页，共五十五页2022/10/19编译原理编译原理38491 分析器的生成器分析器的生成器Yacc q按照惯例，Yacc 文件有 y 后缀。q调用 Yacc 编译器：yacc Yacc编译器编译器Yacc源程序源程序translateyytabcC编译器编译器ytabcaoutaout输入输入输出输出本讲稿第三十八页，共五十五页2022/10/19编译原理编译原理39语法规则语法规则(.y文件文件)yyparse()YaccLex词法规则词法规则(.l文文件件)yylex()输出输出本讲稿第三十九页，共五十五页2022/10/19编译原理编译原理40用用 Yacc 创建语法分析器包括四个步骤：创建语法分析器包括四个步骤：q通过在语法文件上运行 Yacc 生成一个解析器。q说明语法：编写一个y的语法文件（同时说明C在这里要进行的动作）。写一个词法分析器来处理输入并将标记传递给解析器。这可以使用Lex来完成。编写一个函数，通过调用yyparse()来开始解析。编写错误处理例程（如yyerror()）。q编译 Yacc 生成的代码以及其他相关的源文件。q将目标文件链接到适当的可执行解析器库。本讲稿第四十页，共五十五页2022/10/19编译原理编译原理41Yacc源程序的组成部分源程序的组成部分%C声明%文法规则及翻译规则%用C语言编写的支持例程本讲稿第四十一页，共五十五页2022/10/19编译原理编译原理42例例4.50 台式计算器台式计算器 E E+T|T T T*F|F F (E)|digitdigitq读入一个算术表达式，计算它的值并输出。本讲稿第四十二页，共五十五页2022/10/19编译原理编译原理43%#include%token DIGIT%line:exprn printf(“%dn”,$1);expr:expr+term$=$1+$3;:term ;所声明的token可用于第二、三部分$表示左部非终结符的属性值，$i表示右部第i个文法符号关联的属性值。默认动作是$=$1;本讲稿第四十三页，共五十五页2022/10/19编译原理编译原理44term:term*factor$=$1*$3;:factor ;factor:(expr)$=$2;:DIGIT ;%yylex()int c;c=getchar();if(isdigit(c)yylval=c-0;return DIGIT;return c;辅助的简单词法分析程序本讲稿第四十四页，共五十五页2022/10/19编译原理编译原理454.9.2 用用Yacc处理二义文法处理二义文法q采用简单的二义文法：E E+E|E-E|E*E|E/E|(E)|-E|numbernumberq输入一个表达式并回车，显示计算结果。q也可以输入一个空白行。本讲稿第四十五页，共五十五页2022/10/19编译原理编译原理46声明部分声明部分%#include#include#define YYSTYPE double /*将栈定义为double类型*/%token NUMBER%left +%left */%right UMINUS%本讲稿第四十六页，共五十五页2022/10/19编译原理编译原理47翻译规则翻译规则lines:lines expr 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%prec UMINUS$=$2;|NUMBER;%本讲稿第四十七页，共五十五页2022/10/19编译原理编译原理48支持例程支持例程yylex()int c;while(c=getchar()=);if(c=)|(isdigit(c)ungetc(c,stdin);scanf(“%lf”,&yylval);return NUMBER;return c;本讲稿第四十八页，共五十五页2022/10/19编译原理编译原理49Yacc文件格式中的几个问题文件格式中的几个问题qTOKEN的定义%token NUM%token IDENTq语法规则与语义动作本讲稿第四十九页，共五十五页2022/10/19编译原理编译原理50Yacc文件格式中的几个问题文件格式中的几个问题q为算符指定优先级与结合率%left -+%left */%left NEG /*negation-unary minus*/%right /*exponentiation */q二义性及冲突的解决归约/归约冲突：选择Yacc说明中先出现的产生式移进/归约冲突：移近优先q出错处理本讲稿第五十页，共五十五页2022/10/19编译原理编译原理51将将 Lex 与与 Yacc 结合起来结合起来 q一个程序通常在每次返回一个标记时都要调用 yylex()函数。只有在文件结束或者出现错误标记时才会终止。q一个由 Yacc 生成的解析器调用 yylex()函数来获得标记。yylex()可以由 Lex 来生成或完全由自己来编写。对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。因此 Lex 中匹配模式时的动作一般格式为：pattern /*do something*/return TOKEN_NAME;本讲稿第五十一页，共五十五页2022/10/19编译原理编译原理52q于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的.y文件时，会生成一个头文件，它对每个标记都有#define 的定义。如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件.lex中的 C 声明段中包括#include“lex.yy.c”。本讲稿第五十二页，共五十五页2022/10/19编译原理编译原理53Yacc的错误恢复的错误恢复q编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。qYacc把错误产生式当作普通产生式处理本讲稿第五十三页，共五十五页2022/10/19编译原理编译原理54q遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析本讲稿第五十四页，共五十五页2022/10/19编译原理编译原理55包含错误恢复的计算器包含错误恢复的计算器lines:lines expr nprintf(“%g n”,$2)|lines n|/*/|error nprintf(“重新输入上一行”);yyerrok;本讲稿第五十五页，共五十五页