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

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

2、gexpexp: factor: factor| | expexp + factorfactor| | expexp - factorfactor; ;遞歸下降分析舉例Zhou, Erqiang3School of Information and Software Engineering語(yǔ)言語(yǔ)言：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 .重復(fù)出現(xiàn)的部分重復(fù)出現(xiàn)的部分factorfactor: term: term| | factor factor * * term term| | factor factor / term term; ;遞歸下降分析舉例Zhou, Erqiang4School of Information and Software Engineering語(yǔ)言語(yǔ)言：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 .重復(fù)出現(xiàn)的部分重復(fù)出現(xiàn)的部分termterm: : NUMBERNUMBER| | - term term; ;遞歸下降分析舉例Zhou, Erqiang5School of Information and Softwar

5、e Engineering語(yǔ)言語(yǔ)言：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(); 純粹的語(yǔ)法分析只分析純

6、粹的語(yǔ)法分析只分析 詞法記號(hào)序列是否符合語(yǔ)言的文法詞法記號(hào)序列是否符合語(yǔ)言的文法 如如 -5+20 -5+20* *5-35-3實(shí)際的編譯器實(shí)際的編譯器 需要找出詞法記號(hào)序列的需要找出詞法記號(hào)序列的結(jié)構(gòu)結(jié)構(gòu) 即語(yǔ)法樹(shù)即語(yǔ)法樹(shù)遞歸下降分析舉例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-抽象的語(yǔ)法樹(shù)抽象的語(yǔ)法樹(shù)（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 抽象語(yǔ)法樹(shù)Zhou, Erqiang9School of Information and Software Engineering抽象語(yǔ)法樹(shù)結(jié)點(diǎn)設(shè)計(jì)抽象語(yǔ)法樹(shù)結(jié)點(diǎn)設(shè)計(jì) 所有樹(shù)結(jié)點(diǎn)統(tǒng)一為所有樹(shù)結(jié)點(diǎn)統(tǒng)一為 一個(gè)一個(gè) 結(jié)構(gòu)類型結(jié)

9、構(gòu)類型 如何區(qū)別結(jié)點(diǎn)：賦值語(yǔ)句？選擇語(yǔ)句？如何區(qū)別結(jié)點(diǎn)：賦值語(yǔ)句？選擇語(yǔ)句？ 結(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)為樹(shù)的葉結(jié)點(diǎn)結(jié)點(diǎn)為樹(shù)的葉結(jié)點(diǎn) 需要保存運(yùn)算的數(shù)值需要保存運(yùn)算的數(shù)值 表達(dá)式的抽象語(yǔ)法樹(shù)Zhou, Erqiang10School of Information and Software Engineering抽象語(yǔ)法樹(shù)結(jié)點(diǎn)設(shè)計(jì)抽象語(yǔ)法樹(shù)結(jié)點(diǎn)設(shè)計(jì) 表達(dá)式的抽象語(yǔ)法樹(shù)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; ;遞歸下降分析函數(shù)遞歸下降分析函數(shù) 表達(dá)式的抽象語(yǔ)法樹(shù)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; 實(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. 編寫(xiě)編寫(xiě)rdgramrdgram所提供文法的遞歸下降程序所提供文法的遞歸下降程序 (1)(1)編寫(xiě)不生成編寫(xiě)不生成“語(yǔ)法樹(shù)語(yǔ)法樹(shù)”的遞歸下降程序的遞歸下降程序 rdcheck.c (2) (2)將將rdcheck.c改造為生成語(yǔ)法樹(shù)的遞歸下降程序改造為生成語(yǔ)法樹(shù)的遞歸下降程序rdparser.c (3) (3)改進(jìn)改進(jìn) 詞法分析程序、詞法分析程序、showAst函數(shù)、函數(shù)、main函數(shù)等，使函數(shù)等，

14、使遞歸下降程序遞歸下降程序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)境為L(zhǎng)inuxLinux，如出現(xiàn)亂碼等錯(cuò)誤，扣，如出現(xiàn)亂

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

16、ng16School of Information and Software Engineering實(shí)驗(yàn)安排要求4. 4. 提交方式提交方式 組長(zhǎng)用自己組長(zhǎng)用自己QQQQ登錄騰訊登錄騰訊 微云微云 http:/ 之后以組長(zhǎng)之后以組長(zhǎng)“學(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è)置訪問(wèn)密碼，否則設(shè)置訪問(wèn)密碼，否則視為未提交視為未提交 將分享鏈接發(fā)到將分享鏈接發(fā)到 郵件主

17、題郵件主題 “編譯實(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)容 將無(wú)效將無(wú)效編譯技術(shù)資料編譯技術(shù)資料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 ; ;程序在詞法分析后的結(jié)果是？程序在詞法分析后的結(jié)果是？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 等為枚舉類型定義的值等為枚舉類型定義的值 , = 等為符號(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 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對(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;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