語(yǔ)法分析器-YACC實(shí)驗(yàn)報(bào)告

1、大學(xué)學(xué) 院實(shí)驗(yàn)報(bào)告學(xué)號(hào)：姓名：專業(yè)：班級(jí)：第周課程名稱編譯原理課程設(shè)計(jì)實(shí)驗(yàn)課時(shí)實(shí)驗(yàn)項(xiàng)目基于YACC的語(yǔ)法分析器實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)?zāi)康?2學(xué)習(xí)基于 YACC的語(yǔ)法分析器的構(gòu)造方法。學(xué)習(xí) C-的語(yǔ)法結(jié)構(gòu)。Parser Generator實(shí)驗(yàn)環(huán)境VC+ 6.0實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法）基于 YACC構(gòu)造詞法分析器的方法1 YACC文件格式Lex 文件分成三個(gè)部分，分別為definitions、rules以及auxiliary routines，中間用 %分割開(kāi)。Definitions包括要加入到生成的C程序的頭部的代碼， 包括#include 語(yǔ)句、 #define 語(yǔ)句及一些全局變量的定義。 t

2、oken 也在 Definitions 部分定義，YACC規(guī)定，必須自己定義 token ，他將 token 定義為一系列從 258 開(kāi)始的正整數(shù)，如在 Definition 部分加入了如下定義： %token NUMBER,則在生成的 C 代碼中：#define NUMBER 258。當(dāng)然這個(gè)值也可以由用戶定義。Definitions 中同時(shí)還定義了 YACC中的返回值類型，由于 rules 部分是由固定符號(hào)來(lái)代替一個(gè) Symbol 的返回值，其默認(rèn)類型為 int ，如果用戶希望返回其他類型的值 （如 ParseTree 樹(shù)結(jié)點(diǎn)），則可以在 Definition 中定義 Symbol 的返回

3、值。首先使用一個(gè)%union 包含所有需要的返回值類型，定義 %type<t> 其中包含所有返回值為 t 的 Symbol。Definitions 中可以定義語(yǔ)法的結(jié)合性來(lái)消除二義性， 包括兩個(gè)符號(hào) %left 表示左結(jié)合和 %right 表示右結(jié)合。rules 部分定義所有語(yǔ)法，以及語(yǔ)法識(shí)別出后執(zhí)行的操作。例如：declaration:var_declaration $ = $1; |fun_declaration $ = $1; ;%表示產(chǎn)生式左邊， $n 表示產(chǎn)生式右邊第 n 個(gè)字符的返回值，這條規(guī)則表示 var_declaration 或 fun_declaration 識(shí)

4、別出后，將其賦值給 declaration。Auxiliary部分包括 rules部分使用的一些輔助函數(shù)，同時(shí)，main 函數(shù)也在其中定義。 YACC中會(huì)自動(dòng)調(diào)用 yylex() 獲取 token ，默認(rèn) yylex() 返回 int ，代表識(shí)別出的 token ，如果文件結(jié)束返回 0。因此一般會(huì)進(jìn)行如下定義：static Type yylex(void) return getToken(); Type 就是 int ，專門(mén)代表 token 值。Auxiliaryyyerror(char部分還可以定義YACC的出錯(cuò)處理函數(shù)，*s) ，其中 s 是 YACC在遇到錯(cuò)誤時(shí)產(chǎn)生的錯(cuò)誤信息。YACC的

5、入口函數(shù)為： yyparse() ，調(diào)用這個(gè)函數(shù)即開(kāi)始語(yǔ)法分析過(guò)程。2 數(shù)據(jù)結(jié)構(gòu)我們需要再 YACC中構(gòu)造 Parse Tree, 必須定義樹(shù)結(jié)點(diǎn)，觀察C-的語(yǔ)法，我們可以將語(yǔ)法分為三類：Declaration :包括函數(shù)與變量的聲明。Statement :包括各種語(yǔ)句，如循環(huán)語(yǔ)句，選擇語(yǔ)句等。Expression :包括各種表達(dá)式及各種變量、常量。我們也將節(jié)點(diǎn)類型分為Dec、Stmt 、Exp。節(jié)點(diǎn)類型定義如下：typedefstructtreeNode/ 兒子structtreeNode* childMAXCHILDREN;/ 兄弟structtreeNode* sibling;/ 結(jié)點(diǎn)在

6、 source 中的行數(shù)intlineno;/ 如果結(jié)點(diǎn)是函數(shù)或變量的話，記錄其類型Type type;/ 結(jié)點(diǎn)的大類型NodeKind nodekind;/ 結(jié)點(diǎn)的小類型union StmtKind stmt;ExpKind exp;DecKind dec;kind;/ 結(jié)點(diǎn)的值union Type op;intvalue;/ 如果是非葉結(jié)點(diǎn)，則應(yīng)該有token/C Minus中只有一種數(shù)據(jù)類型類型int ，如果是葉結(jié)點(diǎn)，一定是 intchar * name;/ 如果是 ID 類型，則有名字attr;TreeNode;由于我們的最終目的是構(gòu)造 Parse Tree ，因此 YACC的返回類型

