編譯原理課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、編譯原理課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康模哼@個(gè)實(shí)驗(yàn)的目的是構(gòu)造C minus語(yǔ)言的編譯器，要求能夠編譯C minus語(yǔ)言的程序并且生成中間代碼。在實(shí)驗(yàn)的過(guò)程中，學(xué)會(huì)使用flex/bison這兩個(gè)重要的工具。實(shí)驗(yàn)內(nèi)容： 參見(jiàn)教材 p491 appendix A.設(shè)計(jì)一cminus語(yǔ)言編譯器語(yǔ)言介紹。Decaf（cminus）語(yǔ)言的關(guān)鍵字：int while if else return void運(yùn)算符：+ - * / > < = , . != <= >= = () C minus語(yǔ)言的限制。數(shù)字：支持10進(jìn)制整數(shù)。小數(shù)可以采用科學(xué)記數(shù)法，如1E3也是合法的。字符串：字符串內(nèi)部不允

2、許出現(xiàn)換行，即字符串變量必須在同一行內(nèi)。注釋：C minus語(yǔ)言允許采用/*/注釋，并且注釋不可以嵌套，即下面的注釋是不合法的：/*This is /*a valid */comment*/程序流程圖開始詞法分析語(yǔ)法分析建立符號(hào)表類型檢查代碼生成結(jié)束語(yǔ)法樹符號(hào)表程序的流程參照了書本TINY編譯器的實(shí)例程序：語(yǔ)法分析器(Parser)調(diào)用詞法分析器得到符合詞法的字，建立語(yǔ)法樹；符號(hào)表通過(guò)對(duì)語(yǔ)法樹的分析，建立符號(hào)表，同時(shí)檢查變量未定義等錯(cuò)誤；類型檢查包括檢查表達(dá)式兩邊是否匹配，函數(shù)參數(shù)是否匹配等等；經(jīng)由上述步驟而未出錯(cuò)的源程序被認(rèn)為是合法程序，然后代碼生成通過(guò)語(yǔ)法樹和符號(hào)表生成P Code中間代碼

3、，并將變量地址存入符號(hào)表。其中類型檢查和代碼生成不要求實(shí)現(xiàn)。本次實(shí)驗(yàn)要求分組，一組五人，一人完成一個(gè)部分。本組實(shí)驗(yàn)分組成員以及分工介紹：汪晨風(fēng)：（設(shè)計(jì)并實(shí)現(xiàn)cminus符號(hào)表）；E02620105蔡其星：（編寫cminus.l文件，并用lex工具生成c代碼）；E02620107趙婷：（設(shè)計(jì)cminus語(yǔ)法樹結(jié)構(gòu)）；E02620106馬培良：編寫cminus.y文件，并用yacc工具生成可執(zhí)行代碼）；E02620121丘廷：（進(jìn)行程序的測(cè)試）以下為具體實(shí)驗(yàn)分步報(bào)告以及過(guò)程：第一部分：設(shè)計(jì)cminus符號(hào)表符號(hào)表是編譯器中的主要繼承屬性，并且在語(yǔ)法樹之后，形成了主要的數(shù)據(jù)結(jié)構(gòu)。符號(hào)表主要的操作有插

4、入、查找和刪除。雜湊表（hash表）通常為符號(hào)表的實(shí)現(xiàn)提供了最好的選擇，因?yàn)樗?種操作都能在幾乎恒定的時(shí)間內(nèi)完成，在實(shí)踐中也是最常使用。該課程設(shè)計(jì)所用的C-符號(hào)表采用建立雜湊表的方法。雜湊表是一個(gè)入口數(shù)組，稱作“桶( b u c k e t )”，使用一個(gè)整數(shù)范圍的索引，通常從0到表的尺寸減1。雜湊函數(shù)(hash fuction)把索引鍵(在這種情況下是標(biāo)識(shí)符名，組成一個(gè)字符串)轉(zhuǎn)換成索引范圍內(nèi)的一個(gè)整數(shù)的雜湊值，對(duì)應(yīng)于索引鍵的項(xiàng)存儲(chǔ)在這個(gè)索引的“桶”中。每個(gè)“桶”實(shí)際上又是一個(gè)線性表，通過(guò)把新的項(xiàng)插入到“桶”表中來(lái)解決沖突在任何情況下，“桶”數(shù)組的實(shí)際大小要選擇一個(gè)素?cái)?shù)，因?yàn)檫@將使一般的雜

