语法分析5学习.pptx

《语法分析5学习.pptx》由会员分享，可在线阅读，更多相关《语法分析5学习.pptx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/261LR(0)项目在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少。A XYZ由X推导出的子串已经分析过，X出现在栈中，下一步希望看到YZ推导出的子串。第1页/共71页2023/3/262闭包运算closure若项目集I中有项目A B，且有产生式B ，则下一步希望看到由B推导出的子串，那么等同于希望看到，因此将项目B 加入 closure(I)第2页/共71页2023/3/263有效项目有效项目：如果存在规范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。代表某一时刻，栈中的内容是1（活前缀）。一个活前缀的有效项目集就是从DFA的初态出

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

3、目A,a对活前缀有效，如果存在着推导S*rm Aw rm w，其中：1.=；2.a是w的第一个符号，或者w为且a是$。第6页/共71页2023/3/267构造有效的LR(1)项目集项目A B,a对活前缀有效，必定存在S*rm Aax rm Bax，其中=。假设ax能推出by，那么，B,b对有效，b是从 能推出的开始符号，或当 可空时，b就是a。bFIRST(a)。第7页/共71页2023/3/268LALR分析表的构造1.先构造文法的LR(1)项目集族C=I0,I1,In；2.再合并C中的同心集，得到C=J0,J1,Jm；由此得到的识别活前缀的DFA实际上和LR(0)项目的DFA相同，但带上了

4、搜索符第8页/共71页2023/3/269wAwALL分析方法和LR分析方法的比较A ，LL(1)向前看下一个输入根据FIRST()确定使用哪条产生式推导；而LR(1)是在识别出整个后，再往前看1个符号，然后确定使用哪条产生式归约。SS第9页/共71页2023/3/2610在下面的推导中，最后一步用的是ALL(1)决定用该产生式的位置是First()LR(1)决定用该产生式的位置LL分析方法和LR分析方法的比较第10页/共71页2023/3/2611非LR结构例：L=wwR wa,b*S aSa bSb 第11页/共71页2023/3/2612LL分析方法和LR分析方法的比较LL(k)文法都是

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

6、 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 LR分析方法和LL分析方法的比较第14页/共71页2023/3/2615LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 不会将出错点后的符号移入分析栈 和LR一样，不会读过出错点而不报错 LR分析方法和LL分析方法的比较第15页/共71页2023/3/261648 二义文法的应用任何二义性的文法都不是LR文法。二义文法的特点：简洁、自然例如，表达式文法二义文法：E E+E|E*E|(E)|id非二义的文法：E E+T|TT T*F|FF (E)|id语法

7、分析的效率高（基于消除二义后得到的分析表）第16页/共71页2023/3/26174.8.1 使用文法以外信息解决分析动作冲突优先级和结合规则例：规定：*优先级高于+，两者都是左结合E E+E|E*E|(E)|id第17页/共71页2023/3/2618拓广文法的LR(0)项目集I0:EEE E+EE E*EE(E)E idI1:EEE E+EE E*EI2:E(E)E E+EE E*EE(E)E idI3:E idI4:E E+EE E+EE E*EE(E)E idI5:EE*EEE+EEE*EE(E)EidI6:E(E)EE+EEE*EI7:EE+EEE+EEE*EI8:EE*EEE+EE

8、E*EI9:E(E)FOLLOW(E)=$,+,*,)移进-归约冲突第18页/共71页2023/3/2619第19页/共71页2023/3/2620SLR分析表（存在冲突）第20页/共71页2023/3/2621使用文法以外信息来解决分析动作冲突考虑id+id+id 和id+id*id 形成格局栈输入0E1+4E7*id$面临+，归约面临*，移进面临)和$，归约I7:EE+EEE+EEE*E第21页/共71页2023/3/26224.8.2 悬空else的二义性S SS iSeS|iS|a第22页/共71页2023/3/2623I0:SSS iSeSS iSS aI1:SSI2:SiSeS S

