實(shí)驗(yàn)2 遞歸下降語法分析

1、編譯技術(shù)實(shí)驗(yàn)(2) 遞歸下降語法分析周爾強(qiáng)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 Engine

2、eringexpexp: 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

3、= + | tok = -) advance(); advance(); factor(); factor(); +/- factor +/- factor .+/- factor +/- factor .重復(fù)出現(xiàn)的部分重復(fù)出現(xiàn)的部分factorfactor: term: term| | factor factor * * term term| | factor factor / term term; ;遞歸下降分析舉例Zhou, Erqiang4School of Information and Software Engineering語言語言：term term * */ term / t

4、erm * */ term ./ term .程序程序：void void factor()factor() term(); term(); whilewhile( tok = ( tok = * * | tok = /) | tok = /) advance(); advance(); term(); term(); * */ term / term * */ term ./ term .重復(fù)出現(xiàn)的部分重復(fù)出現(xiàn)的部分termterm: : NUMBERNUMBER| | - term term; ;遞歸下降分析舉例Zhou, Erqiang5School of Information and

5、 Software 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、語法分析只分析純粹的語法分析只分析 詞法記號(hào)序列是否符合語言的文法詞法記號(hào)序列是否符合語言的文法 如如 -5+20 -5+20* *5-35-3實(shí)際的編譯器實(shí)際的編譯器 需要找出詞法記號(hào)序列的需要找出詞法記號(hào)序列的結(jié)構(gòu)結(jié)構(gòu) 即語法樹即語法樹遞歸下降分析舉例Zhou, Erqiang6School of Information and Software Engineeringexpexp: factor: factor| | expexp + factorfactor| | expexp - factorfactor; ;factorfactor: term: term| | factor fa

7、ctor * * 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-3t

8、ermtermtermtermfactorfactorexptermfactorexpfactorexpnull5205-*+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抽象語法樹結(jié)點(diǎn)設(shè)計(jì)抽象語法樹結(jié)點(diǎn)設(shè)計(jì) 所有樹結(jié)點(diǎn)統(tǒng)一為所有樹結(jié)點(diǎn)統(tǒng)一為 一個(gè)

9、一個(gè) 結(jié)構(gòu)類型結(jié)構(gòu)類型 如何區(qū)別結(jié)點(diǎn)：賦值語句？選擇語句？如何區(qū)別結(jié)點(diǎn)：賦值語句？選擇語句？ 結(jié)點(diǎn)內(nèi)需要結(jié)點(diǎn)內(nèi)需要 用用標(biāo)志位標(biāo)志位 結(jié)點(diǎn)的最大分支數(shù)結(jié)點(diǎn)的最大分支數(shù) 表達(dá)式最多為二元運(yùn)算，至少表達(dá)式最多為二元運(yùn)算，至少 2 2 個(gè)個(gè) 結(jié)點(diǎn)為樹的葉結(jié)點(diǎn)結(jié)點(diǎn)為樹的葉結(jié)點(diǎn) 需要保存運(yùn)算的數(shù)值需要保存運(yùn)算的數(shù)值 表達(dá)式的抽象語法樹Zhou, Erqiang10School of Information and Software Engineering抽象語法樹結(jié)點(diǎn)設(shè)計(jì)抽象語法樹結(jié)點(diǎn)設(shè)計(jì) 表達(dá)式的抽象語法樹Zhou, Erqiang11School of Information and Softwar

10、e Engineeringtypedef 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; ;遞歸下降分析函數(shù)遞歸下降分析函數(shù) 表達(dá)式的抽象語法樹Zhou, Erqiang12School of Information a

11、nd Software 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

12、 = tok;advanceadvance();();past past r = astTerm();r = astTerm();l = newExpr(oper, l, r);l = newExpr(oper, l, r); return return l;l; 實(shí)驗(yàn)任務(wù)1. 1. 學(xué)習(xí)所提供的學(xué)習(xí)所提供的“表達(dá)式文法表達(dá)式文法”的遞歸下降處理的遞歸下降處理 理解理解 rdlex.lrdlex.l、rdparser.crdparser.c的內(nèi)容的內(nèi)容 在在eclipseeclipse中建立工程并調(diào)試運(yùn)行中建立工程并調(diào)試運(yùn)行2. 2. 學(xué)習(xí)學(xué)習(xí)rdgram.txtrdgram.txt所提供的文

13、法所提供的文法 與詞法分析所提供的文法作比較與詞法分析所提供的文法作比較Zhou, Erqiang13School of Information and Software Engineering實(shí)驗(yàn)任務(wù)3. 3. 編寫編寫rdgramrdgram所提供文法的遞歸下降程序所提供文法的遞歸下降程序 (1)(1)編寫不生成編寫不生成“語法樹語法樹”的遞歸下降程序的遞歸下降程序 rdcheck.c (2) (2)將將rdcheck.c改造為生成語法樹的遞歸下降程序改造為生成語法樹的遞歸下降程序rdparser.c (3) (3)改進(jìn)改進(jìn) 詞法分析程序、詞法分析程序、showAst函數(shù)、函數(shù)、main函

