slr.cpp

计算机编译原理相关实验3：一个用SLR(1)文法自底向上的语义分析器

#include <iostream>
#include <stack>
#include <cstring>
#include <fstream>
#include <ctype.h>
#include <stdlib.h>
#include <sys/stat.h>
using namespace std;

struct  symbolRecord
{
	char symbol[10];
	int id;
}record[32];

struct entryType
{
	char idName[16];
	int address;
	char *type;
	entryType* next;
};
struct digitTable
{
	int address;
	int digit;
	digitTable *next;
};

struct tokenType
{
	int id;
	int entry;
	tokenType* next;
};

struct creat
{
	int id;
	int length;
	char left;
	char string[32];
}grammar[64];

struct term
{
	int id;
	char character;
}nonTerminate[32];

struct equal
{
	int id;
	char first[16];
	char second[16];
	char third[16];
	char forth[16];
}equalExp[32];

int entry, digit, instruction;
int line, row, cursor;
char stringBuffer[128];
char* file;
int fileLength;

int i,j;

entryType *headEntry,*tailEntry;
digitTable *headDigit,*tailDigit;
tokenType  *headToken, *tailToken;

int gotoTable[66][13];
int actionTable[66][28];
tokenType* position;
stack<int> stateStack;
stack<int> termStack;
stack<int> tokenStack;

int nextQuad;
int nextList_L, nextList_S, nextList_C, nextList_U, nextList_F;
int	quad_M;
int head_W,head_U;
int trueList_B,falseList_B;
int trueList_N,falseList_N;
int trueList_P,falseList_P;
char relop[16];
char type_T[16];
char place_E[32][16];
int list_D[32];							//variables' address
char tempVariable[32][16];
int num_E, num_D;
int tempNum;


void sort(char);
void panner(int);
void handleCom(char);
void readGrammar();
char getCharacter();

void recogId(char);
void recogStr(char);
void recogDel(char);
void recogDig(char);


void initRecord();
int insertEntry(char*, char*);
void insertToken(int, int);
void insertDigit(int);
void scanner();
bool empty(int );
void initize();
int nonTerminative(char);
char* terminative(int);
void analyse();
void backPatch(int ,int);
int merger(int ,int);
void output();

void  f1(); void  f2(); void  f3(); void  f4(); void  f5(); void  f6(); void  f7();
void  f8(); void  f9(); void f10(); void f11(); void f12(); void f13(); void f14();
void f15(); void f16();	void f17(); void f18(); void f19(); void f20();	void f21();
void f22(); void f23(); void f24();	void f25(); void f26(); void f27(); void f28();
void f29(); void f30(); void f31(); void f32();	void f33(); void f34(); void f35(); 
//******************************   init   *****************************
void init()
{
	headEntry = tailEntry = NULL;
	headDigit = tailDigit = NULL;
	headToken = tailToken = NULL;
	file = NULL; fileLength = 0; 
	line = 0; row = 0; cursor = -1;
	digit = 0; entry = 0;
	instruction = 0; nextQuad = 0;
	num_D = 0; num_E = 0; tempNum = 0;
}

void initRecord()			//initize symbol code
{
	for(int i = 0; i < 30; i++) record[i].id = i;
	char ch;
	int j = 0, k = 0;
	try {
		ifstream inFile("symbol.txt", ios::in) ;
		if(inFile == NULL) throw(" file symbol.txt doesn't exist\n");
		while((ch = inFile.get()) != EOF ) {
			while((ch != '\n') && (ch != EOF)) {
				if((ch != ' ') && (ch != '\t')) record[j].symbol[k++] = ch;
				ch = inFile.get();
			}
			record[j++].symbol[k] = '\0';
			k = 0;
		}
		inFile.close() ;
	}catch(const char* p )
	{
		cout << p << endl;
	};	
}