9、iSS iSeSS iS SaI3:SaI4:S iS eSS iS I5:SiSe S S iSeSS iS SaI6:SiSeS FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作第23页/共71页2023/3/2624第24页/共71页2023/3/2625I0:SSS iSeSS iSS aI1:SSI2:SiSeS SiSS iSeSS iS SaI3:SaI4:S iS eSS iS I5:SiSe S S iSeSS iS SaI6:SiSeS FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作第25页/共71页2023/3/2626根据最近匹

10、配原则选择移进动作 图4-49 LR分析表第26页/共71页2023/3/2627处理iiaea的语法分析动作第27页/共71页2023/3/26284.8.3 LR分析的错误恢复LR分析器在什么情况下发现错误访问动作表时若遇到出错条目，就检测到一个语法错误访问转移表时不会遇到出错条目若发现当前已扫描的输入不可能存在正确的后续，LR语法分析器立刻报错（决不做任何无效归约）SLR和LALR分析可能会在报错之前执行几步归约，但决不会把不正确的后继移进栈第28页/共71页2023/3/2629紧急方式错误恢复（panic mode）退栈，直至出现状态s,它有预先确定的A的转移；抛弃若干个输入符号，直

11、至找到a,它是A的合法后继；再把A和状态gotos,A压进栈，恢复正常分析。第29页/共71页2023/3/2630s.栈.a.A发现错误s:C AA b.C A.AAb.b第30页/共71页2023/3/2631s.栈.a.A发现错误sgoto(s,A).栈.a.A继续分析第31页/共71页2023/3/2632例4.49 E E+E|E*E|(E)|ide1:id(状态)3进栈，缺少运算对象e2:从输入删除“)”，右括号不匹配e3:+(状态)4进栈，缺少操作符e4:)(状态)9进栈，缺少右括号第32页/共71页2023/3/2633输入id+)的分析和出错恢复分析栈输入串动作和错误信息0i

12、d+)$移进0id3+)$归约,Eid0E1+)$移进0E1+4)$e2右括号不匹配，从输入删除“)”0E1+4$e1缺少运算对象，假想的id进栈0E1+4id3$归约,Eid0E1+4E7$归约,EE+E0E1$accept第33页/共71页2023/3/26344.9 语法分析器的生成器Yacc：yet another compiler-compiler基于LALR(1)的语法分析程序的生成器Yacc 的 GNU 版叫做 Bison。Yacc是一种工具，根据编程语言的语法生成针对该语言的 Yacc 语法分析器。它用巴科斯范式(BNF,Backus Naur Form)来书写。第34页/共7

13、1页2023/3/2635491 分析器的生成器Yacc 按照惯例，Yacc 源文件的后缀为 y。调用 Yacc 编译器：yacc Yacc编译器Yacc源程序translateyytabcC编译器ytabcaoutaout输入输出第35页/共71页2023/3/2636语法规则(.y文件)yyparse()YaccLex词法规则(.l文件)yylex()输出第36页/共71页2023/3/2637用 Yacc 创建语法分析器包括四个步骤：通过在语法文件上运行 Yacc 生成一个解析器。说明语法：编写一个 y 的语法文件（同时说明 C 在这里要进行的动作）。写一个词法分析器来处理输入并将标记传

14、递给解析器。这可以使用 Lex 来完成。编写一个函数，通过调用 yyparse()来开始解析。编写错误处理例程（如 yyerror()）。编译 Yacc 生成的代码以及其他相关的源文件。将目标文件链接到适当的可执行解析器库。第37页/共71页2023/3/2638Yacc源程序的组成部分%C声明%对词法单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程声明部分第38页/共71页2023/3/2639翻译规则产生式 1|2|n写成：1 语义动作|2 语义动作|n 语义动作；第39页/共71页2023/3/2640带单引号的单个字符终结符语义动作：$表示左部非终结符的属性值，$i表示右部

15、第i个文法符号关联的属性值。默认动作是$=$1;expr:expr+term$=$1+$3;|term ;第40页/共71页2023/3/2641例4.50 台式计算器 E E+T|T T T*F|F F (E)|digit读入一个算术表达式，计算它的值并输出。第41页/共71页2023/3/2642%#include%token DIGIT%line:exprn printf(“%dn”,$1);expr:expr+term$=$1+$3;|term ;term:term*factor$=$1*$3;|factor ;factor:(expr)$=$2;|DIGIT ;%第42页/共71页2

