1、2022-7-291第四章第四章 语法分析语法分析(5)4.82022-7-29编译原理2LR Parsing2022-7-29编译原理3LR(0)项目项目q 在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。A XYZq 由X推导出的子串已经分析过，X出现在栈中，下一步希望看到YZ推导出的子串。2022-7-29编译原理4闭包运算闭包运算closureq 若项目集I中有项目A B，且有产生式B ，则下一步希望看到由B推导出的子串，那么等同于希望看到，因此将项目B 加入 closure(I)2022-7-29编译原理5有效项目有效项目q 有效项目：有效项目：如果存在规
2、范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。代表某一时刻，栈中的内容是1（活前缀）。一个活前缀的有效项目集就是从DFA的初态出发，沿着标记为的路径到达的那个项目集（状态）。2022-7-29编译原理6q 项目决定了动作：移进或归约q 希望同一个项目集中的若干个项目没有动作冲突q SLR(1)分析方法 若有A 在Ii中，那么对FOLLOW(A)中的所有a，actioni,a为rj 更好的避免冲突的方法2022-7-29编译原理7LR(1)分析法分析法q 需要更多的信息，指出A 句柄之后紧跟哪个终结符才能归约S*Aaw aw，q 让项目带上搜索符，LR(1)项目由LR(0)项
3、目和一个lookahead符号组成：A ,a搜索符a的集合总是Follow(A)的子集。2022-7-29编译原理8活前缀的有效活前缀的有效LR(1)项目项目q LR(1)项目A,a对活前缀有效，如果存在着推导S*rm Aw rm w，其中：1.=；a是w的第一个符号，或者w为且a是$。2022-7-29编译原理9构造有效的构造有效的LR(1)项目集项目集q 项目A B,a对活前缀有效，必定存在S*rm Aax rm Bax，其中=。q 假设ax能推出by，那么，B,b对有效，b是从 能推出的开始符号，或当 可空时，b就是a。bFIRST(a)。2022-7-29编译原理10LALR分析表的构
4、造分析表的构造1.先构造文法的LR(1)项目集族C=I0,I1,In；2.再合并C中的同心集，得到C=J0,J1,Jm；由此得到的识别活前缀的DFA实际上和LR(0)项目的DFA相同，但带上了搜索符2022-7-29编译原理11wA wALL分析方法和分析方法和LR分析方法的比较分析方法的比较q A ，LL(1)向前看下一个输入根据FIRST()确定使用哪条产生式推导；而LR(1)是在识别出整个后，再往前看1个符号，然后确定使用哪条产生式归约。SS2022-7-29编译原理12在下面的推导中，最后一步用的是A LL(1)决定用该决定用该产生式的位置是产生式的位置是First()LR(1)决定用
5、该决定用该产生式的位置产生式的位置LL分析方法和分析方法和LR分析方法的比较分析方法的比较bwAbwSrmrm*wwASlmlm*2022-7-29编译原理13非非LR结构结构q 例：L=wwR wa,b*S aSa bSb 2022-7-29编译原理14LL分析方法和LR分析方法的比较q LL(k)文法都是LR(k)文法。LR文法比LL文法描述的语言更多。2022-7-29编译原理15LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规范 归 约(最右推导的逆过程)最 左 推 导 决定使用产生式的时机 看见产生式右部推出的全部内容后再决定用哪
6、个产生式进行归约 看见产生式右部推出的第一个终结符后就确定用哪个产生式进行推导 LR分析方法和LL分析方法的比较2022-7-29编译原理16LR(1)方 法 LL(1)方 法 对CFG的显式限制 没有限制 无左递归、无公共左因子 分析表比较 状态文法符号 分析表大 非终结符终结符分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 LR分析方法和分析方法和LL分析方法的比较分析方法的比较2022-7-29编译原理17LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 不会将出错点后的符号移入分析栈 和
7、LR一样，不会读过出错点而不报错 LR分析方法和分析方法和LL分析方法的比较分析方法的比较2022-7-29编译原理1848 二义文法的应用二义文法的应用q 任何二义性的文法都不是LR文法。q 二义文法的特点：简洁、自然例如，表达式文法二义文法：E E+E|E*E|(E)|id非二义的文法：E E+T|TT T*F|FF (E)|idq 语法分析的效率高（基于消除二义后得到的分析表）2022-7-29编译原理194.8.1 使用文法以外信息解决分析动使用文法以外信息解决分析动作冲突作冲突优先级和结合规则例：规定：*优先级高于+，两者都是左结合E E+E|E*E|(E)|id2022-7-29编
8、译原理20拓广文法的拓广文法的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-7-29编译原理212022-7-29编译原理22SLR分析表（存在冲突）分析表（存
9、在冲突）2022-7-29编译原理23使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突考虑考虑id+id+id 和和id+id*id 形成格局形成格局 栈栈输入输入0E1+4E7*id$面临+，归约面临*，移进面临)和$，归约I7:EE+E EE+E EE*E2022-7-29编译原理244.8.2 悬空悬空else的二义性的二义性S SS iSeS|iS|a2022-7-29编译原理25I0: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
10、 S iSeS S iS S aI6:S iSeS FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作2022-7-29编译原理262022-7-29编译原理27I0: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-7-29编译原理28根据最近匹配原则选择移进动作 图图4-49 LR分析表分析表2022-7-29编译
11、原理29处理处理iiaea的语法分析动作的语法分析动作2022-7-29编译原理304.8.3 LR分析的错误恢复q LR分析器在什么情况下发现错误访问动作表时若遇到出错条目，就检测到一个语法错误访问转移表时不会遇到出错条目若发现当前已扫描的输入不可能存在正确的后续，LR语法分析器立刻报错（决不做任何无效归约）SLR和LALR分析可能会在报错之前执行几步归约，但决不会把不正确的后继移进栈2022-7-29编译原理31紧急方式错误恢复（panic mode）q 退栈，直至出现状态s,它有预先确定的A的转移；q 抛弃若干个输入符号，直至找到a,它是A的合法后继；q 再把A和状态gotos,A压进栈
12、，恢复正常分析。2022-7-29编译原理32s.栈栈.a.A发现错误发现错误s:C A A b.C A.AAb.b2022-7-29编译原理33s.栈栈.a.A发现错误发现错误sgoto(s,A).栈栈.a.A继续分析继续分析2022-7-29编译原理34例4.49 E E+E|E*E|(E)|idaction goto 状态 id +*()$E 0 1 2 3 4 5 6 7 8 9 s3 e1 e1 s2 e2 e1 e3 s4 s5 e3 e2 acc s3 e1 e1 s2 e2 e1 r4 r4 r4 r4 r4 r4 s3 e1 e1 s2 e2 e1 s3 e1 e1 s2 e
13、2 e1 e3 s4 s5 e3 s9 e4 r1 r1 s5 r1 r1 r1 r2 r2 r2 r2 r2 r2 r3 r3 r3 r3 r3 r3 1 6 7 8 e1:id(状态)3进栈，缺少运算对象e2:从输入删除“)”，右括号不匹配e3:+(状态)4进栈，缺少操作符e4:)(状态)9进栈，缺少右括号2022-7-29编译原理35输入id+)的分析和出错恢复分析栈 输入串 动作和错误信息 0 id+)$移进 0id3 +)$归约,E id 0E1 +)$移进 0E1+4 )$e2右括号不匹配，从输入删除“)”0E1+4$e1缺少运算对象，假想的id进栈 0E1+4id3$归约,E i
14、d 0E1+4E7$归约,E E+E 0E1$accept2022-7-29编译原理364.9 语法分析器的生成器语法分析器的生成器q Yacc：yet another compiler-compiler基于LALR(1)的语法分析程序的生成器q Yacc 的 GNU 版叫做 Bison。q Yacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF,Backus Naur Form)来书写。2022-7-29编译原理37491 分析器的生成器分析器的生成器Yacc q 按照惯例，Yacc 源文件的后缀为 y。q 调用 Yacc 编译器：yacc Ya
15、cc编译器编译器Yacc源程序源程序translateyytabcC编译器编译器ytabcaoutaout输入输入输出输出2022-7-29编译原理38语法规则语法规则(.y文件文件)yyparse()YaccLex词法规则词法规则(.l文件文件)yylex()输出输出2022-7-29编译原理39用用 Yacc 创建语法分析器包括四个步创建语法分析器包括四个步骤：骤：q 通过在语法文件上运行 Yacc 生成一个解析器。q 说明语法：编写一个 y 的语法文件（同时说明 C 在这里要进行的动作）。写一个词法分析器来处理输入并将标记传递给解析器。这可以使用 Lex 来完成。编写一个函数，通过调用
16、yyparse()来开始解析。编写错误处理例程（如 yyerror()）。q 编译 Yacc 生成的代码以及其他相关的源文件。q 将目标文件链接到适当的可执行解析器库。2022-7-29编译原理40Yacc源程序的组成部分源程序的组成部分%C声明%对词法单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程声明部分2022-7-29编译原理41翻译规则翻译规则q 产生式 1|2|nq 写成：1 语义动作|2 语义动作|n 语义动作；2022-7-29编译原理42q 带单引号的单个字符终结符q 语义动作：$表示左部非终结符的属性值，$i表示右部第i个文法符号关联的属性值。默认动作是$=$1
17、;expr:exprexpr:expr+term +term$=$1+$3;$=$1+$3;|term|term ;2022-7-29编译原理43例例4.50 台式计算器台式计算器 E E+T|T T T*F|F F (E)|digitdigitq 读入一个算术表达式，计算它的值并输出。2022-7-29编译原理44%#include ctype.h#include%token DIGIT%token DIGIT%line:exprline:expr nn printf(“%dn”,$1);printf(“%dn”,$1);expr:exprexpr:expr +term term$=$1+$
18、3;$=$1+$3;|term|term ;term:termterm:term *factor$=$1factor$=$1*$3;$3;|factor|factor ;factor:factor:(exprexpr )$=$2;$=$2;|DIGIT|DIGIT ;%2022-7-29编译原理45yylexyylex()()intint c;c;c=getcharc=getchar();();if(isdigit(cif(isdigit(c)yylvalyylval=c-=c-0 0;return DIGIT;return DIGIT;return c;return c;词法分析返回二元组词
19、法分析返回二元组 由变量由变量yylval传递给传递给Parser在声明部分进行在声明部分进行说明，如说明，如DIGIT2022-7-29编译原理464.9.2 用用Yacc处理二义文法处理二义文法q 采用简单的二义文法：E E+E|E-E|E*E|E/E|(E)|-E|numbernumberq 输入一个表达式并回车，显示计算结果。q 也可以输入一个空白行。2022-7-29编译原理47声明部分声明部分%#include#include#define YYSTYPE double /*将栈定义为double类型*/%token NUMBER%left +%left */%right UMIN
20、US%2022-7-29编译原理48翻译规则翻译规则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-7-29编译原理49支持例程支持例程yylex()int c;while(c=getchar()=);if(c=)|(isdigit(c)ungetc(c,stdin);scanf(“%lf”,&yylv
21、al);return NUMBER;return c;2022-7-29编译原理50Yacc文件格式中的几个问题文件格式中的几个问题q TOKEN的定义%token NUM%token IDENTq 语法规则与语义动作2022-7-29编译原理51Yacc文件格式中的几个问题文件格式中的几个问题q 为算符指定优先级与结合率%left -+%left */%left NEG /*negation-unary minus*/%right /*exponentiation */q 二义性及冲突的解决归约/归约冲突：选择Yacc说明中先出现的产生式移进/归约冲突：移近优先q 出错处理2022-7-29
22、编译原理52将将 Lex 与与 Yacc 结合起来结合起来 q 一个程序通常在每次返回一个标记时都要调用 yylex()函数。只有在文件结束或者出现错误标记时才会终止。q 一个由 Yacc 生成的解析器调用 yylex()函数来获得标记。yylex()可以由 Lex 来生成或完全由自己来编写。对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。因此 Lex 中匹配模式时的动作一般格式为：pattern /*do something*/return TOKEN_NAME;2022-7-29编译原理53q 于是 Yacc 就会获得返
23、回的标记。当 Yacc 编译一个带有 _d 标记的.y文件时，会生成一个头文件，它对每个标记都有#define 的定义。如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件.lex中的 C 声明段中包括#include“lex.yy.c”。2022-7-29编译原理54Yacc的错误恢复的错误恢复q 编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。q Yacc把错误产生式当作普通产生式处理2022-7-29编译原理55q 遇到语法错误时从栈中弹出状态，直到
24、发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析2022-7-29编译原理56包含错误恢复的计算器包含错误恢复的计算器lines:lines expr nprintf(“%g n”,$2)|lines n|/*/|error nprintf(“重新输入上一行”);yyerrok;2022-7-29编译原理57Flex&Bison的使用的使用q Flex.exeq Bison.exe2022-7-29编译原理58步骤步骤1q 点击“开始”，在“开始”菜单中选择“运行”2022-7-29
25、编译原理59步骤步骤2q 在弹出的对话框中敲入cmd，启动DOS窗口2022-7-29编译原理60步骤步骤3q 在DOS窗口中把当前目录切换到存放bison和flex的目录（例中为d:bison）2022-7-29编译原理61步骤步骤4q 在bison目录中建立一个子目录来放置相关的文件（例中为example）2022-7-29编译原理62步骤步骤5q 用文本编辑器编辑相应的bison和flex文件myyacc.y和mylex.l（注意：这两个文件名不要变）2022-7-29编译原理63步骤步骤6q 运行bison生成myyacc.tab.c和myyacc.tab.h文件2022-7-29编译
26、原理64步骤步骤7q 运行flex生成lex.yy.c文件2022-7-29编译原理65步骤步骤8q 在这个目录中再编写一个C文件example.c（具体见所给的例子）2022-7-29编译原理66步骤步骤9q 双击example.c文件用VC+打开这个文件，然后编译这个文件2022-7-29编译原理67步骤步骤10q 这时候会弹出一个对话框问你是否要建立一个缺省的项目工作空间，选择“是”2022-7-29编译原理68q VC+会自动建立一个工程项目，并编译刚才的C文件2022-7-29编译原理69步骤步骤11q 点击窗口左侧的“FileView”切换到文件视图，将bison和flex生成的三个文件加入工程2022-7-29编译原理70步骤步骤12q 再编译并链接生成可执行文件2022-7-29编译原理71q 成功后生成example.exe2022-7-29编译原理72步骤步骤13q 在当前目录的debugdebug子目录中建立一个名为exprTest.txtexprTest.txt的文本文件来测试
