編譯原理四則表達(dá)式試驗(yàn)

本文格式為Word版，下載可任意編輯——編譯原理四則表達(dá)式試驗(yàn)1、前序

這是編譯原理的試驗(yàn)，自認(rèn)為是上大學(xué)以來做過的最難的一個(gè)試驗(yàn)。所以寫篇博客記錄一下。

試驗(yàn)用到的基礎(chǔ)知識(shí)：C語言、數(shù)據(jù)結(jié)構(gòu)、匯編（只需簡(jiǎn)單的了解）。開發(fā)工具：VC

2、問題描述

編譯整數(shù)四則運(yùn)算表達(dá)式，將整數(shù)四則運(yùn)算表達(dá)式翻譯為匯編語言代碼。消除左遞歸后的文法：E→TE'E'→+TE'|εT→FT'T'→*FT'|ε

F→(E)|i

消除左遞歸后的翻譯模式：E::=T{E'.i:=T.nptr}E'{E.nptr:=E'.s}

E'::=+T{E'1.i:=mknode(‘+’,E'.i,T.nptr)}E'1{E'.s:=E1.s}

E'::=-T{E'1.i:=mknode(‘-’,E'.i,T.nptr)}E'1{E'.s:=E1.s}

E'::=ε{E'.s:=E'.i}T::=F{T'.i:=F.nptr}T'{T.nptr:=T'.s}

T'::=*F{T'1.i:=mknode(‘*’,T'.i,F.nptr)}T'1{T'.s:=T1.s}

T'::=/F{T'1.i:=mknode(‘/’,T'.i,F.nptr)}T'1{T'.s:=T1.s}T'::=ε{T'.s:=T'.i}F::=(E){F.nptr:=E.nptr}

F::=num{F.nptr:=mkleaf(num,num.val)}

3、全局定義

test.c文件

#ifndefTEST_C#defineTEST_C/**

*全局變量和全局函數(shù)文件**/

#include#include#include#include

/*************************以下是全局變量(函數(shù))的定義*******************/

//輸入的表達(dá)式最大長(zhǎng)度，可以看做是緩沖區(qū)的長(zhǎng)度#defineMAX_EXPRESSION_LENGTH50

//存放輸入的表達(dá)式

charexpression[MAX_EXPRESSION_LENGTH];

//表達(dá)式字符數(shù)組的下標(biāo)intexpression_index=0;

//存放一個(gè)單詞符號(hào)

charstrToken[MAX_EXPRESSION_LENGTH/2];

//判斷是否是數(shù)字

intisNum(char*strToken){

inti=0;

while(strToken[i]){}

returnstrToken[i]==0;

2

if(!isdigit(strToken[i]))i++;

break;

}

//錯(cuò)誤處理程序

voiderror(char*errerMessage){

printf(\exit(0);

}

/*************************以上是全局變量(函數(shù))的定義******************/#endif

4、詞法分析

詞法分析的要求是：接受一個(gè)表達(dá)式，輸出該表達(dá)式中的各類單詞符號(hào)

一般有兩種方法來進(jìn)行詞法分析，一種是用狀態(tài)圖來實(shí)現(xiàn)，一種是用狀態(tài)轉(zhuǎn)換表。下面采用狀態(tài)圖實(shí)現(xiàn)

首先定義單詞符號(hào)的種類和所屬類型

typedefenumSymbol{ERR=-1,END,NUM,PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN}Symbol;

然后轉(zhuǎn)態(tài)轉(zhuǎn)換圖如下所示：

3

test1.c文件用代碼表示如下：

#ifndefTEST1_C#defineTEST1_C/**

*采用狀態(tài)圖進(jìn)行詞法分析以及測(cè)試詞法分析***/

#include\

//枚舉類型

typedefenumSymbol{ERR=-1,END,NUM,PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN}Symbol;

//獲取一個(gè)單詞符號(hào)，該單詞符號(hào)存放在strToken中。返回該單詞符號(hào)的枚舉類型

SymbolgetToken();

//根據(jù)傳入的枚舉類型輸出對(duì)應(yīng)的單詞符號(hào)voidprintToken(Symboli);

//測(cè)試詞法分析

voidtestLexAnalyse();

//獲取一個(gè)單詞符號(hào)，該單詞符號(hào)存放在strToken中。返回該單詞符號(hào)的枚舉類型

SymbolgetToken(){

charch;

intstate=0;//每次都是從狀態(tài)0開始intj=0;

//表達(dá)式遍歷完成，單詞符號(hào)為'#'

if(expression[expression_index]=='\\0'){

strToken[0]='#';strToken[1]='\\0';

returnEND;

4

}

while(1){

switch(state){

case0:

//讀取一個(gè)字符

ch=strToken[j++]=expression[expression_index++];

if(isspace(ch)){j--;//注意退格}

elseif(isdigit(ch))state=1;elseif(ch=='+')elsebreak;

returnERR;state=2;state=3;state=4;state=5;state=6;state=7;

elseif(ch=='-')

elseif(ch=='*')elseif(ch=='/')elseif(ch=='(')elseif(ch==')')

state=0;

case1:

ch=strToken[j++]=exp