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

1、2022-4-6编译原理1LR Parsing2022-4-6编译原理2LR(0)项目项目q 在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。 A XYZq 由X推导出的子串已经分析过， X出现在栈中，下一步希望看到YZ推导出的子串。2022-4-6编译原理3闭包运算闭包运算closureq 若项目集I中有项目A B ，且有产生式B ，则下一步希望看到由B推导出的子串，那么等同于希望看到 ，因此将项目B 加入 closure(I)2022-4-6编译原理4有效项目有效项目q 有效项目：有效项目：如果存在规范推导 S *Aw 12w，则说项目A1 2对活前缀 1 是有

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

3、a的集合总是Follow(A)的子集。2022-4-6编译原理7活前缀的有效活前缀的有效LR(1)项目项目q LR(1)项目A, a对活前缀有效，如果存在着推导S *rm Aw rm w，其中：1. = ；2. a是w的第一个符号，或者w为且a是$。2022-4-6编译原理8构造有效的构造有效的LR(1)项目集项目集q 项目A B, a对活前缀有效，必定存在S *rm Aax rm Bax，其中 = 。q 假设ax能推出by，那么， B , b对有效，b是从 能推出的开始符号，或当 可空时，b就是a。bFIRST(a)。2022-4-6编译原理9LALR分析表的构造分析表的构造1. 先构造文法

4、的LR(1)项目集族C=I0, I1, , In；2. 再合并C中的同心集，得到C=J0, J1, , Jm； 由此得到的识别活前缀的DFA实际上和LR(0)项目的DFA相同，但带上了搜索符2022-4-6编译原理10wA wALL分析方法和分析方法和LR分析方法的比较分析方法的比较q A ，LL(1) 向前看下一个输入根据FIRST()确定使用哪条产生式推导；而LR(1)是在识别出整个后，再往前看1个符号，然后确定使用哪条产生式归约。SS2022-4-6编译原理11在下面的推导中，最后一步用的是A LL(1)决定用该决定用该产生式的位置是产生式的位置是First( )LR(1)决定用该决定用

5、该产生式的位置产生式的位置LL分析方法和分析方法和LR分析方法的比较分析方法的比较bwAbwSrmrm*wwASlmlm*2022-4-6编译原理12非非LR结构结构q 例：L=wwR wa, b*S aSa bSb 2022-4-6编译原理13LL分析方法和LR分析方法的比较q LL(k)文法都是LR(k)文法。LR文法比LL文法描述的语言更多。2022-4-6编译原理14LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规范 归 约(最右推导的逆过程) 最 左 推 导 决定使用产生式的时机 看见产生式右部推出的全部内容后再决定用哪个产生式进

6、行归约 看见产生式右部推出的第一个终结符后就确定用哪个产生式进行推导 LR分析方法和LL分析方法的比较2022-4-6编译原理15LR(1)方 法 LL(1)方 法 对CFG的显式限制 没有限制 无左递归、无公共左因子 分析表比较 状态文法符号 分析表大 非终结符终结符分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 LR分析方法和分析方法和LL分析方法的比较分析方法的比较2022-4-6编译原理16LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 不会将出错点后的符号移入分析栈 和LR一样，不会

7、读过出错点而不报错 LR分析方法和分析方法和LL分析方法的比较分析方法的比较2022-4-6编译原理1748 二义文法的应用二义文法的应用q 任何二义性的文法都不是LR文法。q 二义文法的特点：简洁、自然例如，表达式文法二义文法：E E + E | E * E | (E) | id非二义的文法：E E + T | TT T * F | FF (E) | idq 语法分析的效率高（基于消除二义后得到的分析表）2022-4-6编译原理184.8.1 使用文法以外信息解决分析动使用文法以外信息解决分析动作冲突作冲突优先级和结合规则例：规定： *优先级高于+，两者都是左结合E E + E | E *

8、E | (E) | id2022-4-6编译原理19拓广文法的拓广文法的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-4-

