实验2 递归下降语法分析

1、编译技术实验(2) 递归下降语法分析周尔强2015年10月expexp: factor: factor| | expexp + factorfactor| | expexp - factorfactor; ;factorfactor: term: term| | factor factor * * term term| | factor factor / term term; ;termterm: : NUMBERNUMBER| | - term term; ;递归下降分析举例Zhou, Erqiang2School of Information and Software Engineerin

2、gexpexp: factor: factor| | expexp + factorfactor| | expexp - factorfactor; ;递归下降分析举例Zhou, Erqiang3School of Information and Software Engineering语言语言：factor +/- factor +/- factor +/- factor +/- factor .factor .程序程序：void void exp() exp() factor(); factor(); whilewhile( tok = + | tok = -)( tok = + | to

3、k = -) advance(); advance(); factor(); factor(); +/- factor +/- factor .+/- factor +/- factor .重复出现的部分重复出现的部分factorfactor: term: term| | factor factor * * term term| | factor factor / term term; ;递归下降分析举例Zhou, Erqiang4School of Information and Software Engineering语言语言：term term * */ term / term * */

4、 term ./ term .程序程序：void void factor()factor() term(); term(); whilewhile( tok = ( tok = * * | tok = /) | tok = /) advance(); advance(); term(); term(); * */ term / term * */ term ./ term .重复出现的部分重复出现的部分termterm: : NUMBERNUMBER| | - term term; ;递归下降分析举例Zhou, Erqiang5School of Information and Softwar

5、e Engineering语言语言：NUMBERNUMBER、 - NUMBER- NUMBER - - NUMBER - - NUMBER、- - - NUMBER - - - NUMBER 程序程序：void void term() term() ifif( tok = NUMBER );( tok = NUMBER ); advance(); advance(); else if else if ( tok = -)( tok = -) advance(); advance(); term(); term(); else else error();error(); 纯粹的语法分析只分析纯

6、粹的语法分析只分析 词法记号序列是否符合语言的文法词法记号序列是否符合语言的文法 如如 -5+20 -5+20* *5-35-3实际的编译器实际的编译器 需要找出词法记号序列的需要找出词法记号序列的结构结构 即语法树即语法树递归下降分析举例Zhou, Erqiang6School of Information and Software Engineeringexpexp: factor: factor| | expexp + factorfactor| | expexp - factorfactor; ;factorfactor: term: term| | factor factor * *

7、 term term| | factor factor / term term; ;termterm: : NUMBERNUMBER| | - term term; ;递归下降文法举例Zhou, Erqiang7School of Information and Software Engineering-5+20*5-3termtermtermtermfactorfactorexptermfactorexpfactorexp递归下降文法举例Zhou, Erqiang8School of Information and Software Engineering-5+20*5-3termtermt

8、ermtermfactorfactorexptermfactorexpfactorexpnull5205-*+3-抽象的语法树抽象的语法树（Abstract Syntax Tree, AST）while while b b 0 0 ifif a b a b a a :=:= a a b b elseelse b b :=:= b b a areturn return a a 抽象语法树Zhou, Erqiang9School of Information and Software Engineering抽象语法树结点设计抽象语法树结点设计 所有树结点统一为所有树结点统一为 一个一个 结构类型结

9、构类型 如何区别结点：赋值语句？选择语句？如何区别结点：赋值语句？选择语句？ 结点内需要结点内需要 用用标志位标志位 结点的最大分支数结点的最大分支数 表达式最多为二元运算，至少表达式最多为二元运算，至少 2 2 个个 结点为树的叶结点结点为树的叶结点 需要保存运算的数值需要保存运算的数值 表达式的抽象语法树Zhou, Erqiang10School of Information and Software Engineering抽象语法树结点设计抽象语法树结点设计 表达式的抽象语法树Zhou, Erqiang11School of Information and Software Engine

10、eringtypedef struct typedef struct _ast _ast astast; ;typedef struct typedef struct _ast _ast * *pastpast; ;struct struct _ast_astint int ivalueivalue; ;charchar* * nodeTypenodeType; ;past past leftleft; ;past past rightright; ;递归下降分析函数递归下降分析函数 表达式的抽象语法树Zhou, Erqiang12School of Information and Softw

