实验2-递归下降语法分析ppt课件

编译技术实验(2)递归下降语法分析,周尔强2015年10月,.,exp:factor|exp+factor|exp-factor;factor:term|factor*term|factor/term;term:NUMBER|-term;,递归下降分析举例,Zhou,Erqiang,2,SchoolofInformationandSoftwareEngineering,.,exp:factor|exp+factor|exp-factor;,递归下降分析举例,Zhou,Erqiang,3,SchoolofInformationandSoftwareEngineering,语言：factor+/-factor+/-factor.程序：voidexp()factor();while(tok=+|tok=-)advance();factor();,+/-factor+/-factor.重复出现的部分,.,factor:term|factor*term|factor/term;,递归下降分析举例,Zhou,Erqiang,4,SchoolofInformationandSoftwareEngineering,语言：term*/term*/term.程序：voidfactor()term();while(tok=*|tok=/)advance();term();,*/term*/term.重复出现的部分,.,term:NUMBER|-term;,递归下降分析举例,Zhou,Erqiang,5,SchoolofInformationandSoftwareEngineering,语言：NUMBER、-NUMBER-NUMBER、-NUMBER程序：voidterm()if(tok=NUMBER);advance();elseif(tok=-)advance();term();elseerror();,.,纯粹的语法分析只分析词法记号序列是否符合语言的文法如-5+20*5-3实际的编译器需要找出词法记号序列的结构即语法树,递归下降分析举例,Zhou,Erqiang,6,SchoolofInformationandSoftwareEngineering,.,exp:factor|exp+factor|exp-factor;factor:term|factor*term|factor/term;term:NUMBER|-term;,递归下降文法举例,Zhou,Erqiang,7,SchoolofInformationandSoftwareEngineering,-,5,+,20,*,5,-,3,term,term,term,term,factor,factor,exp,term,factor,exp,factor,exp,.,递归下降文法举例,Zhou,Erqiang,8,SchoolofInformationandSoftwareEngineering,-,5,+,20,*,5,-,3,term,term,term,term,factor,factor,exp,term,factor,exp,factor,exp,null,5,20,5,-,*,+,3,-,抽象的语法树（AbstractSyntaxTree,AST）,.,whileb0ifaba:=abelseb:=bareturna,抽象语法树,Zhou,Erqiang,9,SchoolofInformationandSoftwareEngineering,.,抽象语法树结点设计所有树结点统一为一个结构类型如何区别结点：赋值语句？选择语句？结点内需要用标志位结点的最大分支数表达式最多为二元运算，至少2个结点为树的叶结点需要保存运算的数值,表达式的抽象语法树,Zhou,Erqiang,10,SchoolofInformationandSoftwareEngineering,.,抽象语法树结点设计,表达式的抽象语法树,Zhou,Erqiang,11,SchoolofInformationandSoftwareEngineering,typedefstruct_astast;typedefstruct_ast*past;struct_astintivalue;char*nodeType;pastleft;pastright;,.,递归下降分析函数,表达式的抽象语法树,Zhou,Erqiang,12,SchoolofInformationandSoftwareEngineering,voidfactor()term();while(tok=*|tok=/)advance();term();,pastastFactor()pastl=astTerm();while(tok=*|tok=/)intoper=tok;advance();pastr=astTerm();l=newExpr(oper,l,r);returnl;,.,实验任务,1.学习所提供的“表达式文法”的递归下降处理理解rdlex.l、rdparser.c的内容在eclipse中建立工程并调试运行2.学习rdgram.txt所提供的文法与词法分析所提供的文法作比较,Zhou,Erqiang,13,SchoolofInformationandSoftwareEngineering,.,实验任务,3.编写rdgram所提供文法的递归下降程序(1)编写不生成“语法树”的递归下降程序rdcheck.c(2)将rdcheck.c改造为生成语法树的递归下降程序rdparser.c(3)改进词法分析程序、showAst函数、main函数等，使递归下降程序rdparser最终从命令行读取要分析的程序test.c,分析后调用showAst打印该程序的结构。,Zhou,Erqiang,14,SchoolofInformationandSoftwareEngineering,.,实验安排要求,1.实验分组与实验一相同，每组只需交一份报告及程序2.所有文件都以utf-8进行统一编码保存！(检查环境为Linux，如出现乱码等错误，扣1分！),Zhou,Erqiang,15,SchoolofInformationandSoftwareEngineering,.,实验安排要求,3.提交文件：词法分析程序rdlex.l不生成“语法树”的递归下降程序rdcheck.c生成语法树的递归下降程序rdparser.c实验报告递归下降分析法.docx未按此规定命名的提交扣1分。,Zhou,Erqiang,16,SchoolofInformationandSoftwareEngineering,.,实验安排要求,4.提交方式组长用自己QQ登录腾讯微云,Zhou,Erqiang,17,SchoolofInformationandSoftwareEngineering,.,实验安排要求,5.提交截止日期北京时间2015年10月31日23:59:59（周六）此时间之后再发分享链接或更改文件夹内容将无效编译技术资料,Zhou,Erqiang,18,SchoolofInformationandSoftwareEngineering,.,Zhou,Erqiang,THEENDQUESTIONS,19,SchoolofInformationandSoftwareEngineering,.,program:external_declaration|programexternal_declaration;external_declaration:typedeclaratordecl_or_stmt;decl_or_stmt:statement_list|,declarator_list;|;declarator_list:declarator|declarator_list,declarator;,递归下降分析举例,Zhou,Erqiang,20,SchoolofInformationandSoftwareEngineering,intstr_list:NUMBER|STRING|intstr_list,NUMBER|intstr_list,STRING;declarator:ID|ID=expr|ID(parameter_list)|ID()|IDexpr|ID|IDexpr=intstr_list|ID=intstr_list;parameter_list:parameter|parameter_list,parameter;,.,statement:typedeclarator_list;|statement_list|expr_statement|IF(expr)statement|IF(expr)statementELSEstatement|WHILE(expr)statement|RETURN;|RETURNexpr;|PRINT;|PRINTexpr_list;|SCANid_list;statement_list:statement|statement_liststatement;,递归下降分析举例,Zhou,Erqiang,21,SchoolofInformationandSoftwareEngineering,parameter:typeID;type:INT|STR|VOID;expr_statement:;|expr;expr_list:expr|expr_list,expr;id_list:ID|id_list,ID;,.,mul_expr:primary_expr|mul_expr*primary_expr|mul_expr/primary_expr|mul_expr%primary_expr|-primary_expr;primary_expr:ID(expr_list)|ID()|(expr)|ID|NUMBER|STRING|IDASSIGNexpr|ID=expr|IDexpr|IDexpr=expr;,递归下降分析举例,Zhou,Erqiang,22,SchoolofInformationandSoftwareEngineering,expr:cmp_expr;cmp_expr:add_expr|cmp_exprCMPadd_expr;add_expr:mul_expr|add_expr+mul_expr|add_expr-mul_expr;,.,程序在词法分析后的结果是？enumINT=258,STR,VOID,ID,NUMBER,STRING,PRINT,RETURN,.INTIDNUMBER=NUMBER,NUMBER,NUMBER,NUMBER1010987INT,ID,NUMBER等为枚举类型定义的值,=等为符号对应ASCII编码的值STRID(INTID)STRID=STRING+STRING;STRID=STRING+.,递归下降分析举例,Zhou,Erqiang,23,SchoolofInformationandSoftwareEngineering,intarray210=10,9,8,7;strf(inta)strb=aaa+ddd;strc=ccc+bb;printc;returnc;,.,;,program=external_declaration=typedeclaratordecl_or_stmt=INTIDexpr=intstr_list,递归下降分析举例,Zhou,Erqiang,24,SchoolofInformationandSoftwareEngineering,intarray210=10,9,8,7;strf(inta)strb=aaa+ddd;strc=ccc+bb;printc;returnc;,declarator:ID|ID=expr|ID(parameter_list)|ID()|IDexpr|ID|IDexpr=intstr_list|ID=intstr_list;,decl_or_stmt:statement_list|,declarator_list;|;,.,program=external_declaration=typedeclaratordecl_or_stmt=INTIDexpr=intstr_list;expr=cmp_expr=add_expr=mul_expr=primary_expr=NUMBERintstr_list=intstr_list,NUMBERintstr_list=intstr_list,NUMBER,NUMBERintstr_list=intstr_list,NUMBER,NUMBER,NUMBERintstr_list=NUMBER,NUMBER,NUMBER,NUMBER=INTIDNUMBER=NUMBER,NUMBER,NUMBER,NUMBERtoken对应的属性1010987,递归下降分析举例,Zhou,Erqiang,25,SchoolofInformationandSoftwareEngineering,intarray210=10,9,8,7;strf(inta)strb=aaa+ddd;strc=ccc+bb;printc;returnc;,intstr_list:NUMBER|STRING|intstr_list,NUMBER|intstr_list,STRING;,.,递归下降分析举例,Zhou,Erqiang,26,SchoolofInformationandSoftwareEngineering,external_declaration:typedeclaratordecl_or_stmt;,pastexternal_declaration()pastresult=NULL;pastt=type();pastd=declarator();pastds=decl_or_stmt();result=newExtDecl(t,d,ds);returnresult;,.,递归下降分析举例,Zhou,Erqiang,27,SchoolofInformationandSoftwareEngineering,program:external_declaration|programexternal_declaration;递归程序？,pastprogram()advance();pastext=external_declaration();pastlist=newList(NULL,ext);while(tok)ext=external_declaration();list=newList(list,ext);returnlist;,parameter_list:parameter|parameter_list,parameter;,pastparameter_list()pastresult=newList(NULL,parameter();while(tok=,)advance();result=newList(result,parameter();returnresult;,.,program=programexternal_declaration=external_declarationexternal_declaration=.typedeclaratorde