编译原理四则表达式试验

本文格式为Word版，下载可任意编辑——编译原理四则表达式试验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文件

#ifndefTEST_C#defineTEST_C/**

*全局变量和全局函数文件**/

#include#include#include#include

/*************************以下是全局变量(函数)的定义*******************/

//输入的表达式最大长度，可以看做是缓冲区的长度#defineMAX_EXPRESSION_LENGTH50

//存放输入的表达式

charexpression[MAX_EXPRESSION_LENGTH];

//表达式字符数组的下标intexpression_index=0;

//存放一个单词符号

charstrToken[MAX_EXPRESSION_LENGTH/2];

//判断是否是数字

intisNum(char*strToken){

inti=0;

while(strToken[i]){}

returnstrToken[i]==0;

2

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

break;

}

//错误处理程序

voiderror(char*errerMessage){

printf(\exit(0);

}

/*************************以上是全局变量(函数)的定义******************/#endif

4、词法分析

词法分析的要求是：接受一个表达式，输出该表达式中的各类单词符号

一般有两种方法来进行词法分析，一种是用状态图来实现，一种是用状态转换表。下面采用状态图实现

首先定义单词符号的种类和所属类型

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

然后转态转换图如下所示：

3

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

#ifndefTEST1_C#defineTEST1_C/**

*采用状态图进行词法分析以及测试词法分析***/

#include\

//枚举类型

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

//获取一个单词符号，该单词符号存放在strToken中。返回该单词符号的枚举类型

SymbolgetToken();

//根据传入的枚举类型输出对应的单词符号voidprintToken(Symboli);

//测试词法分析

voidtestLexAnalyse();

//获取一个单词符号，该单词符号存放在strToken中。返回该单词符号的枚举类型

SymbolgetToken(){

charch;

intstate=0;//每次都是从状态0开始intj=0;

//表达式遍历完成，单词符号为'#'

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

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

returnEND;

4

}

while(1){

switch(state){

case0:

//读取一个字符

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