编译技术

班 级 网络 0802 学 号

姓 名 叶晨舟 指导老师 朱 玉 全

2011年 7 月 4 日

一、目的

编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。

二、任务及要求

基本要求：

1．词法分析器 产生下述小语言的单词序列

这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：

对于这个小语言，有几点重要的限制：

首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的：

IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。

再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为

IF i>0 i= 1; 而绝对不要写成

IFi>0 i=1;

因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。

这个小语言的单词符号的状态转换图，如下图：

2．语法分析器 能识别由加+ 减- 乘* 除/ 乘方^ 括号（）操作数所组成的

算术表达式，其文法如下：

E→E+T|E-T|T T→T*F|T/F|F F→P^F|P p→(E)|i

使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；

LR分析法等。

3．中间代码生成器 产生上述算术表达式的中间代码（四元式序列）

三、实现过程

给出各题目的详细算法描述，数据结构和函数说明，流程图。

1、词法分析器的流程图

2、语法分析器主程序图

3、中间代码生成器流程图：

四、源程序

词法分析器:

#include<string.h> #include<malloc.h>

#include<iostream> using namespace std;

typedef struct table //分析表存储结构 {

char m[100]; }table;

table M[100][100]; //定义分析表

typedef struct stacknode //定义栈内元素节点 (带头结点（为空）的) {

char data;

struct stacknode *next; }stackk;

void initlink(stackk *&s) //初始化新栈 {

s=(stackk *)malloc(sizeof(stackk)); s->next=NULL; }

void poplink(stackk *&s) //顶元素出栈 {

stackk *p;char v;

if(s->next!=NULL) {

p=s->next;

v=p->data; s->next=p->next; } free(p); }

void pushlink(stackk *&s,char x) //新 元 素 入 栈 {

stackk *p;

p=(stackk *)malloc(sizeof(stackk)); p->data=x;

p->next=s->next; s->next=p; }

void display(stackk *s) //打印 现实显示 栈内元素 {

int i=0,j; char st[100]; p=s->next;

while(p!=NULL) {

st[i++]=p->data; p=p->next; } for(j=i-1;j>=0;j--) printf("%c",st[j]);

for(j=0;j<16-i;j++) //打印 对齐格式 printf("%c",' '); }

char gettop(stackk *s) //返 回 栈 顶 元 素 值 {

if(s->next==NULL) return 0; else

return s->next->data; }

int find(char c,char array[]) //查找函数， { int i;

int flag=0;

for(i=0;i<100;i++) {

if(c==array[i]) flag=1; }

return flag; }

int location(char c,char array[]) //定位函数,指出字符所在位置 { int i;

for(i=0;i<100;i++) {

if(c==array[i])

} }

void error() //出错函数定义 {

printf("%15c出错!\n",' '); }

void analyse(char Vn[],char Vt[]) {

int i,j,m,p,q,length,t,h; char w,X; char str[100]; opt0:

scanf("%s",str);

for(i=0;i<strlen(str);i++) {

if(!find(str[i],Vt)) {

printf("输入字符串有误!请重新输入!"); goto opt0; break; } }

stackk *st; initlink(st);

pushlink(st,'#'); pushlink(st,Vn[0]); //#与识别符号入栈 j=0;

h=1; w=str[0];

printf("步骤%-12c分析栈%-24c剩余输入串%-12c所用产生式\n",' ',' ',' '); opt1:

printf("%-16d",h); //显示步骤 h++;

display(st); //显示分析栈中内容 X=gettop(st); //上托栈顶符号放入X poplink(st);

for(int k=0;k<14+j;k++) //打印对齐格式

printf("%c",' ');

for(t=j;t<strlen(str);t++)

{

printf("%c",str[t]); //显示剩余字符串 }

if(find(X,Vt)&& X!='#') //分析栈的栈顶元素和剩余输入串的第一个元素相比较 {

if(X==w) { printf("%15c匹配\n",X); j++; w=str[j]; goto opt1; } else

error(); } else {

if(X=='#') {

if(X==w) {

printf("%8c是该文法的句子！\n",' '); } else

error(); } else {

p=location(X,Vn); q=location(w,Vt);

char *S1="null",*S2="NULL";

if(strcmp(M[p][q].m,S1)==0||strcmp(M[p][q].m,S2)==0) //查找产生式 error(); else

{

char str0[100];

strcpy(str0,M[p][q].m);

printf("%15c-->%s\n",X,str0); //显示对应的产生式 if(strcmp(str0,"$")==0) goto opt1; else {

length=strlen(str0); //逆序进栈 for(m=length-1;m>=0;m--) {

pushlink(st,str0[m]); }

goto opt1; } } } } }