void initize()
{
	FILE *noter;
	if((noter = fopen("nonTerminative.txt","rt")) == NULL) {
		cout<<"can not open the file nonTerminative.txt"<<endl;
		exit(1);
	} else {
		for(i = 0; i < 20; i++) 
			fscanf(noter, "%d  %c", &nonTerminate[i].id, &nonTerminate[i].character);
	}
	fclose(noter);
	readGrammar();
	ifstream gotoTableFile("gotoTable.txt");
	for(i = 0; i < 66; i++) {
		for(j = 0; j < 13; j++) gotoTableFile >> gotoTable[i][j];
	}
	gotoTableFile.close();
	ifstream actionTableFile("actionTable.txt");
	for(i = 0; i < 66; i++) {
		for(j = 0; j < 28; j++)
			actionTableFile >> actionTable[i][j];
	}
	actionTableFile.close();
	memset(equalExp, 0, sizeof(equalExp));
}

//******************************   insert   *****************************
void insertDigit(int Digit)
{
	digitTable* tempDigitTable;
	tempDigitTable = new digitTable;
	tempDigitTable->address = digit;
	tempDigitTable->digit = Digit;
	tempDigitTable->next = NULL;

	if(headDigit == NULL) {
		headDigit = tailDigit = tempDigitTable;
		digit++;
	} else {
		tailDigit = tailDigit->next = tempDigitTable;
		digit++;
	}
}

void insertToken(int id,int entry)
{
	tokenType *tempToken;
	tempToken= new tokenType;
	tempToken->id = id;
	tempToken->entry = entry;
	tempToken->next = NULL;
	if(headToken == NULL) headToken = tailToken = tempToken;
	else tailToken = tailToken->next = tempToken;
}
//*********************************  scanner  *********************************
void scanner()
{
	struct stat buffer;
	char ch;
	int i = 0;
	try{
		stat("source.txt", &buffer);
		file = new char[buffer.st_size] ;
		ifstream inFile("source.txt", ios::in) ;
		if(inFile == NULL) throw("file source.txt does not exist\n");
		while((ch = inFile.get()) != EOF) file[i++] = ch;
		inFile.close() ;
	}catch(const char* p)
	{
		cout << p << endl;
	};
	file[i++] = '\0';
	fileLength = i;
	initRecord();
	while((ch = getCharacter()) != '\0') {
		if((ch != '\n') && (ch != ' ') && (ch != '\t')) {
			if( islower(ch) || isupper(ch) || ch == '_' ) recogId(ch);
			else if(ch == '/') handleCom(ch) ;
			else if(isdigit(ch)) recogDig(ch);
			else if(ch== '"') recogStr(ch);
			else recogDel(ch);
		};
	}
	insertToken(27,-1);
}

void recogId(char character)
{
	char digbuf[10];
	int i = 0;
	bool keyword = false;
	while(islower(character) || isupper(character) || isdigit(character)) {
		digbuf[i] = character;
		character = getCharacter();
		i++;
	}
	digbuf[i] = '\0';
	cursor--;
	row--;
	for(i = 0; i <= 8; i++) {
		if(strcmp(record[i].symbol,digbuf) == 0) {
			insertToken(record[i].id, -1);
			keyword = true;
		}
	}
	if(!keyword) {
		entryType *head, * tempEntry;
		bool word = false;
		if(headEntry == NULL) {
			head = new entryType;
			strcpy(head->idName, digbuf);
			head->address = entry;
			head->type = NULL;
			head->next = NULL;
			headEntry = tailEntry = head;
			entry++;
			insertToken(10, entry - 1);
		} else {
			tempEntry = headEntry;
			while(tempEntry != NULL) {
				if(strcmp(tempEntry->idName, digbuf) == 0) {
					insertToken(10, tempEntry->address);
					word = true;
				}
				tempEntry = tempEntry->next;
			}
			if(!word) {
				head = new entryType;
				strcpy(head->idName, digbuf);
				head->address = entry;
				head->type = NULL;
				head->next = NULL;
				tailEntry = tailEntry->next = head;
				entry++;
				insertToken(10, entry - 1);
			}
		}
	}
}

void handleCom(char character)
{
	char ch;
	ch = getCharacter();
	if(ch != '*') {
		insertToken(29, -1);
		row--;
		cursor--;
	} else {
		bool translate = false;
		char tempCh;
		tempCh = getCharacter();
		while(row != 1 ) {
			ch = getCharacter();
			if(tempCh == '*' && ch == '/') {
				translate = true;
				break;
			}
			tempCh = ch;
		}
		if(!translate) cout<<"notation has not finished"<<endl;
	}
}

