当文法中存在A->…BD…时,LA(B)>D且LA(B)>FA(D)
3.5.2分析表结构
分析表采用二维数组存储方式,文法中的每一个符号对应数组a中的一个位置,
而a[i][j]代表第i个和第j个的优先关系:
(1)a[i][i]=0 无优先关系
(2)a[i][i]=1 i对应元素优先级小于j的
(3)a[i][i]=2 i对应元素优先级大于j的
(4)a[i][i]=3 i对应元素优先级等于j的
而在分析过程中规约产生式的选择则在语法分析过程中,在语法分析过程中实现。
分析表最终结果如下:
intanltable[22][22]={
/*S*/ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2},
/*if*/{0,0,3,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*E*/ {0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*then*/{0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
/*B*/ {0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2},
/*else*/{0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
/*(*/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*)*/
{0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*>*/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*<*/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*=*/
{0,0,0,0,0,0,0,0,0,0,0,1,1,1,3,0,0,0,0,0,0,0},
/*A*/
{0,0,0,0,0,0,0,3,3,3,0,0,0,0,0,0,2,3,3,3,3,0},
/*d*/
{0,0,0,0,0,0,0,2,2,2,3,0,0,0,0,0,2,2,2,2,2,0},
/*num*/{0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,0,2,2,2,2,2,0},
/*C*/
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0},
/*{*/
{0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0},
/*}*/
{0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2},
/*+*/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*_*/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/***/
{0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*/*/ {0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0},
/*#*/ {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
};//0-error,1=<,2=>,3==
4中间代码形式描述及结构设计
四元式是一种比较普遍采用的中间代码形式。
四元式的四个组成成分是:
算符op,第一和第二运算对象ARG1和ARG2及运算结果RESULT。
运算对象和运算结果有时指用户自己定义的变量,有时指编译程序引进的临时变量。
例如:
a=b*c+b*d的四元式表示如下:
(1)(*,b,c,t1)
(2)(*,b,d,t2)
(3)(+,t1,t2,t3)
(4)(=,t3,-,a)
四元式和三元式的主要不同在于,四元式对中间结果的引用必须通过给定的名字,而三元式是通过产生中间结果的三元式编号。
也就是说,四元式之间的联系是通过临时变量实现的。
5编译系统的概要设计
(1)系统主要分为两个模块:
词法分析和语法分析(包括语义分析)。
并且在分析过程中将词法分析产生的单词输出到文件,语法分析过程中分析栈的变化情况输出到文件。
(2)系统设计采用过程化的设计方法,将词法分析、语法分析等功能模块在独立的过程中实现。
(3)系统概要结构如下:
1)预定义模块
2)词法分析模块
3)语法分析模块
4)其他辅助模块
主程序
5)主程序模块(主要指程序入口函数main())各模块调用关系如下:
预定义
词法分析
语法分析
其他辅助模块
6算法描述
6.1预定义模块
预定义模块主要包括宏定义、常量定义、类型定义以及全局变量定义等。
具体如下:
(1)宏定义
#defineOK1//正常#defineERROR-1//出错
#defineFAILURE-1//分析失败
(2)类型定义
structatt
{//名字表类型stringsname;charselect;charaddre;
};
typedefstructSqStack
{
char *base;
char *top;
int stacksize;
}SqStack;//栈定义
(3)全局变量
intlineno=1;//输出时的当前行号charch;//当前字符
charallname[30][30];//单词全名charout[30][30];//保存单词简称attattname[40];//名字表
(4)优先关系表初始化(见3.5.2)
6.2词法分析
词法分析主要为analysis(ifstream&fin,ofstream&fout)函数,其中fin为输入文件流,fout为单词输出文件流。
辅助函数为judge(char*string),判断单词是否为关键字。
分析算法如下描述:
while(true)
武汉理工大学《编译原理》课程设计说明书
{
字符串存放临时数组temp;if(到文件末尾)break;读取一个字符到ch;
if(ch是换行){lineno+=1;}elseif(ch是字符)
{
while(ch是字符或数字)
{
ch存入temp;
读取下一个字符;
}
判断temp是否为关键字,并根据判断结果使temp入名字表并设置正确
的属性。
}
elseif(ch是数字)
{
while(ch是数字)
{
ch存入temp;
读取下一个字符;
}
temp入名字表并设置正确的属性。
}
elseif(ch为其他合法字符(如:
>,<,=等等))填入名字表。
else输出错误,无法识别的字符。
}
6.3语法分析
语法分析主要为laynax(ofstream&f)函数,其中,f为栈变化情况输出文件。
其他辅助函数为除judge(char*string)外的其他所有辅助函数。
语法分析的过称描述如下:
初始化分析栈;
while(还有单词)
{
判断当前栈顶单词与输入单词的优先级;
if(<||=)当前符号入栈
elseif(>)
{
while(栈顶元素优先级等于输入单词)
{
保存输入单词;
置输入单词为栈顶单词;栈顶元素出栈;
}
12
判断保存单词串是否为句柄;
if(是句柄)
{
进行规约;
进行语义规则计算;输出栈的变化情况;
使规约后单词为新的输入符号;
}
else
{
输出规约出错;
}
}
else
{
输出输入单词错误;
}
}
6.4其他模块
其他模块描述如下:
(1)栈操作模块
voidInitStack(SqStack&S)
{//栈初始化
S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));//分配存储空
间
if(!
S.base)
exit(OVERFLOW); //为栈S分配存储空间失败S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
intpush(SqStack&S,charch)//将元素e插入到栈S中,成为新的栈顶元素
{
if(S.top-S.base>S.stacksize) //判定栈是否满
{
S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT
*sizeof(char)));
if(!
S.base)
{
printf("分配存储单元失败.\n"); //存储单元分配失败exit(OVERFLOW);
}
S.top=S.base+S.stacksize; //指明栈顶指针的基址S.stacksize+=STACKINCREMENT;//指明栈的空间大小
武汉理工大学《编译原理》课程设计说明书
*S.top++=ch; //先将e送入栈顶指针所指向的单元,再将栈顶指针加return(OK);
}
intpop(SqStack&S,char&ch)
{//栈顶元素出栈if(S.top==S.base)
{
printf("溢出");
return(ERROR);
}
ch=*--S.top;return(OK);
}
chargettop(SqStackS)
{//返回栈顶元素
if(S.top==S.base)cout<<"栈空,出错"<e=*(S.top-1);
returne;
}
voidprintstack(SqStack&S,intnaa,intty,ofstream&fout)
{//输出栈当前情况
chartemp[40][20];for(intk=0;k<40;k++)
{
for(intt=0;t<20;t++)temp[k][t]=NULL;
}
intte=0;inti=0,j=0;intnu=0;char*ku;ku=S.base;i=naa+1;
char*contrl;contrl=S.base;while(contrl!
=S.top)
{
if(*contrl!
='1')
{
if(*contrl=='i')
{fout<<"if";nu=nu+2;}elseif(*contrl=='t')
19
{fout<<"then";nu=nu+4;}elseif(*contrl=='e')
{fout<<"else";nu=nu+4;}else
{fout<<*contrl;nu++;}
}
contrl++;
}
fout<<"\t\t\t";for(i;i<=length;i++)
{
if(gettop(S)=='S')fout<<"#";
else
fout<}
if(gettop(S)=='S')fout<<"#";
else
fout<fout<}
(2)其他
intgetnum(charcc)
{//返回元素在优先表中的位置
switch(cc)
{
case'S':
return0;break;case'i':
return1;break;case'E':
return2;break;case't':
return3;break;case'B':
return4;break;case'e':
return5;break;case'(':
return6;break;case')':
return7;break;case'>':
return8;break;case'<':
return9;break;case'=':
return10;break;case'A':
return11;break;case'd':
return12;break;case'n':
return13;break;case'C':
return14;break;case'{':
return15;break;case'}':
return16;break;case'+':
return17;break;case'-':
return18;break;case'*':
return19;break;case'/':
return20;break;case'#':
return21;break;default:
return88;
}
}
intjudge(char*string)
{//判断是否是关键字
char*keywords[1000]={"if","then","else"};for(inti=0;i<=2;i++)
{
if(!
strcmp(string,*(keywords+i)))
{
return1;
}
}
return0;
}
6.5主程序
主程序主要负责,用户界面的初始化,以及程序执行控制。
程序如下:
intmain()
{
inttest=0;
cout<<"============================================================
==================="<cout<<"= IF-ELSE条件语句的翻译程序设计(简单优先法、输出四元式) ="<cout<<"============================================================
==================="<charinFile[100],wordOutFile[100],stackFile[100];ifstream*fin;
ofstream*wordOut,*stackOut;while(true)
{
printf("输入源文件名(包括路径):
");
cin>>inFile;
fin=newifstream(inFile);if(fin==NULL)
{
printf("输入源文件名错误!
\n");
continue;
}
break;
}
while(true)
{
printf("输入单词输出文件(包括路径):
");
cin>>wordOutFile;
wordOut=newofstream(wordOutFile);if(wordOut==NULL)
{
printf("输入文件名错误!
\n");
continue;
}
break;
}
while(true)
{
printf("输入栈情况输出文件(包括路径):
");
cin>>stackFile;
stackOut=newofstream(stackFile);if(stackOut==NULL)
{
printf("输入文件名错误!
\n");
continue;
}
break;
}
getchar();
test=analysis(*fin,*wordOut);if(test==1)
{
test=laynax(*stackOut);
}
else
return0;if(test==1)
{
printfou();
}
return0;
}
7测试方法和结果
7.1测试方法
(1)程序设计过程中采用单步测试的方法,每完成一个独立的功能模块则对其进行单独测试。
各模块测试成功之后,则对程