int main() {

int i,k,n,r;

char Vn[100],Vt[100],select;

printf("******************************************************************\n"); printf("对任意输入LL(1)文法的分析表，判断验证字符串是否为该文法的句子 \n"); printf("并能给出分析和演示过程。 \n");

printf("******************************************************************\n"); opt2:

printf("请输入各终结符（#号表示结束 ）Vt[i]:\n"); for(i=0;i<100;i++) {

scanf("%c",&Vt[i]); if(Vt[i]=='#') {

r=i; break; } }

printf("请输入非终结符个数:\n"); scanf("%d",&n); getchar();

for (i=0;i<n;i++) {

printf("请输入非终结符Vn[%d]:\n",i); scanf("%c",&Vn[i]); getchar();

printf("请输入此非终结符对应各终结符的产生式右部(null或NULL表示出错;$表示空串):\n");

for(k=0;k<=r;k++) {

scanf("%s",M[i][k].m); getchar(); } } opt3:

printf("请输入要分析的字符串，且以#结束:\n"); analyse(Vn, Vt);

printf("********************请选择***********************\n"); printf(" 1: 输入字符串 \n"); printf(" 2: 输入新分析表 \n"); printf(" 0: 退 出 \n"); printf("*************************************************\n"); opt4: cin>>select; switch(select) {

case '1': {goto opt3;break;} case '2': {goto opt2;} case '0': {break;}

default: {printf("输入错误!请重新选择:"); goto opt4; break;} }

return 0; }

运行结果：

语法分析器 源程序：

#include<string.h> #include<iostream> using namespace std; char prog[100],token[10]; char ch;

int syn,p,m=0,n,row,sum=0;

char *rwtab[20]={"dim","if","do","stop","end" ,"and","begin","bool","case","char", "false","for","int","not","or","set","then","true","until","while" };

void scaner() { for(n=0;n<9;n++) token[n]=NULL; ch=prog[p++]; while(ch==' ') { ch=prog[p]; p++; } if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))

{ m=0; while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { token[m++]=ch; ch=prog[p++]; } token[m++]='\0'; p--; syn=21; for(n=0;n<20;n++) { if(strcmp(token,rwtab[n])==0) { syn=n+1; break; } } } else if((ch>='0'&&ch<='9')) { { sum=0; while((ch>='0'&&ch<='9')) { sum=sum*10+ch-'0'; ch=prog[p++]; } } p--; syn=7+15; if(sum>32767) syn=-1; } else switch(ch) {

case'=':syn=8+15;token[0]=ch;break; case'+':syn=9+15;token[0]=ch;break; case'*': m=0; token[m++]=ch; ch=prog[p++]; if(ch=='*') {

syn=11+15; token[m++]=ch; } else { syn=10+15; p--; }

break;

case',':syn=12+15;token[0]=ch;break; case'(':syn=13+15;token[0]=ch;break; case')':syn=14+15;token[0]=ch;break; case'#':syn=0;token[0]=ch;break; case'<':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='>') { syn=17+15; token[m++]=ch; } else if(ch=='=') { syn=16+15; token[m++]=ch; } else { syn=15+15; p--; } break;

case'>':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=19+15; token[m++]=ch; } else { syn=18+15; p--;

} break;

case':':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=21+15; token[m++]=ch; } else { syn=20+15; p--; } break;

case'/':syn=22+15;token[0]=ch;break; case'-':syn=23+15;token[0]=ch;break; case';':syn=24+15;token[0]=ch;break; default: syn=-1;break; } }

