第四章--语法分析(5)课件

1、第四章 语法分析(5)4.87/25/20221LR Parsing7/25/20222编译原理LR(0)项目在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。 A XYZ由X推导出的子串已经分析过， X出现在栈中，下一步希望看到YZ推导出的子串。7/25/20223编译原理闭包运算closure若项目集I中有项目A B ，且有产生式B ，则下一步希望看到由B推导出的子串，那么等同于希望看到 ，因此将项目B 加入 closure(I)7/25/20224编译原理有效项目有效项目：如果存在规范推导 S *Aw 12w，则说项目A1 2对活前缀 1 是有效的。代表某一时刻

2、，栈中的内容是1 （活前缀）。一个活前缀的有效项目集就是从DFA的初态出发，沿着标记为的路径到达的那个项目集（状态） 。7/25/20225编译原理项目决定了动作：移进或归约希望同一个项目集中的若干个项目没有动作冲突SLR(1)分析方法若有A 在Ii中，那么对FOLLOW(A)中的所有a， actioni, a为rj更好的避免冲突的方法7/25/20226编译原理LR(1)分析法需要更多的信息，指出A 句柄之后紧跟哪个终结符才能归约S *Aaw aw，让项目带上搜索符，LR(1)项目由LR(0)项目和一个lookahead符号组成： A , a搜索符a的集合总是Follow(A)的子集。7/2

3、5/20227编译原理活前缀的有效LR(1)项目LR(1)项目A, a对活前缀有效，如果存在着推导S *rm Aw rm w，其中： = ； a是w的第一个符号，或者w为且a是$。7/25/20228编译原理构造有效的LR(1)项目集项目A B, a对活前缀有效，必定存在S *rm Aax rm Bax，其中 = 。假设ax能推出by，那么， B , b对有效，b是从 能推出的开始符号，或当 可空时，b就是a。bFIRST(a)。7/25/20229编译原理LALR分析表的构造1. 先构造文法的LR(1)项目集族C=I0, I1, , In；2. 再合并C中的同心集，得到C=J0, J1, ,

4、 Jm；由此得到的识别活前缀的DFA实际上和LR(0)项目的DFA相同，但带上了搜索符7/25/202210编译原理wAwALL分析方法和LR分析方法的比较A ，LL(1) 向前看下一个输入根据FIRST()确定使用哪条产生式推导；而LR(1)是在识别出整个后，再往前看1个符号，然后确定使用哪条产生式归约。SS7/25/202211编译原理在下面的推导中，最后一步用的是A LL(1)决定用该产生式的位置是First()LR(1)决定用该产生式的位置LL分析方法和LR分析方法的比较7/25/202212编译原理非LR结构例：L=wwR wa, b*S aSa bSb 7/25/202213编译原

5、理LL分析方法和LR分析方法的比较LL(k)文法都是LR(k)文法。LR文法比LL文法描述的语言更多。7/25/202214编译原理LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规范 归 约(最右推导的逆过程) 最 左 推 导 决定使用产生式的时机 看见产生式右部推出的全部内容后再决定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后就确定用哪个产生式进行推导 LR分析方法和LL分析方法的比较7/25/202215编译原理LR(1)方 法 LL(1)方 法 对CFG的显式限制 没有限制 无左递归、无公共左因子 分析表比较 状态文法符号

6、 分析表大 非终结符终结符分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 LR分析方法和LL分析方法的比较7/25/202216编译原理LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 不会将出错点后的符号移入分析栈 和LR一样，不会读过出错点而不报错 LR分析方法和LL分析方法的比较7/25/202217编译原理48 二义文法的应用任何二义性的文法都不是LR文法。二义文法的特点：简洁、自然例如，表达式文法二义文法：E E + E | E * E | (E) | id非二义的文法：E E + T

7、 | TT T * F | FF (E) | id语法分析的效率高（基于消除二义后得到的分析表）7/25/202218编译原理4.8.1 使用文法以外信息解决分析动作冲突优先级和结合规则例：规定： *优先级高于+，两者都是左结合E E + E | E * E | (E) | id7/25/202219编译原理拓广文法的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

8、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) = $,+,*,)移进-归约冲突7/25/202220编译原理7/25/202221编译原理SLR分析表（存在冲突）7/25/202222编译原理使用文法以外信息来解决分析动作冲突考虑id + id + id 和id + id * id 形成格局 栈输入0E1+4E7*id$面临+，归约面临*，移进面临 ) 和$，归约I7: EE+E EE+E EE*E7/25/202223编译原理4.8.2 悬空else的二义

9、性S SS iSeS | iS | a7/25/202224编译原理I0: 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移进-归约冲突根据最近匹配原则选择移进动作7/25/202225编译原理7/25/202226编译原理I0: 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

10、I4: S iS eS S iS I5: S iSe S S iSeS S iS S aI6: S iSeS FOLLOW(S) = i, e移进-归约冲突根据最近匹配原则选择移进动作7/25/202227编译原理根据最近匹配原则选择移进动作 图4-49 LR分析表7/25/202228编译原理处理iiaea的语法分析动作7/25/202229编译原理4.8.3 LR分析的错误恢复LR分析器在什么情况下发现错误访问动作表时若遇到出错条目，就检测到一个语法错误访问转移表时不会遇到出错条目若发现当前已扫描的输入不可能存在正确的后续，LR语法分析器立刻报错（决不做任何无效归约）SLR和LALR分析可

