第四章语法分析5PPT资料.ppt
- 文档编号:8694791
- 上传时间:2023-05-13
- 格式:PPT
- 页数:72
- 大小:1.11MB
第四章语法分析5PPT资料.ppt
《第四章语法分析5PPT资料.ppt》由会员分享,可在线阅读,更多相关《第四章语法分析5PPT资料.ppt(72页珍藏版)》请在冰点文库上搜索。
假设ax能推出by,那么,B,b对有效,b是从能推出的开始符号,或当可空时,b就是a。
bFIRST(a)。
2023/5/13,编译原理,10,LALR分析表的构造,1.先构造文法的LR
(1)项目集族C=I0,I1,In;
2.再合并C中的同心集,得到C=J0,J1,Jm;
由此得到的识别活前缀的DFA实际上和LR(0)项目的DFA相同,但带上了搜索符,2023/5/13,编译原理,11,w,A,w,A,LL分析方法和LR分析方法的比较,A,LL
(1)向前看下一个输入根据FIRST()确定使用哪条产生式推导;
而LR
(1)是在识别出整个后,再往前看1个符号,然后确定使用哪条产生式归约。
S,S,2023/5/13,编译原理,12,在下面的推导中,最后一步用的是A,LL
(1)决定用该产生式的位置是First(),LR
(1)决定用该产生式的位置,LL分析方法和LR分析方法的比较,2023/5/13,编译原理,13,非LR结构,例:
L=wwRwa,b*SaSabSb,2023/5/13,编译原理,14,LL分析方法和LR分析方法的比较,LL(k)文法都是LR(k)文法。
LR文法比LL文法描述的语言更多。
2023/5/13,编译原理,15,LR分析方法和LL分析方法的比较,2023/5/13,编译原理,16,LR分析方法和LL分析方法的比较,2023/5/13,编译原理,17,LR分析方法和LL分析方法的比较,2023/5/13,编译原理,18,48二义文法的应用,任何二义性的文法都不是LR文法。
二义文法的特点:
简洁、自然例如,表达式文法二义文法:
EE+E|E*E|(E)|id非二义的文法:
EE+T|TTT*F|FF(E)|id语法分析的效率高(基于消除二义后得到的分析表),2023/5/13,编译原理,19,4.8.1使用文法以外信息解决分析动作冲突,优先级和结合规则例:
规定:
*优先级高于+,两者都是左结合EE+E|E*E|(E)|id,2023/5/13,编译原理,20,拓广文法的LR(0)项目集,I0:
EEEE+EEE*EE(E)EidI1:
EEEE+EEE*E,I2:
E(E)EE+EEE*EE(E)EidI3:
EidI4:
EE+EEE+EEE*EE(E)Eid,I5:
EE*EEE+EEE*EE(E)EidI6:
E(E)EE+EEE*E,I7:
EE+EEE+EEE*EI8:
EE*EEE+EEE*EI9:
E(E),FOLLOW(E)=$,+,*,)移进-归约冲突,2023/5/13,编译原理,21,2023/5/13,编译原理,22,SLR分析表(存在冲突),2023/5/13,编译原理,23,使用文法以外信息来解决分析动作冲突,考虑id+id+id和id+id*id形成格局栈输入0E1+4E7*id$面临+,归约面临*,移进面临)和$,归约,I7:
EE+EEE+EEE*E,2023/5/13,编译原理,24,4.8.2悬空else的二义性,SSSiSeS|iS|a,2023/5/13,编译原理,25,I0:
SSSiSeSSiSSaI1:
SSI2:
SiSeSSiSSiSeSSiSSa,I3:
SaI4:
SiSeSSiSI5:
SiSeSSiSeSSiSSaI6:
SiSeS,FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作,2023/5/13,编译原理,26,2023/5/13,编译原理,27,I0:
SiSeS,FOLLOW(S)=i,e移进-归约冲突根据最近匹配原则选择移进动作,2023/5/13,编译原理,28,根据最近匹配原则选择移进动作,图4-49LR分析表,2023/5/13,编译原理,29,处理iiaea的语法分析动作,2023/5/13,编译原理,30,4.8.3LR分析的错误恢复,LR分析器在什么情况下发现错误访问动作表时若遇到出错条目,就检测到一个语法错误访问转移表时不会遇到出错条目若发现当前已扫描的输入不可能存在正确的后续,LR语法分析器立刻报错(决不做任何无效归约)SLR和LALR分析可能会在报错之前执行几步归约,但决不会把不正确的后继移进栈,2023/5/13,编译原理,31,紧急方式错误恢复(panicmode),退栈,直至出现状态s,它有预先确定的A的转移;
抛弃若干个输入符号,直至找到a,它是A的合法后继;
再把A和状态gotos,A压进栈,恢复正常分析。
2023/5/13,编译原理,32,栈,.a.,A,发现错误,s:
CAAb.,CA.,A,Ab.,b,2023/5/13,编译原理,33,栈,.a.,A,发现错误,s,goto(s,A),.,栈,.a.,A,继续分析,2023/5/13,编译原理,34,例4.49EE+E|E*E|(E)|id,e1:
id(状态)3进栈,缺少运算对象e2:
从输入删除“)”,右括号不匹配e3:
+(状态)4进栈,缺少操作符e4:
)(状态)9进栈,缺少右括号,2023/5/13,编译原理,35,输入id+)的分析和出错恢复,分析栈输入串动作和错误信息0id+)$移进0id3+)$归约,Eid0E1+)$移进0E1+4)$e2右括号不匹配,从输入删除“)”0E1+4$e1缺少运算对象,假想的id进栈0E1+4id3$归约,Eid0E1+4E7$归约,EE+E0E1$accept,2023/5/13,编译原理,36,4.9语法分析器的生成器,Yacc:
yetanothercompiler-compiler基于LALR
(1)的语法分析程序的生成器Yacc的GNU版叫做Bison。
Yacc是一种工具,根据编程语言的语法生成针对该语言的Yacc语法分析器。
它用巴科斯范式(BNF,BackusNaurForm)来书写。
2023/5/13,编译原理,37,491分析器的生成器Yacc,按照惯例,Yacc源文件的后缀为y。
调用Yacc编译器:
yacc,2023/5/13,编译原理,38,语法规则(.y文件),2023/5/13,编译原理,39,用Yacc创建语法分析器包括四个步骤:
通过在语法文件上运行Yacc生成一个解析器。
说明语法:
编写一个y的语法文件(同时说明C在这里要进行的动作)。
写一个词法分析器来处理输入并将标记传递给解析器。
这可以使用Lex来完成。
编写一个函数,通过调用yyparse()来开始解析。
编写错误处理例程(如yyerror())。
编译Yacc生成的代码以及其他相关的源文件。
将目标文件链接到适当的可执行解析器库。
2023/5/13,编译原理,40,Yacc源程序的组成部分,%C声明%对词法单元的声明%文法规则及翻译规则%用C语言编写的辅助性支持例程,声明部分,2023/5/13,编译原理,41,翻译规则,产生式1|2|n写成:
1语义动作|2语义动作|n语义动作;
2023/5/13,编译原理,42,带单引号的单个字符终结符语义动作:
$表示左部非终结符的属性值,$i表示右部第i个文法符号关联的属性值。
默认动作是$=$1;
expr:
expr+term$=$1+$3;
|term;
2023/5/13,编译原理,43,例4.50台式计算器,EE+T|TTT*F|FF(E)|digit读入一个算术表达式,计算它的值并输出。
2023/5/13,编译原理,44,%#include%tokenDIGIT%line:
exprnprintf(“%dn”,$1);
expr:
term:
term*factor$=$1*$3;
|factor;
factor:
(expr)$=$2;
|DIGIT;
%,2023/5/13,编译原理,45,yylex()intc;
c=getchar();
if(isdigit(c)yylval=c-0;
returnDIGIT;
returnc;
词法分析返回二元组,由变量yylval传递给Parser,在声明部分进行说明,如DIGIT,2023/5/13,编译原理,46,4.9.2用Yacc处理二义文法,采用简单的二义文法:
EE+E|E-E|E*E|E/E|(E)|-E|number输入一个表达式并回车,显示计算结果。
也可以输入一个空白行。
2023/5/13,编译原理,47,声明部分,%#include#include#defineYYSTYPEdouble/*将栈定义为double类型*/%tokenNUMBER%left+%left*/%rightUMINUS%,2023/5/13,编译原理,48,翻译规则,lines:
linesexprnprintf(“%gn”,$2)|linesn|/*/;
expr+expr$=$1+$3;
|exprexpr$=$1$3;
|expr*expr$=$1*$3;
|expr/expr$=$1/$3;
|(expr)$=$2;
|expr%precUMINUS$=$2;
|NUMBER;
%,2023/5/13,编译原理,49,支持例程,yylex()intc;
while(c=getchar()=);
if(c=)|(isdigit(c)ungetc(c,stdin);
scanf(“%lf”,2023/5/13,编译原理,50,Yacc文件格式中的几个问题,TOKEN的定义%tokenNUM%tokenIDENT语法规则与语义动作,2023/5/13,编译原理,51,Yacc文件格式中的几个问题,为算符指定优先级与结合率%left-+%left*/%leftNEG/*negation-unaryminus*/%right/*exponentiation*/二义性及冲突的解决归约/归约冲突:
选择Yacc说明中先出现的产生式移进/归约冲突:
移近优先出错处理,2023/5/13,编译原理,52,将Lex与Yacc结合起来,一个程序通常在每次返回一个标记时都要调用yylex()函数。
只有在文件结束或者出现错误标记时才会终止。
一个由Yacc生成的解析器调用yylex()函数来获得标记。
yylex()可以由Lex来生成或完全由自己来编写。
对于由Lex生成的lexer来说,要和Yacc结合使用,每当Lex中匹配一个模式时都必须返回一个标记。
因此Lex中匹配模式时的动作一般格式为:
pattern/*dosomething*/returnTOKEN_NAME;
2023/5/13,编译原理,53,于是Yacc就会获得返回的标记。
当Yacc编译一个带有_d标记的.y文件时,会生成一个头文件,它对每个标记都有#define的定义。
如果Lex和Yacc一起使用的话,头文件必须在相应的Lex文件.lex中的C声明段中包括#include“lex.yy.c”。
2023/5/13,编译原理,54,Yacc的错误恢复,编译器设计者的工作决定哪些“主要的”非终符将有错误恢复与它们相关联。
加入Aerror的错误产生式,其中A是主要非终结符,是文法符号串。
为这样的产生式配上语义动作。
Yacc把错误产生式当作普通产生式处理,2023/5/13,编译原理,55,遇到语法错误时从栈中弹出状态,直到发现栈顶状态的项目集包含形为Aerror的项目为止把虚构的终结符error“移进”栈忽略若干输入符号,直至找到,把移进栈把error归约为A,恢复正常分析,2023/5/13,编译原理,56,包含错误恢复的计算器,lines:
linesexprnprintf(“%gn”,$2)|linesn|/*/|errornprintf(“重新输入上一行”);
yyerrok;
2023/5/13,编译原理,57,Flex&
Bison的使用,Flex.exeBison.exe,2023/5/13,编译原理,58,步骤1,点击“开始”,在“开始”菜单中选择“运行”,2023/5/13,编译原理,59,步骤2,在弹出的对话框中敲入cmd,启动DOS窗口,2023/5/13,编译原理,60,步骤3,在DOS窗口中把当前目录切换到存放bison和flex的目录(例中为d:
bison),2023/5/13,编译原理,61,步骤4,在bison目录中建立一个子目录来放置相关的文件(例中为example),2023/5/13,编译原理,62,步骤5,用文本编辑器编辑相应的bison和flex文件myyacc.y和mylex.l(注意:
这两个文件名不要变),2023/5/13,编译原理,63,步骤6,运行bison生成myyacc.tab.c和myyacc.tab.h文件,2023/5/13,编译原理,64,步骤7,运行flex生成lex.yy.c文件,2023/5/13,编译原理,65,步骤8,在这个目录中再编写一个C文件example.c(具体见所给的例子),2023/5/13,编译原理,66,步骤9,双击example.c文件用VC+打开这个文件,然后编译这个文件,2023/5/13,编译原理,67,步骤10,这时候会弹出一个对话框问你是否要建立一个缺省的项目工作空间,选择“是”,2023/5/13,编译原理,68,VC+会自动建立一个工程项目,并编译刚才的C文件,2023/5/13,编译原理,69,步骤11,点击窗口左侧的“FileView”切换到文件视图,将bison和flex生成的三个文件加入工程,2023/5/13,编译原理,70,步骤12,再编译并链接生成可执行文件,2023/5/13,编译原理,71,成功后生成example.exe,2023/5/13,编译原理,72,步骤13,在当前目录的debug子目录中建立一个名为exprTest.txt的文本文件来测试,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 语法分析
![提示](https://static.bingdoc.com/images/bang_tan.gif)