解析四則表達式的編譯過程及生成匯編代碼

1、前序
這是編譯原理的實驗，自認為是上大學以來做過的最難的一個實驗。
實驗用到的基礎知識：C語言、數據結構、匯編（只需簡單的了解）。
開發工具：VC

2、問題描述
編譯整數四則運算表達式，將整數四則運算表達式翻譯為匯編語言代碼。
消除左遞歸後的文法：
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文件

復制代碼 代碼如下:
#ifndef TEST_C
#define TEST_C
/**
* 全局變量和全局函數文件
**/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
/************************* 以下是全局變量(函數)的定義 *******************/
//輸入的表達式最大長度，可以看做是緩沖區的長度
#define MAX_EXPRESSION_LENGTH 50
//存放輸入的表達式
char expression[MAX_EXPRESSION_LENGTH];
//表達式字符數組的下標
int expression_index=0;
//存放一個單詞符號
char strToken[MAX_EXPRESSION_LENGTH/2];
//判斷是否是數字
int isNum(char * strToken)
{
int i=0;
while(strToken[i]){
if(!isdigit(strToken[i]))
break;
i++;
}
return strToken[i]==0;
}
//錯誤處理程序
void error(char* errerMessage)
{
printf("nERROR:%sn",errerMessage);
exit(0);
}
/************************* 以上是全局變量(函數)的定義 ******************/
#endif

4、詞法分析
詞法分析的要求是：接受一個表達式，輸出該表達式中的各類單詞符號
一般有兩種方法來進行詞法分析，一種是用狀態圖來實現，一種是用狀態轉換表。下面采用狀態圖實現
首先定義單詞符號的種類和所屬類型
typedef enum Symbol { ERR = -1, END, NUM, PLUS, MINUS, TIMES, SLASH, LPAREN, RPAREN } Symbol;

然後轉態轉換圖如下所示：

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

復制代碼 代碼如下:
#ifndef TEST1_C
#define TEST1_C
/**
* 采用狀態圖進行詞法分析以及測試詞法分析
*
**/
#include"test.c"
//枚舉類型
typedef enum Symbol { ERR = -1, END, NUM, PLUS, MINUS, TIMES,
SLASH, LPAREN, RPAREN } Symbol;
//獲取一個單詞符號，該單詞符號存放在strToken中。返回該單詞符號的枚舉類型
Symbol getToken();
//根據傳入的枚舉類型輸出對應的單詞符號
void printToken(Symbol i);
//測試詞法分析
void testLexAnalyse();
//獲取一個單詞符號，該單詞符號存放在strToken中。返回該單詞符號的枚舉類型
Symbol getToken()
{
char ch;
int state=0;//每次都是從狀態0開始
int j=0;
//表達式遍歷完成，單詞符號為'#'
if(expression[expression_index]==''){
strToken[0]='#';
strToken[1]='';
return END;
}
while(1){
switch(state){
case 0:
//讀取一個字符
ch=strToken[j++]=expression[expression_index++];
if(isspace(ch)){
j--;//注意退格
state=0;
}
else if(isdigit(ch))
state=1;
else if(ch=='+')
state=2;
else if(ch=='-')
state=3;
else if(ch=='*')
state=4;
else if(ch=='/')
state=5;
else if(ch=='(')
state=6;
else if(ch==')')
state=7;
else
return ERR;
break;
case 1:
ch=strToken[j++]=expression[expression_index++];
if(isdigit(ch))
state=1;
else{
expression_index--;
strToken[--j]=0;
return NUM;
}
break;
case 2:
strToken[j]=0;
return PLUS;
case 3:
strToken[j]=0;
return MINUS;
case 4:
strToken[j]=0;
return TIMES;
case 5:
strToken[j]=0;
return SLASH;
case 6:
strToken[j]=0;
return LPAREN;
case 7:
strToken[j]=0;
return RPAREN;
}
}
}
//根據傳入的枚舉類型輸出對應的單詞符號
void printToken(Symbol i){
switch(i){
case -1:printf("ERRn");break;
case 0:printf("ENDn");break;
case 1:printf("NUM %sn",strToken);break;
case 2:printf("PLUS %sn",strToken);break;
case 3:printf("MINUS %sn",strToken);break;
case 4:printf("TIMES %sn",strToken);break;
case 5:printf("SLASH %sn",strToken);break;
case 6:printf("LPAREN %sn",strToken);break;
case 7:printf("RPAREN %sn",strToken);break;
}
}
//測試詞法分析
void testLexAnalyse()
{
Symbol tokenStyle;//單詞符號類型
expression_index=0;
puts("n詞法分析結果如下：");
while(1){
tokenStyle=getToken();
printToken(tokenStyle);
if(tokenStyle == ERR){
error("詞法分析錯誤!");
}
if(tokenStyle == END){
break;
}
}
}

//主函數
int main()
{
gets(expression);
testLexAnalyse();
return 0;
}

#endif

運行結果


5、語法分析
要求：接受一個表達式，分析該表達式，並根據輸入正確與否給出相應信息
主要是根據無左遞歸文法寫出對應的各個子程序
test2.c

復制代碼 代碼如下:
#ifndef TEST_2
#define TEST_2
/**
* 語法分析以及測試語法分析
**/
#include"test1.c"
/*
消除左遞歸後的文法：
E→TE'
E'→+TE' |ε
T→FT'
T'→*FT' |ε
F→(E) | i
*/
//每個非終結符有對應的子程序函數聲明
void E();
void E1();
void T();
void T1();
void F();
//測試語法分析
void testSyntaxAnalyse();
//每個非終結符有對應的子程序
void E()
{
T();
E1();
}
void E1()
{
if(strcmp(strToken,"+")==0 || strcmp(strToken,"-")==0){
getToken();
T();
E1();
}
//Follow(E1)={#,)}
else if(strcmp(strToken,"#")!=0 && strcmp(strToken,")")!=0){
error("語法分析錯誤!");
}
}
void T()
{
F();
T1();
}
void T1()
{
if(strcmp(strToken,"*")==0 || strcmp(strToken,"/")==0){
getToken();
F();
T1();
}
//Follow(T1)={+,#,)}，如果考慮-號的話要加上-號
else if(strcmp(strToken,"-")!=0 &&strcmp(strToken,"+")!=0 && strcmp(strToken,"#")!=0 && strcmp(strToken,")")!=0){
error("語法分析錯誤!");
}
}<