11、能会在报错之前执行几步归约，但决不会把不正确的后继移进栈7/25/202230编译原理紧急方式错误恢复（panic mode）退栈，直至出现状态s, 它有预先确定的A的转移；抛弃若干个输入符号，直至找到a, 它是A的合法后继；再把A和状态gotos, A压进栈，恢复正常分析。7/25/202231编译原理s.栈. . . . . . . . a . .A发现错误s :C AA b. . .C A. . .AAb. . .b7/25/202232编译原理s.栈. . . . . . . . a . .A发现错误sgoto(s,A).栈. . . . . . . . a . .A继续分析7/25/

12、202233编译原理例4.49 E E + E | E * E | (E) | ide1: id(状态)3进栈，缺少运算对象e2:从输入删除“)”，右括号不匹配e3:+(状态)4进栈，缺少操作符e4: )(状态)9进栈，缺少右括号7/25/202234编译原理输入id+)的分析和出错恢复分析栈 输入串 动作和错误信息 0 id+)$ 移进 0id3 +)$ 归约, E id 0E1 +)$ 移进 0E1+4 )$ e2右括号不匹配，从输入删除“)” 0E1+4 $ e1缺少运算对象，假想的id进栈 0E1+4id3 $ 归约, E id 0E1+4E7 $归约, E E+E 0E1 $acce

13、pt7/25/202235编译原理4.9 语法分析器的生成器Yacc：yet another compiler-compiler基于LALR(1)的语法分析程序的生成器Yacc 的 GNU 版叫做 Bison。Yacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF, Backus Naur Form)来书写。7/25/202236编译原理491 分析器的生成器Yacc 按照惯例，Yacc 源文件的后缀为 y 。调用 Yacc 编译器： yacc Yacc编译器Yacc源程序translateyytabcC编译器ytabcaoutaout输入输出7/

14、25/202237编译原理语法规则(.y文件)yyparse()YaccLex词法规则(.l文件)yylex()输出7/25/202238编译原理用 Yacc 创建语法分析器包括四个步骤：通过在语法文件上运行 Yacc 生成一个解析器。 说明语法： 编写一个 y 的语法文件（同时说明 C 在这里要进行的动作）。 写一个词法分析器来处理输入并将标记传递给解析器。 这可以使用 Lex 来完成。 编写一个函数，通过调用 yyparse() 来开始解析。 编写错误处理例程（如 yyerror()）。 编译 Yacc 生成的代码以及其他相关的源文件。 将目标文件链接到适当的可执行解析器库。7/25/20

15、2239编译原理Yacc源程序的组成部分%C声明%对词法单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程声明部分7/25/202240编译原理翻译规则产生式 1| 2 | |n写成： ：1 语义动作| 2 语义动作| | n 语义动作；7/25/202241编译原理带单引号的单个字符终结符语义动作：$表示左部非终结符的属性值，$i表示右部第i个文法符号关联的属性值。默认动作是$ =$1;expr : expr + term $ = $1 + $3; | term ;7/25/202242编译原理例4.50 台式计算器 E E + T | T T T * F | F F ( E )

16、| digit读入一个算术表达式，计算它的值并输出。7/25/202243编译原理%#include %token DIGIT%line:exprn printf(“%dn”,$1); ;expr:expr +term $=$1+$3; | term ;term:term *factor $=$1*$3; | factor ;factor:(expr ) $=$2; | DIGIT ;%7/25/202244编译原理yylex() int c; c=getchar(); if (isdigit(c) yylval = c - 0; return DIGIT; return c; 词法分析返回二

17、元组 由变量yylval传递给Parser在声明部分进行说明，如DIGIT7/25/202245编译原理4.9.2 用Yacc处理二义文法采用简单的二义文法： E E + E | E - E | E * E | E / E | ( E ) | - E | number输入一个表达式并回车，显示计算结果。也可以输入一个空白行。7/25/202246编译原理声明部分%# include # include # define YYSTYPE double /* 将栈定义为double类型 */%token NUMBER%left + %left * / %right UMINUS% 7/25/202

18、247编译原理翻译规则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;%7/25/202248编译原理支持例程yylex ( ) int c;while ( ( c = getchar ( ) ) = = );

19、if ( ( c = = ) | | (isdigit (c) ) ) ungetc (c, stdin);scanf ( “% lf ”, &yylval);return NUMBER;return c;7/25/202249编译原理Yacc文件格式中的几个问题TOKEN的定义%token NUM %token IDENT语法规则与语义动作7/25/202250编译原理Yacc文件格式中的几个问题为算符指定优先级与结合率%left - + %left * / %left NEG /* negation-unary minus */ %right /* exponentiation */二义性

20、及冲突的解决归约/归约冲突：选择Yacc说明中先出现的产生式移进/归约冲突：移近优先出错处理7/25/202251编译原理将 Lex 与 Yacc 结合起来 一个程序通常在每次返回一个标记时都要调用 yylex() 函数。只有在文件结束或者出现错误标记时才会终止。 一个由 Yacc 生成的解析器调用 yylex() 函数来获得标记。 yylex() 可以由 Lex 来生成或完全由自己来编写。 对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。 因此 Lex 中匹配模式时的动作一般格式为： pattern /* do somet

21、hing*/ return TOKEN_NAME; 7/25/202252编译原理于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的 .y文件时，会生成一个头文件，它对每个标记都有 #define 的定义。 如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件 .lex中的 C 声明段中包括#include “lex.yy.c”。 7/25/202253编译原理Yacc的错误恢复编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。Ya

22、cc把错误产生式当作普通产生式处理7/25/202254编译原理遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析7/25/202255编译原理包含错误恢复的计算器lines: lines expr nprintf ( “%g n”, $2 ) | lines n| /* */| error nprintf ( “重新输入上一行”); yyerrok;7/25/202256编译原理Flex & Bison的使用Flex.exeBison.exe7/25/202257编译原理步骤