16、023/3/2643yylex()int c;c=getchar();if(isdigit(c)yylval=c-0;return DIGIT;return c;词法分析返回二元组 由变量yylval传递给Parser在声明部分进行说明，如DIGIT第43页/共71页2023/3/26444.9.2 用Yacc处理二义文法采用简单的二义文法：E E+E|E-E|E*E|E/E|(E)|-E|number输入一个表达式并回车，显示计算结果。也可以输入一个空白行。第44页/共71页2023/3/2645声明部分%#include#include#define YYSTYPE double /*将栈

17、定义为double类型*/%token NUMBER%left +%left */%right UMINUS%第45页/共71页2023/3/2646翻译规则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;%第46页/共71页2023/3/2647支持例程yylex()int c;while(c=getchar()

18、=);if(c=)|(isdigit(c)ungetc(c,stdin);scanf(“%lf”,&yylval);return NUMBER;return c;第47页/共71页2023/3/2648Yacc文件格式中的几个问题TOKEN的定义%token NUM%token IDENT语法规则与语义动作第48页/共71页2023/3/2649Yacc文件格式中的几个问题为算符指定优先级与结合率%left -+%left */%left NEG /*negation-unary minus*/%right /*exponentiation */二义性及冲突的解决归约/归约冲突：选择Yacc说

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

20、50页/共71页2023/3/2651于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的.y文件时，会生成一个头文件，它对每个标记都有#define 的定义。如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件.lex中的 C 声明段中包括#include“lex.yy.c”。第51页/共71页2023/3/2652Yacc的错误恢复编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。加入A error 的错误产生式，其中A是主要非终结符，是文法符号串。为这样的产生式配上语义动作。Yacc把错误产生式当作普通产生式处理第52页/共

21、71页2023/3/2653遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈忽略若干输入符号，直至找到，把移进栈把error 归约为A，恢复正常分析第53页/共71页2023/3/2654包含错误恢复的计算器lines:lines expr nprintf(“%g n”,$2)|lines n|/*/|error n printf(“重新输入上一行”);yyerrok;第54页/共71页2023/3/2655Flex&Bison的使用Flex.exeBison.exe第55页/共71页2023/3/2656步骤1点击“开

22、始”，在“开始”菜单中选择“运行”第56页/共71页2023/3/2657步骤2在弹出的对话框中敲入cmd，启动DOS窗口第57页/共71页2023/3/2658步骤3在DOS窗口中把当前目录切换到存放bison和flex的目录（例中为d:bison）第58页/共71页2023/3/2659步骤4在bison目录中建立一个子目录来放置相关的文件（例中为example）第59页/共71页2023/3/2660步骤5用文本编辑器编辑相应的bison和flex文件myyacc.y和mylex.l（注意：这两个文件名不要变）第60页/共71页2023/3/2661步骤6运行bison生成myyacc.

23、tab.c和myyacc.tab.h文件第61页/共71页2023/3/2662步骤7运行flex生成lex.yy.c文件第62页/共71页2023/3/2663步骤8在这个目录中再编写一个C文件example.c（具体见所给的例子）第63页/共71页2023/3/2664步骤9双击example.c文件用VC+打开这个文件，然后编译这个文件第64页/共71页2023/3/2665步骤10这时候会弹出一个对话框问你是否要建立一个缺省的项目工作空间，选择“是”第65页/共71页2023/3/2666VC+会自动建立一个工程项目，并编译刚才的C文件第66页/共71页2023/3/2667步骤11点击窗口左侧的“FileView”切换到文件视图，将bison和flex生成的三个文件加入工程第67页/共71页2023/3/2668步骤12再编译并链接生成可执行文件第68页/共71页2023/3/2669成功后生成example.exe第69页/共71页2023/3/2670步骤13在当前目录的debug子目录中建立一个名为exprTest.txt的文本文件来测试第70页/共71页2023/3/26编译原理71感谢您的观看！第71页/共71页