void main() { p=0; row=1; cout<<endl<<endl<<endl; cout<<"***************************小型词法**********************************"<<endl<<endl; cout<<"请输入一段程序（以#结束）:"; do { cin.get(ch); prog[p++]=ch; } while(ch!='#'); p=0; cout<<endl<<"**************************词法分析*********************************"<<endl; cout<<" 种别编码 自身值"<<endl; do { scaner(); switch(syn)

分析结果如器

下

{ case 22 : cout<<" ("<<syn<<" , "<<sum<<")"<<endl; break; case -1: cout<< " Error in row"<<row<<"!"<<endl; break;

default: cout<<" ("<<syn<<" , "<<token<<")"<<endl;break; } } while (syn!=0); }

运行结果：

}

中间代码生成器源程序：

表达式生成四元式 递归子程序法

#include<string> #include <iostream> using namespace std;

#define DEFAULT_SIZE 100

char EMachine(char w); //表达式E的自动机 char TMachine(char w); //表达式T的自动机 char FMachine(char w); //表达式F的自动机 bool ZMachine(); //表达式Z的自动机 string intToString(int a); //整形变成字符串形函数

class stack //栈类定义 {

private: int top;

string *stacka; int maxsize; public:

stack(int size=DEFAULT_SIZE); ~stack(){ delete [] stacka; } void push(const string &item); string pop(void);

string gettop(void) const ;

bool empty(void) const { return (top==-1); }

bool full(void) const { return (top==maxsize-1); } void clear(void) { top=-1; } };

stack::stack(int size) //栈类的构造函数 {

top=-1;

maxsize=size;

stacka=new string[maxsize]; if(!stacka) {

cerr<<"allocate memory failed."<<endl; exit(1); } }

void stack::push(const string &item) //压栈操作 {

if(full()) {

cerr<<"stack full, cannot push."<<endl; return; }

top++;

stacka[top]=item; }

string stack::pop(void) //出栈操作 {

if(empty()) {

cerr<<"stack empty, cannot pop."<<endl; exit(1) ; }

string item=stacka[top]; top--;

return item; }

string stack::gettop(void) const //取栈顶操作 {

if(empty()) {

cerr<<"stack empty, cannot gettop."<<endl; exit(1) ; }

return stacka[top]; }

static stack wordStack; //符号栈 static int noOfQuet=0; //静态四元式个数记录 static int noOfT = 1; //静态状态个数记录

void main(){ //主函数 char yesOrNo; //进行一个循环操作控制 do{ cout<<"请输入算术表达式："<<endl; noOfT = 1; //每次结束询问 ZMachine(); cout<<endl<<"Continue?Yes or Not:"; cin>>yesOrNo; //输入“Y”则继续 }while(yesOrNo=='y'); //否则程序结束 }

bool ZMachine(){ //Z自动机 char w; cin>>w; w = EMachine(w); //调用E自动机

if(w=='#'){ //遇到“#”则结束 return true; } else{ return false; } }

char EMachine(char w){ //E自动机 string operate,a,b,c; string state[5]; w = TMachine(w); //调用T自动机 while(w=='+'||w=='-'){ //是加或减符号 operate = w; cin>>w; //读入下一字符 w = TMachine(w); //调用T自动机 b = wordStack.pop(); //字符栈弹出 a = wordStack.pop(); //两个操作字符 cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<noOfT<<")"<<endl; c = "t"+intToString(noOfT); //输出四元式 wordStack.push(c); //新状态压栈 noOfT++; //状态计数加一 } return w; }

char TMachine(char w){ string operate,a,b,c; string state[5]; w = FMachine(w); //调用F自动机 while(w=='*'||w=='/'){ //是乘除号 operate = w; cin>>w; //读取下一字符 w = FMachine(w); //调用F自动机 b = wordStack.pop(); //符号栈弹出 a = wordStack.pop(); //两个操作字符 cout<<"(\""<<operate<<"\","<<a<<","<<b<<",t"<<noOfT<<")"<<endl; c = "t"+intToString(noOfT); //输出四元式 wordStack.push(c); //新状态压栈 noOfT++; //状态计数加1 } return w; }