编译技术实验 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 whileb 0ifa ba a belseb b areturna 抽象语法树 Zhou Erqiang 9 SchoolofInformationandSoftwareEngineering 抽象语法树结点设计所有树结点统一为一个结构类型如何区别结点 赋值语句 选择语句 结点内需要用标志位结点的最大分支数表达式最多为二元运算 至少2个结点为树的叶结点需要保存运算的数值 表达式的抽象语法树 Zhou Erqiang 10 SchoolofInformationandSoftwareEngineering 抽象语法树结点设计 表达式的抽象语法树 Zhou Erqiang 11 SchoolofInformationandSoftwareEngineering typedefstruct astast typedefstruct ast past struct ast intivalue 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 ID expr ID ID expr 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 ID expr ID expr 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 程序在词法分析后的结果是 enum INT 258 STR VOID ID NUMBER STRING PRINT RETURN INTID NUMBER NUMBER NUMBER NUMBER NUMBER 1010987INT ID NUMBER等为枚举类型定义的值 等为符号对应ASCII编码的值STRID INTID STRID STRING STRING STRID STRING 递归下降分析举例 Zhou Erqiang 23 SchoolofInformationandSoftwareEngineering intarray2 10 10 9 8 7 strf inta strb aaa ddd strc ccc bb printc returnc program external declaration typedeclaratordecl or stmt INTID expr intstr list 递归下降分析举例 Zhou Erqiang 24 SchoolofInformationandSoftwareEngineering intarray2 10 10 9 8 7 strf inta strb aaa ddd strc ccc bb printc returnc declarator ID ID expr ID parameter list ID ID expr ID ID expr intstr list ID intstr list decl or stmt statement list declarator list program external declaration typedeclaratordecl or stmt INTID expr intstr list expr cmp expr add expr mul expr primary expr NUMBERintstr list intstr list N