11、are Engineeringvoid void factor()factor() term(); term(); whilewhile( tok = ( tok = * * | tok = /) | tok = /) advance(); advance(); term(); term(); past past astFactor()astFactor() past past l = astTerm();l = astTerm();whilewhile(tok = (tok = * * | tok = /) | tok = /) int int oper = tok;oper = tok;a

12、dvanceadvance();();past past r = astTerm();r = astTerm();l = newExpr(oper, l, r);l = newExpr(oper, l, r); return return l;l; 实验任务1. 1. 学习所提供的学习所提供的“表达式文法表达式文法”的递归下降处理的递归下降处理 理解理解 rdlex.lrdlex.l、rdparser.crdparser.c的内容的内容 在在eclipseeclipse中建立工程并调试运行中建立工程并调试运行2. 2. 学习学习rdgram.txtrdgram.txt所提供的文法所提供的文法

13、与词法分析所提供的文法作比较与词法分析所提供的文法作比较Zhou, Erqiang13School of Information and Software Engineering实验任务3. 3. 编写编写rdgramrdgram所提供文法的递归下降程序所提供文法的递归下降程序 (1)(1)编写不生成编写不生成“语法树语法树”的递归下降程序的递归下降程序 rdcheck.c (2) (2)将将rdcheck.c改造为生成语法树的递归下降程序改造为生成语法树的递归下降程序rdparser.c (3) (3)改进改进 词法分析程序、词法分析程序、showAst函数、函数、main函数等，使函数等，

14、使递归下降程序递归下降程序rdparser最终最终从命令行读取从命令行读取要分析的程序要分析的程序test.c, ,分析后调用分析后调用showAst打印该程序的结构。打印该程序的结构。Zhou, Erqiang14School of Information and Software Engineering实验安排要求1. 1. 实验分组与实验一相同，每组只需交一份报告及程序实验分组与实验一相同，每组只需交一份报告及程序2. 2. 所有文件都以所有文件都以 utf-8utf-8 进行统一编码保存！进行统一编码保存！ ( (检查环境为检查环境为LinuxLinux，如出现乱码等错误，扣，如出现乱

15、码等错误，扣 1 1 分！分！) )Zhou, Erqiang15School of Information and Software Engineering实验安排要求3. 3. 提交文件：提交文件： 词法分析程序词法分析程序 rdlex.lrdlex.l 不生成不生成“语法树语法树”的递归下降程序的递归下降程序 rdcheck.crdcheck.c 生成语法树的递归下降程序生成语法树的递归下降程序 rdparser.crdparser.c 实验报告实验报告 递归下降分析法递归下降分析法.docx.docx 未按此规定命名的提交未按此规定命名的提交 扣扣 1 1 分分。Zhou, Erqia