14、數(shù)等，使函數(shù)等，使遞歸下降程序遞歸下降程序rdparser最終最終從命令行讀取從命令行讀取要分析的程序要分析的程序test.c, ,分析后調(diào)用分析后調(diào)用showAst打印該程序的結(jié)構(gòu)。打印該程序的結(jié)構(gòu)。Zhou, Erqiang14School of Information and Software Engineering實(shí)驗(yàn)安排要求1. 1. 實(shí)驗(yàn)分組與實(shí)驗(yàn)一相同，每組只需交一份報(bào)告及程序?qū)嶒?yàn)分組與實(shí)驗(yàn)一相同，每組只需交一份報(bào)告及程序2. 2. 所有文件都以所有文件都以 utf-8utf-8 進(jìn)行統(tǒng)一編碼保存！進(jìn)行統(tǒng)一編碼保存！ ( (檢查環(huán)境為檢查環(huán)境為LinuxLinux，如出現(xiàn)亂碼等錯(cuò)

15、誤，扣，如出現(xiàn)亂碼等錯(cuò)誤，扣 1 1 分！分！) )Zhou, Erqiang15School of Information and Software Engineering實(shí)驗(yàn)安排要求3. 3. 提交文件：提交文件： 詞法分析程序詞法分析程序 rdlex.lrdlex.l 不生成不生成“語法樹語法樹”的遞歸下降程序的遞歸下降程序 rdcheck.crdcheck.c 生成語法樹的遞歸下降程序生成語法樹的遞歸下降程序 rdparser.crdparser.c 實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告 遞歸下降分析法遞歸下降分析法.docx.docx 未按此規(guī)定命名的提交未按此規(guī)定命名的提交 扣扣 1 1 分分。Zho

16、u, Erqiang16School of Information and Software Engineering實(shí)驗(yàn)安排要求4. 4. 提交方式提交方式 組長用自己組長用自己QQQQ登錄騰訊登錄騰訊 微云微云 http:/ 之后以組長之后以組長“學(xué)號(hào)學(xué)號(hào)_ _姓氏姓氏_ _實(shí)驗(yàn)實(shí)驗(yàn)2 2”的格式建立文件夾的格式建立文件夾 ( (如如 2013110101011_2013110101011_周周_ _實(shí)驗(yàn)實(shí)驗(yàn)2 2） 將所需的文件上傳至該文件夾，之后分享該文件夾將所需的文件上傳至該文件夾，之后分享該文件夾 切勿切勿設(shè)置訪問密碼，否則設(shè)置訪問密碼，否則視為未提交視為未提交 將分享鏈接發(fā)到將分享

17、鏈接發(fā)到 郵件主題郵件主題 “編譯實(shí)驗(yàn)編譯實(shí)驗(yàn)”, 發(fā)到其它郵箱發(fā)到其它郵箱視為未提交視為未提交Zhou, Erqiang17School of Information and Software Engineering實(shí)驗(yàn)安排要求5. 5. 提交截止日期提交截止日期 北京時(shí)間北京時(shí)間 20152015年年1010月月3131日日23:59:5923:59:59（周六）（周六） 此時(shí)間之后此時(shí)間之后 再發(fā)分享鏈接再發(fā)分享鏈接 或或 更改文件夾內(nèi)容更改文件夾內(nèi)容 將無效將無效編譯技術(shù)資料編譯技術(shù)資料http:/ 自己的微云，再瀏覽下載，不用直接下載自己的微云，再瀏覽下載，不用直接下載Zhou, E

18、rqiang18School of Information and Software EngineeringZhou, ErqiangTHE ENDQUESTIONS19School of Information and Software Engineeringprogramprogram : external_declaration : external_declaration | | program program external_declarationexternal_declaration ; ;external_declarationexternal_declaration : t

19、ype declarator 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 ; ;遞歸下降

20、分析舉例Zhou, 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 parame

21、ter_list ) ) | 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 :

22、 type declarator_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

23、 | RETURN 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 Engineeringparameter

24、parameter : 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

25、_expr | 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

26、| | NUMBERNUMBER | | 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

27、| cmp_expr 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 ; ;程序在詞法分析后的結(jié)果是？程序在詞法分析后的結(jié)果是？enum enum INT INT = 258, = 258, STR, VOID, ID, NUMBER, STRING, PRINT, RETURN, STR, VOID, ID, NUMBER, STRING,

28、PRINT, RETURN, .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 等為枚舉類型定義的值等為枚舉類型定義的值 , = 等為符號(hào)對(duì)應(yīng)等為符號(hào)對(duì)應(yīng)ASCII編碼的值編碼的值 STR ID ( INT ID ) STR ID = STRING + STRING ; STR ID = STRING + .STR ID ( INT

29、ID ) STR 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; ;progr

30、am =program = external_declaration external_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(in

31、t a)f(int 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_

32、list | ID | ID = = intstr_listintstr_list ; ;decl_or_stmtdecl_or_stmt : : statement_list statement_list | | | | , , declarator_list declarator_list ; | | ; ; ;program =program = external_declaration external_declaration= = type type declarator declarator decl_or_stmtdecl_or_stmt= = INT INT ID expr =

33、 intstr_list ID expr = intstr_list ; ;expr = cmp_expr = add_expr = mul_expr = primary_expr = expr = cmp_expr = add_expr = mul_expr = primary_expr = NUMBERNUMBERintstr_list = intstr_list = intstr_listintstr_list , NUMBER , NUMBER intstr_list = intstr_list = intstr_list , NUMBERintstr_list , NUMBER ,

34、NUMBER , NUMBERintstr_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 ,

35、 NUMBER , NUMBER tokentoken對(duì)應(yīng)的屬性對(duì)應(yīng)的屬性 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;

36、c; intstr_listintstr_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 de

37、clarator decl_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, d

38、s);return return 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 = ex

39、ternal_declaration();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_li

40、st : parameter : 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();resul

41、t = newList(result, parameter(); return result;return result; program =program = program program external_declarationexternal_declaration= = external_declarationexternal_declaration external_declaration external_declaration= . = . type type declarator declarator decl_or_stmtdecl_or_stmt= . = . STR STR ID ( parameter_list )ID ( parameter_list ) statement_list stat