9、6编译原理202022-4-6编译原理21SLR分析表（存在冲突）分析表（存在冲突）2022-4-6编译原理22使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突考虑考虑id + id + id 和和id + id * * id 形成格局形成格局 栈栈输入输入0E1+4E7*id$面临+，归约面临*，移进面临 ) 和$，归约I7: EE+E EE+E EE*E2022-4-6编译原理234.8.2 悬空悬空else的二义性的二义性S SS iSeS | iS | a2022-4-6编译原理24I0: S S S iSeS S iS S aI1: S S I2: S i SeS

10、 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-4-6编译原理252022-4-6编译原理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移进-归约冲突

11、根据最近匹配原则选择移进动作2022-4-6编译原理27根据最近匹配原则选择移进动作 图图4-49 LR分析表分析表2022-4-6编译原理28处理处理iiaea的语法分析动作的语法分析动作2022-4-6编译原理294.8.3 LR分析的错误恢复q LR分析器在什么情况下发现错误访问动作表时若遇到出错条目，就检测到一个语法错误访问转移表时不会遇到出错条目若发现当前已扫描的输入不可能存在正确的后续，LR语法分析器立刻报错（决不做任何无效归约）SLR和LALR分析可能会在报错之前执行几步归约，但决不会把不正确的后继移进栈2022-4-6编译原理30紧急方式错误恢复（panic mode）q 退栈

12、，直至出现状态s, 它有预先确定的A的转移；q 抛弃若干个输入符号，直至找到a, 它是A的合法后继；q 再把A和状态gotos, A压进栈，恢复正常分析。2022-4-6编译原理31s.栈栈. . . . . . . . a . .A发现错误发现错误s :C A A b . . .C A . . .AAb . . .b2022-4-6编译原理32s.栈栈. . . . . . . . a . .A发现错误发现错误sgoto(s,A).栈栈. . . . . . . . a . .A继续分析继续分析2022-4-6编译原理33例4.49 E E + E | E * E | (E) | idact

13、ion 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 e2 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: )(状态)

14、9进栈，缺少右括号2022-4-6编译原理34输入id+)的分析和出错恢复分析栈 输入串 动作和错误信息 0 id+)$ 移进 0id3 +)$ 归约, E id 0E1 +)$ 移进 0E1+4 )$ e2右括号不匹配，从输入删除“)” 0E1+4 $ e1缺少运算对象，假想的id进栈 0E1+4id3 $ 归约, E id 0E1+4E7 $归约, E E+E 0E1 $accept2022-4-6编译原理354.9 语法分析器的生成器语法分析器的生成器q Yacc：yet another compiler-compiler基于LALR(1)的语法分析程序的生成器q Yacc 的 GNU

15、版叫做 Bison。q Yacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF, Backus Naur Form)来书写。2022-4-6编译原理36491 分析器的生成器分析器的生成器Yacc q 按照惯例，Yacc 源文件的后缀为 y 。q 调用 Yacc 编译器： yacc Yacc编译器编译器Yacc源程序源程序translateyytabcC编译器编译器ytabcaoutaout输入输入输出输出2022-4-6编译原理37语法规则语法规则(.y文件文件)yyparse()YaccLex词法规则词法规则(.l文件文件)yylex()输出输

16、出2022-4-6编译原理38用用 Yacc 创建语法分析器包括四个步创建语法分析器包括四个步骤：骤：q 通过在语法文件上运行 Yacc 生成一个解析器。 q 说明语法： 编写一个 y 的语法文件（同时说明 C 在这里要进行的动作）。 写一个词法分析器来处理输入并将标记传递给解析器。 这可以使用 Lex 来完成。 编写一个函数，通过调用 yyparse() 来开始解析。 编写错误处理例程（如 yyerror()）。 q 编译 Yacc 生成的代码以及其他相关的源文件。 q 将目标文件链接到适当的可执行解析器库。2022-4-6编译原理39Yacc源程序的组成部分源程序的组成部分%C声明%对词法

