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

资源描述

《第四章--语法分析(5)课件》由会员分享，可在线阅读，更多相关《第四章--语法分析(5)课件（72页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

8、) | id7/29/202419编译原理拓广文法的拓广文法的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) = $,+,*,)移进移进-归约冲突归约冲突7/29/202420编

9、译原理7/29/202421编译原理SLR分析表（存在冲突）分析表（存在冲突）7/29/202422编译原理使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突考虑考虑id + id + id 和和id + id * * id 形成格局形成格局栈栈输入输入0E1+4E7*id$面临+，归约面临*，移进面临 ) 和$，归约I7: EE+E EE+E EE*E7/29/202423编译原理4.8.2 悬空悬空else的二义性的二义性S SS iSeS | iS | a7/29/202424编译原理I0: 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移进-归约冲突根据最近匹配原则选择移进动作7/29/202425编译原理7/29/202426编译原理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移进-归约

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

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

13、ide1: id(状态)3进栈，缺少运算对象e2:从输入删除“)”，右括号不匹配e3:+(状态)4进栈，缺少操作符e4: )(状态)9进栈，缺少右括号7/29/202434编译原理输入id+)的分析和出错恢复分析栈输入串动作和错误信息 0 id+)$ 移进 0id3 +)$ 归约, E id 0E1 +)$ 移进 0E1+4 )$ e2右括号不匹配，从输入删除“)” 0E1+4 $ e1缺少运算对象，假想的id进栈 0E1+4id3 $ 归约, E id 0E1+4E7 $归约, E E+E 0E1 $accept7/29/202435编译原理4.9 语法分析器的生成器语法分析器的生成器q

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

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

16、q将目标文件链接到适当的可执行解析器库。7/29/202439编译原理Yacc源程序的组成部分源程序的组成部分%C声明%对词法单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程声明部分7/29/202440编译原理翻译规则翻译规则q产生式 1| 2 | |nq写成：：1 语义动作| 2 语义动作| | n 语义动作；7/29/202441编译原理q带单引号的单个字符终结符q语义动作：$表示左部非终结符的属性值，$i表示右部第i个文法符号关联的属性值。默认动作是$ =$1;exprexpr : : exprexpr + + term term $ = $1 + $3; $ = $1

18、 ; ;term:termterm:term * * factor $=$1*$3;factor $=$1*$3; | factor | factor ; ;factor:factor: ( ( exprexpr ) ) $=$2; $=$2; | DIGIT | DIGIT ; ;%7/29/202444编译原理yylexyylex()() intint c; c; c=c=getchargetchar();(); if (if (isdigit(cisdigit(c) ) yylvalyylval = c - = c - 0 0 ; ; return DIGIT; return DIGIT

19、; return c; return c; 词法分析返回二元组词法分析返回二元组由变量由变量yylval传递给传递给Parser在声明部分进行在声明部分进行说明，如说明，如DIGIT7/29/202445编译原理4.9.2 用用Yacc处理二义文法处理二义文法q采用简单的二义文法： E E + E | E - E | E * E | E / E | ( E ) | - E | numbernumberq输入一个表达式并回车，显示计算结果。q也可以输入一个空白行。7/29/202446编译原理声明部分声明部分%# include # include # define YYSTYPE doubl

20、e /* 将栈定义为double类型 */%token NUMBER%left + %left * / %right UMINUS% 7/29/202447编译原理翻译规则翻译规则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;

21、| NUMBER;%7/29/202448编译原理支持例程支持例程yylex ( ) int c;while ( ( c = getchar ( ) ) = = );if ( ( c = = ) | | (isdigit (c) ) ) ungetc (c, stdin);scanf ( “% lf ”, &yylval);return NUMBER;return c;7/29/202449编译原理Yacc文件格式中的几个问题文件格式中的几个问题qTOKEN的定义%token NUM %token IDENTq语法规则与语义动作7/29/202450编译原理Yacc文件格式中的几个问题文件格式

22、中的几个问题q为算符指定优先级与结合率%left - + %left * / %left NEG /* negation-unary minus */ %right /* exponentiation */q二义性及冲突的解决归约/归约冲突：选择Yacc说明中先出现的产生式移进/归约冲突：移近优先q出错处理7/29/202451编译原理将将 Lex 与与 Yacc 结合起来结合起来 q一个程序通常在每次返回一个标记时都要调用 yylex() 函数。只有在文件结束或者出现错误标记时才会终止。 q一个由 Yacc 生成的解析器调用 yylex() 函数来获得标记。 yylex() 可以由 Lex

23、来生成或完全由自己来编写。对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。因此 Lex 中匹配模式时的动作一般格式为： pattern /* do something*/ return TOKEN_NAME; 7/29/202452编译原理q于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的 .y文件时，会生成一个头文件，它对每个标记都有 #define 的定义。如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件 .lex中的 C 声明段中包括#include “lex

24、.yy.c”。 7/29/202453编译原理Yacc的错误恢复的错误恢复q编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。qYacc把错误产生式当作普通产生式处理7/29/202454编译原理q遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析7/29/202455编译原理包含错误恢复的计算器包含错误恢复的计算器lines : lin

25、es expr nprintf ( “%g n”, $2 ) | lines n| /* */| error nprintf ( “重新输入上一行”); yyerrok;7/29/202456编译原理Flex & Bison的使用的使用qFlex.exeqBison.exe7/29/202457编译原理步骤步骤1q点击“开始”，在“开始”菜单中选择“运行”7/29/202458编译原理步骤步骤2q在弹出的对话框中敲入cmd，启动DOS窗口7/29/202459编译原理步骤步骤3q在DOS窗口中把当前目录切换到存放bison和flex的目录（例中为d:bison）7/29/202460编译原理步

26、骤步骤4q在bison目录中建立一个子目录来放置相关的文件（例中为example）7/29/202461编译原理步骤步骤5q用文本编辑器编辑相应的bison和flex文件myyacc.y和mylex.l（注意：这两个文件名不要变）7/29/202462编译原理步骤步骤6q运行bison生成myyacc.tab.c和myyacc.tab.h文件7/29/202463编译原理步骤步骤7q运行flex生成lex.yy.c文件7/29/202464编译原理步骤步骤8q在这个目录中再编写一个C文件example.c（具体见所给的例子）7/29/202465编译原理步骤步骤9q双击example.c文件用

27、VC+打开这个文件，然后编译这个文件7/29/202466编译原理步骤步骤10q这时候会弹出一个对话框问你是否要建立一个缺省的项目工作空间，选择“是”7/29/202467编译原理qVC+会自动建立一个工程项目，并编译刚才的C文件7/29/202468编译原理步骤步骤11q点击窗口左侧的“FileView”切换到文件视图，将bison和flex生成的三个文件加入工程7/29/202469编译原理步骤步骤12q再编译并链接生成可执行文件7/29/202470编译原理q成功后生成example.exe7/29/202471编译原理步骤步骤13q在当前目录的debugdebug子目录中建立一个名为exprTest.txtexprTest.txt的文本文件来测试7/29/202472编译原理

展开阅读全文

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

最新文档