void recogDig(char character)
{
	int i = 0;
	do {
		i = i * 10 + character - '0';
		character = getCharacter();
	}while(isdigit(character));
	row--;
	cursor--;
	insertDigit(i);
	insertToken(9, digit - 1);
}

void recogStr(char character)
{
	character = getCharacter();
	while(character != '"') {
		stringBuffer[instruction] = character;
		instruction++;
		character = getCharacter();
	}
	stringBuffer[instruction] = '\n';
}

void recogDel(char character)
{
	char ch;
	switch(character) {
	case '{': {insertToken(11, -1); break;}
	case '}': {insertToken(12, -1); break;}
	case ';': {insertToken(13, -1); break;}
	case ',': {insertToken(14, -1); break;}
	case '!': {insertToken(16, -1); break;}
	case '&': {insertToken(17, -1); break;}
	case '|': {insertToken(18, -1); break;}
	case '+': {insertToken(23, -1); break;}
	case '*': {insertToken(24, -1); break;}
	case '(': {insertToken(25, -1); break;}
	case ')': {insertToken(26, -1); break;}
	case '<': {
		if((ch = getCharacter()) == '=') insertToken(20, -1);
		else {
			if(ch == '>') insertToken(22, -1);
			else {
				insertToken(19, -1);
				row--;
				cursor--;
			}
		}
		break;}
	case '=': {
		if((ch = getCharacter()) == '=') insertToken(21, -1);
		else {
			insertToken(15, -1);
			row--;
			cursor--;
		}
		break;}
	default:break;}
}

//************************************************************************

char getCharacter()		//find next character
{
	if(file[cursor] == '\n') {
		row = 1;
		line++;
		cursor++;
	} else {
		row++;
		cursor++;
	}
	return file[cursor];
}

void readGrammar()
{
	int i = 1;
	try {
		ifstream in("grammar.txt", ios::in);
		if(in == NULL) throw(" grammar.txt is not exist! \n");
		else {
			while(in.getline(grammar[i].string, 20, '\n')) {
				grammar[i].id = i;
				i++;
			}
			in.close();
		}
	}catch( const char * p )
	{
		cout << p << endl;
	};
	for(i = 1; i < 36; i++) { //get the length of generated left and right
		bool end = false;
		int j = 0, k = 0;
		while(grammar[i].string[j] == ' ' && grammar[i].string[j] != '\0') j++;
		grammar[i].left = grammar[i].string[j++];
		while(grammar[i].string[j] == ' '&& grammar[i].string[j] != '\0') j++;
		if(grammar[i].string[j] == '-'&& grammar[i].string[j] != '>') j += 2;
		else {
			cout<<"there are some errors in grammar!"<<endl;
			return;
		}
		while(grammar[i].string[j] == ' ') j++;
		while( grammar[i].string[j] != '\0') {
			while(grammar[i].string[j] != ' ') {
				if(grammar[i].string[j] == '\0' ) {
					end = true;
					break;
				} else j++;
			}
			if(!end) {
				k++;
				j++;
			}
		}
		grammar[i].length = k + 1;
	}
}

bool empty(int i)
{
	int j = 0, k = 0;
	char temp[16];
	if(grammar[i].length == 1) {
		while(grammar[i].string[j] != '\0') j++;
		while(grammar[i].string[j] != ' ') j--;
		j++;
		while(grammar[i].string[j] != '\0') {
			temp[k] = grammar[i].string[j];
			j++;
			k++;
		}
		temp[k] = '\0';
		char *str = "epsilon";
		if(!strcmp(temp,str)) return true;
	}
	return false;
}

int nonTerminative(char character)  //test if it is a non-terminative
{
	for(int i = 0; i < 20; i++) {
		if(character == nonTerminate[i].character) return i;
	}
	return -1;
}

char* terminative(int i)
{
	for(int j = 0; j < 30; j++) {
		if(record[j].id == i) return record[j].symbol;
	}
	return NULL;
}
//****************************************  analyse **************************
void analyse()
{
	int temp, j, k;
	initize();
	ofstream out("semantic.txt");
	position = headToken;
	stateStack.push(27);
	tokenStack.push(-1);