7、應(yīng)當(dāng)為 Symbol對(duì)應(yīng)的子樹(shù)的根結(jié)點(diǎn)。而 type_specifer 、addop、 relop 、 mulop我們不希望為他們構(gòu)造結(jié)點(diǎn)，而直接返回其對(duì)應(yīng)值，因此在 YACC中進(jìn)行如下聲明：%type<ptree> program declaration_list declaration var_declaration fun_declaration params param_list param compound_stmt local_declarations statement_list statement expression_stmt selection_stmt ite

8、ration_stmt return_stmt expression var simple_expression additive_expression term factor call args arg_list%type<type> type_specifier relop addop mulop將除 type_specifier relop addop mulop 外所有 Symbol返回樹(shù)結(jié)點(diǎn)，這四個(gè) Symbol直接返回其對(duì)應(yīng)的 Token。3 編譯過(guò)程實(shí)現(xiàn)C-共有 29條規(guī)則，在 YACC不需消除左遞歸與左因子，因此只需定義 29條rules 即可，當(dāng)一條規(guī)則識(shí)別出后，

9、執(zhí)行操作遵循以下規(guī)則：1. 如果有 NUM，則立刻用一個(gè)變量暫存，因?yàn)楹竺娴淖R(shí)別會(huì)把TokenValue覆蓋掉。如： type_specifier id LBRACKET NUM /*記錄 NUM*/ currentNum =atoi(tokenString); RBRACKET SEMICOLON2. 如果有 ID ，與 NUM同理，用立刻一個(gè)字符串暫存。3. 如果產(chǎn)生式右邊有多余一個(gè)的 Symbol，則必須為 $建立結(jié)點(diǎn)，并將右面的 Symbol作為他的兒子，如果有 ID、 NUM、 type_specfier ，和關(guān)鍵字，則不需建立結(jié)點(diǎn)，直接賦值給結(jié)點(diǎn)中的變量或忽略（結(jié)點(diǎn)類型自動(dòng)說(shuō)明）。

10、如：iteration_stmt:WHILE LPARENTHESIS expressionRPARENTHESIS statement$ = newStmtNode(WhileK);$ -> child0 = $3;$ -> child1 = $5;4如果右邊僅有一個(gè) Symbol，如果為 Token，則返回 Token 值，如果為 Nonterminal ，直接 $ = $1 。如：statement:expression_stmt $ = $1; 5. 如果有左遞歸， 則統(tǒng)一用下面代碼處理， 注意，左遞歸的結(jié)點(diǎn)存儲(chǔ)在 sibling 中而不是 child 中。tatement

11、_list:statement_list statementTreeNode* t = $1;if( t != NULL )while(t->sibling != NULL)t = t->sibling;t->sibling = $2;$ = $1;else$ = $2;|$ = NULL;YACC 是由 yylex() 提供 Token，因此需要編寫(xiě) getToken() 函數(shù)，使用 lex 或手工實(shí)現(xiàn)均可，但需注意，其返回的 Token 值必須是YACC中定義的 int, 也就是說(shuō)，不能在別處定義 TokenType。在 main 函數(shù)中調(diào)用 yyparse() 即可進(jìn)行

12、編譯。實(shí)驗(yàn)源程序如下：/* a program to perform selection sort on a 10element array. */int x10;int minloc( int a, int low, int high )數(shù)據(jù)記錄和計(jì)算int i; int x; int k;k = low;x = alow;i = low + 1;while ( i < high )if ( ai < x )x = ai;k = i; return k;生成的 Parse Tree 如下所示：|_Arr name:x, type:INT|_Number type:INT, val

13、ue:10|_FunDec name:minloc, return:INT|_ArrParam name:a, type:INT|_ValParam name:low, type:INT|_ValParam name:high, type:INT|_Comp|_Var name:i, type:INT|_Var name:x, type:INT|_Var name:k, type:INT|_Assign|_VarId name:k結(jié)論|_VarId name:low（結(jié)果）|_Assign|_VarId name:x|_ArrId name:low|_VarId name:low|_Assign|_VarId name:i|_Expression type:+|_VarId name:low|_Number type:INT, value:1|_While|_Expression type:<|_VarId name:i|_VarId name:high|_Comp|_Return|_VarId name:k可見(jiàn) ParseTree中所需結(jié)點(diǎn)都被生成，并且ID 、 NUM、type_specifier都被記錄在結(jié)點(diǎn)中。1. 通過(guò)本實(shí)驗(yàn)，我熟悉了 C-的語(yǔ)法規(guī)則，學(xué)習(xí)了 ParseTree 的構(gòu)造方法。2. 學(xué)習(xí)了通過(guò)