17、单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程声明部分2022-4-6编译原理40翻译规则翻译规则q 产生式 1| 2 | |nq 写成： ：1 语义动作| 2 语义动作| | n 语义动作；2022-4-6编译原理41q 带单引号的单个字符终结符q 语义动作：$表示左部非终结符的属性值，$i表示右部第i个文法符号关联的属性值。默认动作是$ =$1;expr : expr + term expr : expr + term $ = $1 + $3; $ = $1 + $3; | term | term ; ;2022-4-6编译原理42例例4.50 台式计算器台式计算器 E E

18、+ T | T T T * F | F F ( E ) | digitdigitq 读入一个算术表达式，计算它的值并输出。2022-4-6编译原理43%#include #include %token DIGIT%token DIGIT%line:exprline:expr nn printf(“%dn”,$1);printf(“%dn”,$1); ; ;expr:expr expr:expr + + term term $=$1+$3;$=$1+$3; | term | term ; ;term:term term:term * * factor $=$1factor $=$1* *$3;$

19、3; | factor | factor ; ;factor:factor: ( ( expr expr ) ) $=$2; $=$2; | DIGIT | DIGIT ; ;%2022-4-6编译原理44yylex()yylex() int c;int c; c=getchar();c=getchar(); if (isdigit(c) if (isdigit(c) yylval = c - yylval = c - 0 0 ; ; return DIGIT; return DIGIT; return c; return c; 词法分析返回二元组词法分析返回二元组 由变量由变量yylval传

20、递给传递给Parser在声明部分进行在声明部分进行说明，如说明，如DIGIT2022-4-6编译原理454.9.2 用用Yacc处理二义文法处理二义文法q 采用简单的二义文法： E E + E | E - E | E * E | E / E | ( E ) | - E | numbernumberq 输入一个表达式并回车，显示计算结果。q 也可以输入一个空白行。2022-4-6编译原理46声明部分声明部分%# include # include # define YYSTYPE double /* 将栈定义为double类型 */%token NUMBER%left + %left * / %

21、right UMINUS% 2022-4-6编译原理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-4-6编译原理48支持例程支持例程yylex ( ) int c;while

22、( ( c = getchar ( ) ) = = );if ( ( c = = ) | | (isdigit (c) ) ) ungetc (c, stdin);scanf ( “% lf ”, &yylval);return NUMBER;return c;2022-4-6编译原理49Yacc文件格式中的几个问题文件格式中的几个问题q TOKEN的定义%token NUM %token IDENTq 语法规则与语义动作2022-4-6编译原理50Yacc文件格式中的几个问题文件格式中的几个问题q 为算符指定优先级与结合率%left - + %left * / %left NEG /

23、* negation-unary minus */ %right /* exponentiation */q 二义性及冲突的解决归约/归约冲突：选择Yacc说明中先出现的产生式移进/归约冲突：移近优先q 出错处理2022-4-6编译原理51将将 Lex 与与 Yacc 结合起来结合起来 q 一个程序通常在每次返回一个标记时都要调用 yylex() 函数。只有在文件结束或者出现错误标记时才会终止。 q 一个由 Yacc 生成的解析器调用 yylex() 函数来获得标记。 yylex() 可以由 Lex 来生成或完全由自己来编写。 对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用

24、，每当 Lex 中匹配一个模式时都必须返回一个标记。 因此 Lex 中匹配模式时的动作一般格式为： pattern /* do something*/ return TOKEN_NAME; 2022-4-6编译原理52q 于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的 .y文件时，会生成一个头文件，它对每个标记都有 #define 的定义。 如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件 .lex中的 C 声明段中包括#include “lex.yy.c”。 2022-4-6编译原理53Yacc的错误恢复的错误恢复q 编译器设计者的工作

25、决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。q Yacc把错误产生式当作普通产生式处理2022-4-6编译原理54q 遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析2022-4-6编译原理55包含错误恢复的计算器包含错误恢复的计算器lines : lines expr nprintf ( “%g n”, $2 ) | lines n| /* */| error nprintf ( “重新输入上一行”); yyerrok;2022-4-6编译原理5