510min.cpp

学习编译原理的实用教程.教程共分7章: 第1章 编译系统概述 第2章 词法分析 第3章 程序设计语言的语法描述 第4章 自上而下的语法分析 第5章 自下而上的语法分析 第6章 语法制导翻译

//5.10 LR分析法在词法分析器自动构造中的应用（分析表最小化）
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
//常数
const char *word[]={//单词表
	"begin","end","integer","real","=","+","++","*",";","(",")",","
};
const char code[]={//编码表(仅含种别)
	"{}ac=+$*;(),"
};
const int LIN=25,COL=16,PRO_NUM=23;//分析表行数,分析表列数,产生式个数
const char TNT[]="=+*(.a0#LXYNIBAD";//终结符#非终结符
void main()
{
	char buf[4048]={'\0'};//扫描缓冲区
	int p_buf=0;//扫描缓冲区指针
//预处理
	void pro_process(char []);
	pro_process(buf);
	cout<<buf<<endl;//屏幕显示预处理结果
//读入分析表
	int M[LIN][COL];
	void read_table(int[][COL]);
	read_table(M);
//读入产生式
	char *p[PRO_NUM];
	void read_pro(char *[]);
	read_pro(p);
//LR分析控制程序函数原型
	char *lr_ctl(int [][COL],char *[],char [],int &p_buf);
	//形式参数说明:分析表首址,产生式,缓冲区首址,缓冲区指针；返回token字符数组首址。
//词法分析器扫描程序
	char *p_token;
	ofstream coutf("Lex_r.txt");//存放词法分析结果（单词二元式）
	while(1){
		while(buf[p_buf]=='#')p_buf++;//滤去单词前导'#'
		if(buf[p_buf]=='\0')break;//源程序处理完
		p_token=lr_ctl(M,p,buf,p_buf);//调用LR分析控制程序
		for(int i=0;i<(int)strlen(code);i++)//查单词表
			if(strcmp(p_token,word[i])==0){//匹配
				coutf<<code[i]<<'\t'<<"NUL"<<endl;
				break;
			}
		//查表未果，可能是变量名、整常数、实常数和错误词形4者之一
		if(i==(int)strlen(code)){
			if(p_token[0]<='z'&&p_token[0]>='a'){//变量名
				coutf<<'i'<<'\t'<<p_token<<endl;
			}
			else if(strcmp(p_token,".")==0)//错误词形
				coutf<<'!'<<'\t'<<p_token<<endl;
			else {
				for(i=0;p_token[i];i++)//无符号实常数
				if(p_token[i]=='.'){
					coutf<<'y'<<'\t'<<p_token<<endl;
					break;
				}
				if(!p_token[i])//无符号整常数
					coutf<<'x'<<'\t'<<p_token<<endl;
			}
		}//end of if(i==(int)strlen(code))
	}//end of while(1)
 	coutf<<'#'<<'\t'<<"NUL"<<endl;//源程序尾部添加'#'单词二元式
}
void read_table(int M[][COL])//读入分析表
{
	ifstream cinf1("LR_table.txt");	
	int i,j;
	for(i=0;i<LIN;i++)
		for(j=0;j<COL;j++)cinf1>>M[i][j];
}
void read_pro(char *p[])//读入产生式
{
	ifstream cinf2("Productions.txt");
	char t[20];
	for(int i=0;i<PRO_NUM;i++){
		cinf2>>t;p[i]=new char[strlen(t)+1];strcpy(p[i],t);
	}
}
char tra(char c)
{			
	if(c==')'||c==','||c==';')c='(';//大写字母转换为@或^
	if(c<='z' && c>'a')c='a';//小写字母转换为a或e
	if(c>'0' && c<='9')c='0';//数字转换为0
	return c;
}
int col(char c)//将字符转换为分析表的列号
{			
	for(int i=0;i<(int)strlen(TNT);i++)
		if(c==TNT[i])return i;
	cout<<"Err in col char>"<<c<<endl;exit(0);//非法字符
}
char *lr_ctl(int M[][COL],char *p[],char buf[],int &p_buf)//LR分析法控制程序
{			//分析表首址,产生式,缓冲区首址,缓冲区指针
	int state[50]={0},top=0;//状态栈初值,栈顶指针初值
	int action;char cur_ch;
	static char token[20];//token用于拼接单词，因返回首址，故类型为static。
	strcpy(token,"");int t=0;
	do{
		cur_ch=buf[p_buf];
		action=M[state[top]][col(tra(cur_ch))];
		if(action>0 && action!=99){//移进
			state[++top]=action;
			p_buf++;//指向下一字符
			token[t++]=cur_ch;
		}
		else if(action<0){//归约
			if(strcmp(p[-action]+3,"ε"))//F→ε右部符号串长度为0，无需退栈。
				top=top-(strlen(p[-action])-3);//→为汉字占二字节，再加上左部符号，故减3。
			state[top+1]=M[state[top]][col(p[-action][0])];
			top++;
		}
		else if(action==99){//接受
			cout<<"Acc"<<' '<<endl;break;
		}
		else{//出错
			cout<<"Acc0"<<' '<<endl;break;
		}
	}while(1);
	token[t]='\0';
	return token;
}
void pro_process(char buf[])
{
	ifstream cinf0("source.txt",ios::in);
	int i=0;char old_c='\0',cur_c;//计数器，前一个字符，当前字符。
	bool in_comment=false;//状态标志，false表示当前字符未处于注释中。
	while(cinf0.read(&cur_c,sizeof(char))){//从文件读一个字符
		switch(in_comment){
		case false:
			if(old_c=='/' && cur_c=='*'){//进入注释
				in_comment=true;
				i--;//去除已存入扫描缓冲区的字符'/'
			}
			else{
				if(cur_c>='A' && cur_c<='Z') cur_c+=32;
				if(cur_c=='\t' || cur_c=='\n'|| cur_c==' ') cur_c='#';
				buf[i++]=cur_c ;
			}
			break;
		case true:
			if(old_c=='*' && cur_c=='/')//离开注释
				in_comment=false;
		}//end of switch
		old_c= cur_c;//保留前一个字符
	}//end of while
}