5、湊函數(shù)運(yùn)行得更好。雜湊函數(shù)。在符號(hào)表實(shí)現(xiàn)中使用的雜湊函數(shù)將字符串(標(biāo)識(shí)符名)轉(zhuǎn)換成0. . . s i z e- 1范圍內(nèi)的一個(gè)整數(shù)。一般這通過(guò)3步來(lái)進(jìn)行。首先，字符串中的每個(gè)字符轉(zhuǎn)換成一個(gè)非負(fù)整數(shù)。然后，這些整數(shù)用一定的方法組合形成一個(gè)整數(shù)。最后，把結(jié)果整數(shù)調(diào)整到0. . . s i z e- 1范圍內(nèi)。沖突的一個(gè)好的解決辦法是，當(dāng)加上下一個(gè)字符的值時(shí)，重復(fù)地使用一個(gè)常量作為乘法因子。因此，如果ci 是第i 個(gè)字符的數(shù)字值， hi 是在第i 步計(jì)算的部分雜湊值，那么hi 根據(jù)下面的遞歸公式計(jì)算，h0 = 0，hi 1 = ahi ci ，最后的雜湊值用h = hn m o d s i z e

6、計(jì)算。這里n 是雜湊的名字中字符的個(gè)數(shù)。這等價(jià)于下列公式當(dāng)然，在這個(gè)公式中a的選擇對(duì)輸出結(jié)果有重要影響。a的一種合理的選擇是2的冪，如1 6或1 2 8，這樣乘法可以通過(guò)移位來(lái)完成。該程序a選16，s i z e 取211。由于在數(shù)據(jù)結(jié)構(gòu)方面為了實(shí)現(xiàn)很方便的進(jìn)行查找，插入，刪除等操作。我們把它的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)成一哈稀表結(jié)構(gòu)，哈稀表的查找，插入等操作是飛快的。我們所設(shè)計(jì)的哈稀結(jié)構(gòu)符號(hào)表是參考教科書上P295它的結(jié)構(gòu)如下：符號(hào)表的雜湊函數(shù)#define SIZE 211#define SHIFT 4int hash ( char * key ) int temp = 0;int i = 0;whil

7、e (keyi != '0') temp = (temp << SHIFT) + keyi) % SIZE;+ + i ;return temp;該符號(hào)表完成了插入void st_insert( char * name, int lineno, int loc )、查找int st_lookup ( char * name )工作源程序：symtab.c#include <stdio.h>#include <stdlib.h>#include <string.h>#include "symtab.h"/* 定義

8、哈稀表的最大值 */#define SIZE 211/* SHIFT is the power of two used as multiplier in hash function */#define SHIFT 4/* 哈稀函數(shù)結(jié)構(gòu) */static int hash ( char * key ) int temp = 0; int i = 0; while (keyi != '0') temp = (temp << SHIFT) + keyi) % SIZE; +i; return temp;typedef struct LineListRec int line

9、no; struct LineListRec * next; * LineList;typedef struct BucketListRec char * name; LineList lines; int memloc ; /* memory location for variable */ struct BucketListRec * next; * BucketList;/* 哈稀表*/static BucketList hashTableSIZE; void st_insert( char * name, int lineno, int loc ) int h = hash(name)