16、ng16School of Information and Software Engineering实验安排要求4. 4. 提交方式提交方式 组长用自己组长用自己QQQQ登录腾讯登录腾讯 微云微云 http:/ 之后以组长之后以组长“学号学号_ _姓氏姓氏_ _实验实验2 2”的格式建立文件夹的格式建立文件夹 ( (如如 2013110101011_2013110101011_周周_ _实验实验2 2） 将所需的文件上传至该文件夹，之后分享该文件夹将所需的文件上传至该文件夹，之后分享该文件夹 切勿切勿设置访问密码，否则设置访问密码，否则视为未提交视为未提交 将分享链接发到将分享链接发到 邮件主

17、题邮件主题 “编译实验编译实验”, 发到其它邮箱发到其它邮箱视为未提交视为未提交Zhou, Erqiang17School of Information and Software Engineering实验安排要求5. 5. 提交截止日期提交截止日期 北京时间北京时间 20152015年年1010月月3131日日23:59:5923:59:59（周六）（周六） 此时间之后此时间之后 再发分享链接再发分享链接 或或 更改文件夹内容更改文件夹内容 将无效将无效编译技术资料编译技术资料http:/ 自己的微云，再浏览下载，不用直接下载自己的微云，再浏览下载，不用直接下载Zhou, Erqiang18

18、School of Information and Software EngineeringZhou, ErqiangTHE ENDQUESTIONS19School of Information and Software Engineeringprogramprogram : external_declaration : external_declaration | | program program external_declarationexternal_declaration ; ;external_declarationexternal_declaration : type decl

19、arator decl_or_stmt : type declarator decl_or_stmt ; ;decl_or_stmtdecl_or_stmt : : statement_list statement_list | | | | , , declarator_list declarator_list ; | | ; ; ;declarator_listdeclarator_list : declarator : declarator | declarator_list | declarator_list , declarator declarator ; ;递归下降分析举例Zhou

20、, Erqiang20School of Information and Software Engineeringintstr_listintstr_list : : NUMBER | STRINGNUMBER | STRING | intstr_list | intstr_list , NUMBERNUMBER | intstr_list , | intstr_list , STRINGSTRING ; ;declaratordeclarator : ID : ID | ID | ID = expr expr | ID | ID ( parameter_list parameter_list

21、 ) ) | ID | ID ( ) | ID | ID expr expr | ID | ID | | ID ID expr expr = = intstr_list intstr_list | ID | ID = = intstr_listintstr_list ; ;parameter_listparameter_list : parameter : parameter | parameter_list | parameter_list , parameter parameter ; ;statementstatement : type declarator_list : type de

22、clarator_list ; | | statement_list statement_list | expr_statement | expr_statement | IF | IF ( ( expr expr ) statement statement | IF | IF ( ( expr expr ) statement ELSE statement statement ELSE statement | WHILE | WHILE ( ( expr expr ) ) statementstatement | RETURN | RETURN ; | RETURN expr | RETUR

23、N expr ; | PRINT | PRINT ; ; | PRINT expr_list | PRINT expr_list ; ; | SCAN id_list | SCAN id_list ; ; ;statement_liststatement_list : statement : statement | statement_list statement | statement_list statement ; ;递归下降分析举例Zhou, Erqiang21School of Information and Software Engineeringparameterparamete

24、r : type : type IDID ; ;typetype : : INTINT | | STRSTR | | VOIDVOID ; ;expr_statementexpr_statement : : ; | expr | expr ; ; ;expr_listexpr_list : expr : expr | expr_list | expr_list , expr expr ; ;id_listid_list : : IDID | id_list | id_list , IDID ; ;mul_exprmul_expr : primary_expr : primary_expr |

25、mul_expr | mul_expr * * primary_expr primary_expr | mul_expr | mul_expr / primary_expr primary_expr | mul_expr | mul_expr % primary_expr primary_expr | | - - primary_expr primary_expr ; ;primary_exprprimary_expr : : ID ( ID ( expr_list expr_list ) | | ID ( )ID ( ) | | ( expr expr ) | | IDID | | NUMB

26、ERNUMBER | | STRINGSTRING | | ID ASSIGN ID ASSIGN exprexpr | | ID =ID = expr expr | | ID ID expr expr | | ID ID expr expr = = expr expr ; ;递归下降分析举例Zhou, Erqiang22School of Information and Software Engineeringexprexpr : cmp_expr : cmp_expr ; ;cmp_exprcmp_expr : add_expr : add_expr | cmp_expr | cmp_ex

27、pr CMP CMP add_expradd_expr ; ;add_expradd_expr : mul_expr : mul_expr | add_expr | add_expr + mul_expr mul_expr | add_expr | add_expr - mul_expr mul_expr ; ;程序在词法分析后的结果是？程序在词法分析后的结果是？enum enum INT INT = 258, = 258, STR, VOID, ID, NUMBER, STRING, PRINT, RETURN, STR, VOID, ID, NUMBER, STRING, PRINT, R

28、ETURN, .INT ID NUMBER = NUMBER , NUMBER , NUMBER , NUMBER INT ID NUMBER = NUMBER , NUMBER , NUMBER , NUMBER 10 10 9 8 7 10 10 9 8 7 INT, ID, NUMBER INT, ID, NUMBER 等为枚举类型定义的值等为枚举类型定义的值 , = 等为符号对应等为符号对应ASCII编码的值编码的值 STR ID ( INT ID ) STR ID = STRING + STRING ; STR ID = STRING + .STR ID ( INT ID ) STR

29、 ID = STRING + STRING ; STR ID = STRING + .递归下降分析举例Zhou, Erqiang23School of Information and Software Engineeringint int array210 = 10,9,8,7;array210 = 10,9,8,7;str str f(int a)f(int a) str str b = b = aaaaaa + + dddddd;str str c = c = cccccc + + bbbb;print print c;c;return return c;c; ;programprogra

30、m = = external_declarationexternal_declaration= = type type declarator declarator decl_or_stmtdecl_or_stmt= = INT INT ID expr = intstr_list ID expr = intstr_list 递归下降分析举例Zhou, Erqiang24School of Information and Software Engineeringint int array210 = 10,9,8,7;array210 = 10,9,8,7;str str f(int a)f(int

31、 a) str str b = b = aaaaaa + + dddddd;str str c = c = cccccc + + bbbb;print print c;c;return return c;c; declaratordeclarator : ID : ID | ID | ID = expr expr | ID | ID ( parameter_list parameter_list ) ) | ID | ID ( ) | ID | ID expr expr | ID | ID | | ID ID expr expr = = intstr_list intstr_list | ID

32、 | ID = = intstr_listintstr_list ; ;decl_or_stmtdecl_or_stmt : : statement_list statement_list | | | | , , declarator_list declarator_list ; | | ; ; ;programprogram = = external_declarationexternal_declaration= = type type declarator declarator decl_or_stmtdecl_or_stmt= = INT INT ID expr = intstr_li

33、st ID expr = intstr_list ; ;expr = cmp_expr = add_expr = mul_expr = expr = cmp_expr = add_expr = mul_expr = primary_exprprimary_expr = = NUMBERNUMBERintstr_list = intstr_list = intstr_listintstr_list , NUMBER , NUMBER intstr_list = intstr_list = intstr_list , NUMBERintstr_list , NUMBER , NUMBER , NU

34、MBERintstr_list = intstr_list = intstr_list , NUMBERintstr_list , NUMBER , NUMBER , NUMBER , NUMBER , NUMBERintstr_list = intstr_list = NUMBERNUMBER , NUMBER , NUMBER , NUMBER , NUMBER , NUMBER , NUMBER= INT ID = INT ID NUMBER NUMBER = NUMBER , NUMBER , NUMBER , NUMBER = NUMBER , NUMBER , NUMBER , N

35、UMBER tokentoken对应的属性对应的属性 10 10 9 8 710 10 9 8 7递归下降分析举例Zhou, Erqiang25School of Information and Software Engineeringint int array210 = 10,9,8,7;array210 = 10,9,8,7;str str f(int a)f(int a) str str b = b = aaaaaa + + dddddd;str str c = c = cccccc + + bbbb;print print c;c;return return c;c; intstr_l

36、istintstr_list : : NUMBER | STRINGNUMBER | STRING | intstr_list | intstr_list , NUMBERNUMBER | intstr_list , | intstr_list , STRINGSTRING ; ;递归下降分析举例Zhou, Erqiang26School of Information and Software Engineeringexternal_declarationexternal_declaration: type declarator decl_or_stmt: type declarator de

37、cl_or_stmt; ;past past external_declaration()external_declaration() past past result = NULL;result = NULL;past past t = type();t = type();past past d = declarator();d = declarator();past past ds = decl_or_stmt();ds = decl_or_stmt();result = newExtDecl(t, d, ds);result = newExtDecl(t, d, ds);return r

38、eturn resultresult; ; 递归下降分析举例Zhou, Erqiang27School of Information and Software Engineeringprogramprogram: external_declaration: external_declaration| program external_declaration| program external_declaration; ;递归程序？递归程序？past past program()program() advance();advance();past past ext = external_decl

39、aration();ext = external_declaration();past past list = list = newListnewList(NULL, ext);(NULL, ext);while( tok )while( tok ) ext = external_declaration();ext = external_declaration();list = list = newListnewList(list, ext);(list, ext); return return listlist; ; parameter_listparameter_list : parame

40、ter : parameter | parameter_list | parameter_list , parameter parameter ; ;past past parameter_list()parameter_list() past past result = newList(NULL, parameter();result = newList(NULL, parameter();while(tok = ,)while(tok = ,) advance();advance();result = newList(result, parameter();result = newList

41、(result, parameter(); return result;return result; programprogram = = program program external_declarationexternal_declaration= = external_declarationexternal_declaration external_declarationexternal_declaration= . = . type type declarator declarator decl_or_stmtdecl_or_stmt= . = . STRSTR ID ( parameter_list )ID ( parameter_list ) statement_list state