語法分析源代碼分析報告.doc

《語法分析源代碼分析報告.doc》由會員分享，可在線閱讀，更多相關《語法分析源代碼分析報告.doc（10頁珍藏版）》請在裝配圖網上搜索。

語法分析源代碼分析報告 學生：吳藝萍、陳璐、崔旻、劉超群 學號：095 、 094 、 101、103 時間：2014年06月 —————————————————————————————————— 目錄 一、概述.............................................................................................................................................1 二、詞法分析設計與實現.................................................................................................................1 1、相關枚舉類型的定義...........................................................................................................1 2、函數......................................................................................................................................2 三、語法、語義分析設計與實現.......................................................................................................3 1、相關數據結構定義..............................................................................................................3 2、函數.......................................................................................................................................3 四、中間代碼.....................................................................................................................................6 1、相關數據結構定義...............................................................................................................6 2、相關枚舉類型的定義...........................................................................................................6 3、函數.......................................................................................................................................7 一、概述 編譯原理是在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優(yōu)化和目標代碼生成。現在計算機系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼。在現代計算機體系結構的研究中，在處理器的設計階段就開發(fā)編譯器，并將編譯生成的代碼在模擬器上運行，以評價擬采用體系結構的特征。編譯器技術影響計算機體系結構設計的一個著名例子是精簡指令集計算機（RISC）的發(fā)明。 二、詞法分析 1、相關枚舉類型定義 (1）SymType的定義 //記號類型 enum SymType { OR , //或 AND, //與 RELOP, //關系運算符 ADDOP, //加減 MULOP, //乘除 NOT, //非 LP, //左括號 1 RP, //右括號 ID, //標志符 NUM, //數 ASSIGN, //賦值 LB, //左大括號 RB, //右大括號 COMMA, //逗號 SEMICOLON, //分號 UNDEFINED, //未定義 INT, //int IF, //if ELSE, //else WHILE, //while RETURN, //return PRINTF, //printf SCANF, //scanf} // （2）AddOp、MulOp、RelType的定義 次枚舉類型確定了加減乘除運算和關系運算符的符號 enum AddOp{ ADD, //加法 SUB //減法 }; // enum MulOp{ MUL, //乘法 DIV, //除法 MOD, //取余 }; //關系運算符類型 enum RelType{ GT, //大于 > GE, //大于等于 >= EQ, //等于 == LT, //小于 < LE, //小于等于 <= NE, //不等于 != NR //沒有關系 用于優(yōu)先關系表 }; 2、函數 用char * types[]、static char * keywords[KeyWordsCount] (關鍵字) 、static int keyType[KeyWordsCount] (關鍵字對應類別）來申明輸入的字符串中詞語的特定意義，即詞 2 法。根據一下函數來 函數 作用 static int isDigit(char ch); 判斷現在的token是否為數值 static int isLetter(char ch) 判斷現在的token是否為字母 static int getKeyWord(char * str); 獲取現有的token的關鍵字 void getToken(); 取得當前的token進行判斷 識別詞義。組成了詞法分析的功能。 三、語法、語義分析設計與實現 1、相關數據結構的定義 (1）ExprNode的定義. 用來記錄數據存儲的位置 //表達式(采用C的風格，非0為真，0為假) typedef struct { int truelist; //真出口鏈 int falselist; //假出口鏈 int address; //存放表達式值的地址或常量的值 //若為負數，則存放全局變量的地址 //若為正數，則為局部變量的相對地址 bool isTemp; //是否為臨時變量 }ExprNode; (2）SymbolEntry的定義 //符號表表項 typedef struct { int type; //類型FUN 或VAR int address; //地址全局為非正 局部為正 char lexeme[MaxIdLen+1]; //詞素，變量名或函數名 int paramCount; //函數的參數個數 }SymbolEntry; (3）SymbolTable的定義 該數據結構的作用是用來記錄已存在的變量，關聯到相關的存儲位置，還有防止重名 struct SymbolTable{ SymbolEntry * entries; //各表項 int index; //符號表當前表尾的下標，表中第項不用 }; 2、函數 這里采用的是四元式形式的中間代碼。另外還需要實現一個虛擬機來解釋執(zhí)行編譯后 3 的中間代碼。語法定義并未采用文法的形式，而是采用語法圖的直觀形式，語法圖和文法相比具有更易于理解的優(yōu)點。這里是用采用自頂向下的遞歸下降分析方法[2]，它也是基于語法圖進行分析的。下圖由橢圓和圓形代表的其實是語法圖對應文法的終結符，矩形方框代表的是相應文法的非終結符。下圖規(guī)定了合法的程序的“程序體”應具有什么樣的語法形式，此處“程序體”的概念顯然是語法圖對應文法的開始符號。下圖很直觀地給出了語言是由函數的定義和全局變量的聲明所構成。全局變量可以只聲明而不進行初始化，也可在聲明的時侯進行初始化，還可以同時聲明多個全局變量。全局變量與函數的聲明可以交替進行。 通過以下函數實現statement的語法 函數 作用 static void inputValue(); 輸入 static void outputExprValue(); 輸出 static int ifStatement() if語句 static int assignStatement(); 賦值語句 static int whileStatement(); while語句 static int printfStatement() 打印語句 static int scanfStatement(); 輸出語句 static int returnStatement(); return語句 static int compoundStatement(); 復合語句 static void callStatement(char * func); 函數調用 void callExpr(char * func) bool isStatementStarting(int tok); tok是否為語句開始記號 bool isExpressionStarting(int tok) ok是否為表達式開始記號下圖很直觀地給出語言的 statement: )> ( statement else statement expression if )> ( while statement expression ) ( ; print expression , ; }﹛﹜﹛﹜ statement {﹛﹜﹛﹜ expression = id ; 在paramDeclare.cpp中通過以下函數實現變量申明definition 4 函數 作用 static void processOneDeclare() 處理一個聲明 int paramDeclare() 申明 并在varDeclare.cpp中處理變量和對變量列表的內容進行處理： 函數 作用 void processOneVar() 處理一個變量 void varDeclare() 處理變量列表 definition: expression ; int id = 在expression.cpp中 通過ExprNode expression()函數來實現expression ExprNode expression(){ ExprNode left = andTerm(); while(token == OR){ changeArithToCondition(&left); getToken(); backpatch(left.falselist,csIndex); ExprNode right = andTerm(); changeArithToCondition(&right); left.truelist = mergeList(left.truelist,right.truelist); left.falselist = right.falselist; } return left; } expression: term term || 函數 作用 static ExprNode andTerm(); 與項 static ExprNode relationTerm(); 關系項 static ExprNode addTerm(); 和項 static ExprNode mulTerm(); 乘項 static ExprNode factor(); 因子 int mergeList(int list1, int list2); 合并鏈表 void backpatch(int list, int cx); 回填鏈表 ExprNode expression(); 表達式 用以上的函數實現expression中的加減乘除以及關系運算 四、中間代碼生成器 1、數據結構定義 (1）Instruction的定義 此處用四元式形式作為中間代碼，此數據結構來記錄中間代碼 typedef struct { int optr; //運算符 int arg1; //左操作數的地址 int arg2; //右操作數的地址 int result; //存放結果的地址 }Instruction; 2、枚舉類型定義 (1）InstrType的定義 此枚舉類型出現在四則運算的運算符，為了之后的數據運算 //虛擬機指令集 enum InstrType{ InsJtrue, //為真則跳轉 (InsJtrue, arg1, , dest) InsJfalse, //為假則跳轉 (InsJfalse,arg1, , dest) InsJmp, //無條件跳轉 (InsJmp, , , dest) InsMov, //數據復制 (InsMov, arg1, ,dest) InsInit, //初始化某單元 (InsInit,arg1,num, ) InsAdd, //加法 (InsAdd, arg1,arg2,dest) InsSub, //減法 (InsSub, arg1,arg2,dest) InsMul, //乘法 (InsMul, arg1,arg2,dest) InsDiv, //除法 (InsDiv, arg1,arg2,dest) InsMod, //取余 InsNop, //空操作 (InsNop, , , ) InsJlt, //判斷是否< (InsLt,arg1,arg2,result) InsJle, //判斷是否<= (InsLe,arg1,arg2,result) 2 InsJgt, //判斷是否> (InsGt,arg1,arg2,result) InsJge, //判斷是否>= InsJeq, //判斷是否== InsJne, //判斷是否!= InsOr, //邏輯或運算 6 InsAnd, //邏輯與運算 InsNot, //邏輯非運算 InsIn, //讀入一個整數到單元dest (InsIn,dest , ,); InsOut, //輸出一個整數 (InsOut,num, ,); InsUminus, //負數 (InsUminus,oprn, ,dest) InsCall, //過程調用 (InsCall,des, , ,); InsRet, //過程返回 (InsRet,expr, , ); InsSetBx, //設置bx指針，指向活動記錄首地址(InsSetBx,addr, , ) InsAddBx, //bx指針增加 (InsSetBx,addr); }; 3、函數 通過virtualMachine.cpp來實現中間代碼的生成和實現，具體通過以下2個函數 函數 作用 static int getAddress(int offset); 由活動記錄內的偏移來求"變量的地址" void interpret() 具體情況的實現 7