10、; BucketList l = hashTableh; while (l != NULL) && (strcmp(name,l->name) != 0) l = l->next; if (l = NULL) /* variable not yet in table */ l = (BucketList) malloc(sizeof(struct BucketListRec); l->name = name; l->lines = (LineList) malloc(sizeof(struct LineListRec); l->lines->

11、lineno = lineno; l->memloc = loc; l->lines->next = NULL; l->next = hashTableh; hashTableh = l; else /* found in table, so just add line number */ LineList t = l->lines; while (t->next != NULL) t = t->next; t->next = (LineList) malloc(sizeof(struct LineListRec); t->next->

12、;lineno = lineno; t->next->next = NULL; int st_lookup ( char * name ) int h = hash(name); BucketList l = hashTableh; while (l != NULL) && (strcmp(name,l->name) != 0) l = l->next; if (l = NULL) return -1; else return l->memloc; void printSymTab(FILE * listing) int i; fprintf(li

13、sting,"Variable Name Location Line Numbersn"); fprintf(listing,"- - -n"); for (i=0;i<SIZE;+i) if (hashTablei != NULL) BucketList l = hashTablei; while (l != NULL) LineList t = l->lines; fprintf(listing,"%-14s ",l->name); fprintf(listing,"%-8d ",l->

14、memloc); while (t != NULL) fprintf(listing,"%4d ",t->lineno); t = t->next; fprintf(listing,"n"); l = l->next; /* printSymTab */symtab.h#ifndef _SYMTAB_H_#define _SYMTAB_H_void st_insert( char * name, int lineno, int loc ); /*插入函數(shù)*/int st_lookup ( char * name ); /*查找函數(shù)*/v

15、oid printSymTab(FILE * listing); /*用來(lái)打印哈稀表內(nèi)容*/#endif 符號(hào)表設(shè)計(jì)的好壞直接影響到整個(gè)程序運(yùn)行的速度，效率以及準(zhǔn)確度。因?yàn)榻酉聛?lái)的parse工作是基于符號(hào)表的，是從符號(hào)表里提取token進(jìn)行語(yǔ)法分析的。為了提高程序運(yùn)行的的效率，我們把scan直接通過(guò)parse來(lái)調(diào)用。具體的來(lái)講就是，程序運(yùn)行時(shí)，首先進(jìn)入parse部分，當(dāng)parse要用到token時(shí)，調(diào)用scan部分掃描原文件生成token儲(chǔ)存在符號(hào)表中，并同時(shí)提供給parse進(jìn)行語(yǔ)法分析。這樣就可以一遍完成整個(gè)原文件的掃描。第二部分：運(yùn)用LEX實(shí)現(xiàn)cminus詞法分析程序。這一部比較關(guān)鍵，設(shè)計(jì)

16、的正確與否直接影響到在scan過(guò)程中token的產(chǎn)生。以及整個(gè)程序運(yùn)行的結(jié)果的正確與否。在這里主要定義cminus的基本語(yǔ)法規(guī)則，以及token類型，運(yùn)算符類型，并且定義cminus關(guān)鍵字，便于在程序運(yùn)行時(shí)能對(duì)其進(jìn)行識(shí)別。一下為cminus.l文件原代碼：/*定義全局變量、函數(shù)及包含文件說(shuō)明：*/%#include "globals.h "#include "util.h"#include "scan.h "#define MAXTOKENLEN 40char tokenString40;int lineno = 0;%/*有關(guān)語(yǔ)法規(guī)

17、則以及token的定義:*/digit 0-9number digit+letter a-zA-Zidentifier letter+newline nwhitespace t+%/*以下為關(guān)鍵字定義:*/"if" return IF;"else" return ELSE;"int" return INT;"void" return VOID;"return" return RETURN;"while" return WHILE;/*以下為運(yùn)算符號(hào)定義:*/"=&q

18、uot; return ASSIGN;"<=" return LTEQ;">=" return GTEQ;"<" return LT;">" return GT;"=" return EQ;"!=" return NOTEQ;"+" return PLUS;"-" return MINUS;"*" return TIMES;"/" return OVER;"(&q

19、uot; return LPAREN;")" return RPAREN;"" return LBRACK;"" return RBRACK;"" return LCURL;"" return RCURL;"" return SEMI;"," return COMMA;/*終結(jié)符及注釋符號(hào)*/number return NUM;identifier return ID;newline lineno+;whitespace /* skip whitespac

20、e */"/*" char c;char d; c = input(); if (c != EOF) do d = c; c = input(); if (c = EOF) break; if (c = 'n') lineno+; while (!(d = '*' && c = '/'); . return ERROR;%/*定義getToken()函數(shù)體:*/TokenType getToken(void) static int firstTime = TRUE; TokenType currentToken

21、; if (firstTime) firstTime = FALSE; lineno+; yyin = source; yyout = listing; currentToken = yylex(); strncpy(tokenString,yytext,MAXTOKENLEN); if (TraceScan) fprintf(listing,"t%d: ",lineno); printToken(currentToken,tokenString); return currentToken;說(shuō)明：以上代碼已經(jīng)能通過(guò)lex工具產(chǎn)生c代碼。cminus.l的設(shè)計(jì)基本結(jié)構(gòu)是參考t

22、iny.l的結(jié)構(gòu)設(shè)計(jì)而成，但要注意的是，由于在接下來(lái)的cnimus.y中所定義的語(yǔ)法規(guī)則不同，這里的也要稍做修改。比如在這里的getToken函數(shù)，要于cminus.y文件里的設(shè)計(jì)的返回參數(shù)要一一對(duì)應(yīng)，否則在編譯的過(guò)程中會(huì)出現(xiàn)類型不匹配等等的錯(cuò)誤，修改起來(lái)比較麻煩。 第三部分：為C-設(shè)計(jì)語(yǔ)法樹結(jié)構(gòu)，使之適用于分析器產(chǎn)生語(yǔ)法樹是LALR分析的前提。因此在進(jìn)行語(yǔ)法分析之前，必須設(shè)計(jì)語(yǔ)法樹結(jié)構(gòu)，使接下來(lái)的語(yǔ)法分析有一個(gè)具體的數(shù)據(jù)結(jié)構(gòu)。其代碼段如下：#define MAXTOKENSIZE 50typedef int TokenType; /*定義語(yǔ)法樹結(jié)構(gòu)*/typedef struct Token

23、Type tok; char * tokString; TokenStruct;typedef enum IfK,WhileK,AssignK,ReturnK,CallK,VarDeclK,FunDeclK,OpK,ConstK,IdK NodeKind; /*枚舉結(jié)點(diǎn)類型*/typedef enum Void,Integer,Boolean ExpType; /*枚舉返回變量類型*/#define MAXCHILDREN 3 /*聲明一個(gè)結(jié)點(diǎn)最多有三個(gè)子結(jié)點(diǎn)*/typedef struct treeNode /*定義語(yǔ)法樹結(jié)點(diǎn)結(jié)構(gòu)*/ struct treeNode * childMAXCH

24、ILDREN; struct treeNode * sibling; int lineno; NodeKind kind; union TokenType op; int val; char * name; attr; ExpType type; TreeNode; 說(shuō)明：在這里當(dāng)當(dāng)只是設(shè)計(jì)的語(yǔ)法樹的基本數(shù)據(jù)結(jié)構(gòu)，至于要用到parse過(guò)程中還要進(jìn)行具體的修改，調(diào)試。這些工作都已經(jīng)在程序原代碼調(diào)試過(guò)程中做好。第四部分：LALR分析。（使用yacc工具）這一部分完成了整個(gè)編譯過(guò)程中的語(yǔ)法分析，二異性沖突處理，lese懸掛問(wèn)題的處理，運(yùn)算符優(yōu)先級(jí)處理以及錯(cuò)誤報(bào)告。參考課本P492 29條cminus

25、 BNF。并且通過(guò)細(xì)心理解體會(huì)，寫出了cminus.y文件，并能通過(guò)yacc生成c代碼。Cnimus.y代碼以及一些具體功能如下所述：一 YACC源程序的結(jié)構(gòu)說(shuō)明部分的內(nèi)容如下：頭文件宏定義數(shù)據(jù)類型定義全局變量定義語(yǔ)法開始符定義語(yǔ)義值類型定義終結(jié)符定義運(yùn)算符優(yōu)先級(jí)及結(jié)合性定義%#define YYPARSER /* distinguishes Yacc output from other code files */#include "globals.h"#include "util.h"#include "scan.h"#includ

26、e "parse.h"TreeNode * parseTree; /* stores syntax tree for later return */void yyerror (const char *s);%語(yǔ)法開始符號(hào)的定義start 非終結(jié)符注：若沒(méi)有上述說(shuō)明，YACC自動(dòng)將第一條語(yǔ)法規(guī)則左部的非終結(jié)符作為語(yǔ)法開始符。 語(yǔ)義值類型的定義%union定義語(yǔ)義值的類型;%union TreeNode * tnode; TokenType tok; %type定義文法符號(hào)的語(yǔ)義值類型; %type <tnode> program declaration_list

27、declaration var_declaration%type <tnode> fun_declaration params param_list param compound_stmt %type <tnode> local_declarations statement_list statement %type <tnode> expression_stmt selection_stmt iteration_stmt%type <tnode> return_stmt expression var simple_expression%type

28、<tnode> additive_expression term factor call args arg_list%type <tok> type_specifier relop addop mulop%token在定義終結(jié)符號(hào)時(shí)也可以定義語(yǔ)義值類型。終結(jié)符的定義%token <語(yǔ)義值類型> 終結(jié)符名 編號(hào)%token DIGIT LETTER%token BEGIN 100注： 1.非終結(jié)符不需要特別說(shuō)明，如果需要說(shuō)明語(yǔ)義值類型則用type語(yǔ)句； 2.文字字符終結(jié)符不需要特別說(shuō)明，它們的編號(hào)取其在字符集中的值； 3.在規(guī)則中出現(xiàn)文字字符時(shí)用單引號(hào)括起來(lái)。

29、%token ENDFILE,ERROR,%token IF,ELSE,INT,RETURN,VOID,WHILE,%token ID,NUM,%token ASSIGN,%token EQ,NOTEQ,LTEQ,GTEQ,LT,GT,%token PLUS,MINUS,TIMES,OVER,%token LPAREN,RPAREN,LBRACK,RBRACK,LCURL,RCURL,%token SEMI,COMMA運(yùn)算符優(yōu)先級(jí)和結(jié)合性的定義以left和right定義結(jié)合性；以排列順序定義優(yōu)先級(jí)；在語(yǔ)法規(guī)則中，以prec輔助定義優(yōu)先級(jí)消除二義性的兩條規(guī)則： 1.出現(xiàn)移進(jìn)/歸約沖突時(shí)，進(jìn)行移進(jìn)

30、； 2.出現(xiàn)歸約/歸約沖突時(shí)，用先出現(xiàn)的規(guī)則進(jìn)行歸約；stat :IF bexp THEN statIF bexp THEN stat ELSE stat ;用結(jié)合性和優(yōu)先級(jí)解決沖突； 規(guī)則的結(jié)合性就是規(guī)則右部最后一個(gè)非終結(jié)符的優(yōu)先級(jí)和結(jié)合性； 如果使用了prec子句，則優(yōu)先級(jí)和結(jié)合性由prec子句決定； 對(duì)于無(wú)優(yōu)先級(jí)和結(jié)合性的規(guī)則，用規(guī)則1、2解決； 對(duì)于有優(yōu)先級(jí)和結(jié)合行的規(guī)則，用如下的規(guī)則解決：出現(xiàn)移進(jìn)/歸約沖突時(shí)，輸入符號(hào)的優(yōu)先級(jí)大于規(guī)則的優(yōu)先級(jí)則移進(jìn)，若輸入符號(hào)的優(yōu)先級(jí)小于規(guī)則的優(yōu)先級(jí)則歸約，若二者的優(yōu)先級(jí)相同，左結(jié)合則歸約，右結(jié)合則移進(jìn)，無(wú)結(jié)合則出錯(cuò)。二 語(yǔ)法規(guī)則program :

31、declaration_list parseTree = $1; YYACCEPT; ;declaration_list: declaration_list declaration TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | declaration $ = $1;declaration: var_declaration $ = $1; | fun_declarat

32、ion $ = $1; ;程序由聲明的列表(或序列)組成，聲明可以是函數(shù)或變量聲明，順序是任意的。至少必須有一個(gè)聲明。接下來(lái)是語(yǔ)義限制(這些在C中不會(huì)出現(xiàn))。所有的變量和函數(shù)在使用前必須聲明(這避免了向后backpatching引用)。程序中最后的聲明必須是一個(gè)函數(shù)聲明，名字為main。var_declaration: type_specifier ID SEMI $ = (TreeNode *) newNode(VarDeclK); $->attr.op = $1; $->child0 = (TreeNode *) newNode(IdK); $->child0->a

33、 = (char *) copyString(lastid); / add to symbol table | type_specifier ID LBRACK NUM $<tnode>$ = (TreeNode *) newNode(VarDeclK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(last

34、id); $<tnode>$->child0 = (TreeNode *) newNode(ConstK); $<tnode>$->child0->attr.val = atoi(curToken.tokString); / add to symbol table RBRACK SEMI $ = $<tnode>5; ;type_specifier: INT $ = INT;| VOID $ = VOID;變量聲明或者聲明了簡(jiǎn)單的整數(shù)類型變量，或者是基類型為整數(shù)的數(shù)組變量，索引范圍從0到NUM-1。注意，在C中僅有的基本類型是整型和空類型。

35、在一個(gè)變量聲明中，只能使用類型指示符int。void用于函數(shù)聲明(參見(jiàn)下面)。也要注意，每個(gè)聲明只能聲明一個(gè)變量。fun_declaration: type_specifier ID $<tnode>$ = (TreeNode *) newNode(FunDeclK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(lasti

36、d); LPAREN params RPAREN compound_stmt $ = $<tnode>3; $->child1 = $5; $->child2 = $7; ;params: param_list $ = $1; | VOID $ = NULL; ;param_list: param_list COMMA param TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $3; $ = $

37、1; else $ = $3; | param $ = $1; ;param: type_specifier ID $ = (TreeNode *) newNode(VarDeclK); $->attr.op = $1; $->child0 = (TreeNode *) newNode(IdK); $->child0-> = (char *) copyString(lastid); / add to symbol table | type_specifier ID $<tnode>$ = (TreeNode *) newNode(VarDe

38、clK); $<tnode>$->attr.op = $1; $<tnode>$->child0 = (TreeNode *) newNode(IdK); $<tnode>$->child0-> = (char *) copyString(lastid); / add to symbol table LBRACK RBRACK $ = $<tnode>3; ;函數(shù)聲明由返回類型指示符、標(biāo)識(shí)符以及在圓括號(hào)內(nèi)的用逗號(hào)分開的參數(shù)列表組成，后面跟著一個(gè)復(fù)合語(yǔ)句，是函數(shù)的代碼。如果函數(shù)的返回類型是void，那么函數(shù)

39、不返回任何值(即是一個(gè)過(guò)程)。函數(shù)的參數(shù)可以是void(即沒(méi)有參數(shù))，或者一列描述函數(shù)的參數(shù)。參數(shù)后面跟著方括號(hào)是數(shù)組參數(shù)，其大小是可變的。簡(jiǎn)單的整型參數(shù)由值傳遞。數(shù)組參數(shù)由引用來(lái)傳遞(也就是指針)，在調(diào)用時(shí)必須通過(guò)數(shù)組變量來(lái)匹配。注意，類型“函數(shù)”沒(méi)有參數(shù)。一個(gè)函數(shù)參數(shù)的作用域等于函數(shù)聲明的復(fù)合語(yǔ)句，函數(shù)的每次請(qǐng)求都有一個(gè)獨(dú)立的參數(shù)集。函數(shù)可以是遞歸的(對(duì)于使用聲明允許的范圍)。compound_stmt: LCURL local_declarations statement_list RCURL TreeNode * t = $2; if (t != NULL) while (t->

40、sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $3; $ = $2; else $ = $3; ;復(fù)合語(yǔ)句由用花括號(hào)圍起來(lái)的一組聲明和語(yǔ)句組成。復(fù)合語(yǔ)句通過(guò)用給定的順序執(zhí)行語(yǔ)句序列來(lái)執(zhí)行。局部聲明的作用域等于復(fù)合語(yǔ)句的語(yǔ)句列表，并代替任何全局聲明。local_declarations: local_declarations var_declaration TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *

41、) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | $ = NULL; ;statement_list: statement_list statement TreeNode * t = $1; if (t != NULL) while (t->sibling != NULL) t = (TreeNode *) t->sibling; t->sibling = $2; $ = $1; else $ = $2; | $ = NULL; ;注意聲明和語(yǔ)句列表都可以是空的(非終結(jié)符empty表示空字符串，有時(shí)寫作)s

42、tatement: expression_stmt $ = $1; | compound_stmt $ = $1; | selection_stmt $ = $1; | iteration_stmt $ = $1; | return_stmt $ = $1; ;expression_stmt: expression SEMI $ = $1; | SEMI $ = NULL; ;表達(dá)式語(yǔ)句有一個(gè)可選的且后面跟著分號(hào)的表達(dá)式。這樣的表達(dá)式通常求出它們一方的結(jié)果。因此，這個(gè)語(yǔ)句用于賦值和函數(shù)調(diào)用。selection_stmt: IF LPAREN expression RPAREN statemen

43、t $ = (TreeNode *) newNode(IfK); $->child0 = $3; $->child1 = $5; | IF LPAREN expression RPAREN statement ELSE statement $ = (TreeNode *) newNode(IfK); $->child0 = $3; $->child1 = $5; $->child2 = $7; ;if語(yǔ)句有通常的語(yǔ)義：表達(dá)式進(jìn)行計(jì)算；非0值引起第一條語(yǔ)句的執(zhí)行； 0值引起第二條語(yǔ)句的執(zhí)行，如果它存在的話。這個(gè)規(guī)則導(dǎo)致了典型的懸掛else二義性，可以用一種標(biāo)準(zhǔn)的方法

44、解決：else部分通常作為當(dāng)前i f的一個(gè)子結(jié)構(gòu)立即分析(“最近嵌套”非二義性規(guī)則)。iteration_stmt: WHILE LPAREN expression RPAREN statement $ = (TreeNode *) newNode(WhileK); $->child0 = $3; $->child1 = $5; ;while語(yǔ)句是C中唯一的重復(fù)語(yǔ)句。它重復(fù)執(zhí)行表達(dá)式，并且如果表達(dá)式的求值為非0，則執(zhí)行語(yǔ)句，當(dāng)表達(dá)式的值為0時(shí)結(jié)束。return_stmt: RETURN SEMI $ = (TreeNode *) newNode(ReturnK); | RETURN

45、 expression SEMI $ = (TreeNode *) newNode(ReturnK); $->child0 = $2; ;返回語(yǔ)句可以返回一個(gè)值也可無(wú)值返回。函數(shù)沒(méi)有說(shuō)明為void就必須返回一個(gè)值。函數(shù)聲明為void就沒(méi)有返回值。return引起控制返回調(diào)用者(如果它在main中，則程序結(jié)束)。expression: var ASSIGN expression $ = (TreeNode *) newNode(AssignK); $->child0 = $1; $->child1 = $3; | simple_expression $ = $1; ;var:

46、ID $ = (TreeNode *) newNode(IdK); $-> = (char *) copyString(lastid); | ID $<tnode>$ = (TreeNode *) newNode(IdK); $<tnode>$-> = (char *) copyString(lastid); LBRACK expression RBRACK $ = $<tnode>2; $->child0 = $4; ;表達(dá)式是一個(gè)變量引用，后面跟著賦值符號(hào)(等號(hào))和一個(gè)表達(dá)式，或者就是一個(gè)簡(jiǎn)單的表達(dá)式

47、。賦值有通常的存儲(chǔ)語(yǔ)義：找到由v a r表示的變量的地址，然后由賦值符右邊的子表達(dá)式進(jìn)行求值，子表達(dá)式的值存儲(chǔ)到給定的地址。這個(gè)值也作為整個(gè)表達(dá)式的值返回。v a r是簡(jiǎn)單的(整型)變量或下標(biāo)數(shù)組變量。負(fù)的下標(biāo)將引起程序停止(與C不同)。然而，不進(jìn)行下標(biāo)越界檢查。simple_expression: additive_expression relop additive_expression $ = (TreeNode *) newNode(OpK); $->attr.op = $2; $->child0 = $1; $->child1 = $3; | additive_exp

48、ression $ = $1; ;relop: EQ $ = EQ; | NOTEQ $ = NOTEQ; | LTEQ $ = LTEQ; | GTEQ $ = GTEQ; | LT $ = LT; | GT $ = GT; ;簡(jiǎn)單表達(dá)式由無(wú)結(jié)合的關(guān)系操作符組成(即無(wú)括號(hào)的表達(dá)式僅有一個(gè)關(guān)系操作符)。簡(jiǎn)單表達(dá)式在它不包含關(guān)系操作符時(shí)，其值是加法表達(dá)式的值，或者如果關(guān)系算式求值為t u r e，其值為1，求值為false時(shí)值為0。additive_expression: additive_expression addop term $ = (TreeNode *) newNode(OpK); $->attr.op = $2; $-