tfcompile.cpp

词法分析程序的实现

/*
 * @(#)TfCompile.cpp 1.0.1 2007/08/16.
 * Test project for class IntStack.
 * Copyright (c)2007 Joseph Chu, HUST.
 * All rights reserved.
 */

/*
 * 文法如下：
 *		S → A
 *		A → V:=E
 * ------------------------
 *		E → E + T | T
 *		T → T * F | F
 *		F → (E) | i
 * ------------------------
 *		V → i
 */

/*
 * 定义：
 *		< 为 -1
 *		= 为
 *		> 为 1
 *		不可比为0
 *
 * 该文法对应的矩阵为：
 *		=	+	*	i	(	)	$
 *	  |-----------------------------
 *	= |		-1	-1	-1	-1		1
 *	+ |		1	-1	-1	-1	1	1
 *	* |		1	1	-1	-1	1	1
 *	i |	1	1	1	-	-	1	1
 *	( |		-1	-1	-1	-1	-1	-
 *	) |		1	1	-	-	1	1
 *	$ |	-1	-1	-1	-1	-1	-	-1
 *	  |
 */

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int z=65;

int matrix[7][7]={0};

/*
int matrix[7][7]={
	{  0, -1, -1, -1, -1,  0,  1},
	{  0,  1, -1, -1, -1,  1,  1},
	{  0,  1,  1, -1, -1,  1,  1},
	{  1,  1,  1,  0,  0,  1,  1},
	{  0, -1, -1, -1, -1, -1,  0},
	{  0,  1,  1,  0,  0,  1,  1},
	{ -1, -1, -1, -1, -1,  0, -1}
};
*/

typedef struct Quatern{
	char op;
	char arg1;
	char arg2;
	char result;
	struct Quatern *next;
} Quatern;

char newtemp(){
	return z++;
}

int cti(char c){
	switch(c){
	case '=':
		return 0;
	case '+':
		return 1;
	case '*':
		return 2;
	case '(':
		return 4;
	case ')':
		return 5;
	case '$':
		return 6;
	}
	if(isalnum((int)c)!=0)
		return 3;

	return -1;
}

int isCoda(char a){
	if(cti(a)!=-1)
		return 1;
	return 0;
}

int compare(char a,char b){
	if(matrix[cti(a)][cti(b)]==1)
		return 1;
	else if(matrix[cti(a)][cti(b)]==-1)
		return -1;
	else
		return 0;
}

void matrbuild(){
	char a[40]={0};
	char *p=0;

	fprintf(stdout,"输入G[S]的FIRSTVT和LASTVT：\n");

	matrix[6][1]=-1;
	matrix[6][2]=-1;
	matrix[6][4]=-1;
	matrix[4][5]=-1;

	printf("开始符号S的FIRSTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[6][cti(*p)]=-1;
		p++;
	}
	printf("开始符号S的LASTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[cti(*p)][6]=1;
		p++;
	}
	matrix[6][6]=-1;

	printf("符号V的LASTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[cti(*p)][0]=1;
		p++;
	}

	printf("符号F的FIRSTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[2][cti(*p)]=-1;
		p++;
	}

	printf("符号E的FIRSTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[0][cti(*p)]=-1;
		matrix[4][cti(*p)]=-1;
		p++;
	}

	printf("符号E的LASTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[cti(*p)][1]=1;
		matrix[cti(*p)][5]=1;
		p++;
	}

	printf("符号T的FIRSTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[1][cti(*p)]=-1;
		p++;
	}

	printf("符号T的LASTVT：\n");
	scanf("%s",a);
	p=a;
	while(*p!=0){
		matrix[cti(*p)][2]=1;
		p++;
	}

/*
	printf("-------------------------\n");
	for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			if(matrix[i][j]==1)
				printf("%c  ",'1');
			else if(matrix[i][j]==-1)
				printf("-%c ",'1');
			else if(matrix[i][j]==0)
				printf("%c  ",'0');
		}
		printf("\n");
	}
	printf("-------------------------\n");
*/
}

int main(int argc,char **argv){
	char S[40]={0};
	int k=0,j=0;
	char a=0;;
	char q=0;
	Quatern *head=(Quatern *)malloc(sizeof(Quatern));
	Quatern *p=head;
	char temp=0;

	matrbuild();

	getchar();
	fprintf(stdout,"\n输入赋值语句串：\n");
	S[k]='$';
be1:
	a=getchar();

	if(isCoda(S[k])==1)
		j=k;
	else
		j=k-1;
be3:
	if(compare(S[j],a)!=1)
		if(compare(S[j],a)==-1){
			k++;
			S[k]=a;
			goto be1;
		}
		else{
			printf("ERROR!\n");
			exit(0);
		}
be2:
	q=S[j];
	j--;

	if(isCoda(S[j])!=1)
		j--;
	if(compare(S[j],q)!=-1)
		goto be2;

	p->next=(Quatern *)malloc(sizeof(Quatern));
	p=p->next;
	p->next=0;
	if(islower(S[j+1])!=0||isdigit(S[j+1])!=0){
		p->op='#';
		p->arg1=S[j+1];
		p->arg2='-';
		p->result=(temp=newtemp());
	}
	else if(cti(S[k-2])==4){
		p->op='@';
		p->arg1=S[k-1];
		p->arg2='-';
		p->result=(temp=newtemp());
		j--;
	}
	else if(cti(S[k-1])==1){
		p->op='+';
		p->arg1=S[k-2];
		p->arg2=S[k];
		p->result=(temp=newtemp());
	}
	else if(cti(S[k-1])==0){
		p->op='=';
		p->arg1=S[k-2];
		p->arg2=S[k];
		p->result=(temp=newtemp());
	}
	else if(cti(S[k-1])==2){
		p->op='*';
		p->arg1=S[k-2];
		p->arg2=S[k];
		p->result=(temp=newtemp());
	}

	k=j+1;
	S[k]=temp;

	int m=k+1;
	while(S[m]!=0){
		S[m]=0;
		m++;
	}

	if(k==1&&a=='$'){
		p=head->next;
		do{
			printf("( ");
			printf("%c  ",p->op);
			printf("%c  ",p->arg1);
			printf("%c  ",p->arg2);
			printf("%c",p->result);
			printf(" )\n");
			p=p->next;
		}while(p!=0);
		return 0;
	}
	else
		goto be3;
}