Viết chương trình dịch phân tích cú pháp LL(1)

[hanhpth]

Chương trình phân tích cú pháp theo thuật toán LL(1), nhưng còn một số lỗi, mình không hiểu lắm nên các bạn sửa giúp mình, rất cảm ơn !

 
 
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
using namespace std;
// ky hieu epsilon va dola
#define epsilon 100
#define dola 101
#define TOKEN_LEN 50
#define RULE_LEN 10// do dai cua mot luat
#define RULELIST_LEN 100// do dai cua tap luat
#define NONTERMINAL 100// 
#define TABLE_T 50 // toi da co 50 ky hieu Terminal
#define TABLE_N 50 // toi da co 50 ky hieu Nonterminal


// cau truc mot tap hop ky hieu chua first hoac follow
#define SYMBOL_LEN 20

// cau truc ma hoa cac tu to
typedef struct TokenNode1
{	char s[TOKEN_LEN];
	int num;	
	TokenNode1 *next;
}TokenNode;


TokenNode *firsttoken;// tu to dau tien

int ternum;// ky hieu so terminal, dung de sinh so tu dong
int nonternum; // ky hieu so nonterminal, dung de sinh so nonterminal tu dong

typedef struct 
{	int arr[SYMBOL_LEN];
	int num;
}SymbolSet;


// cau truc cua phan tu luu tap first va follow cua cac ky hieu khong ket thuc
typedef struct FirstFollowSet1
{	int symbol;
	SymbolSet firstset,followset;
	FirstFollowSet1 *next;
}FirstFollowSet;

// cau truc rule
// phan tu vi tri 0 la ve trai
// tiep theo la ve phai o vi tri: 1,2,3,. . .
// chung ta qui dinh cac gia tri tu 0->99 danh cho Nonterminal
// tu 102 tro len danh cho Terminal
typedef struct
{
	int arr[RULE_LEN];
	int num;//so luong tu to trong luat
	SymbolSet firstset;// tap first cua ve phai	
}Rule;

typedef struct// cau truc danh sach luat
{
	Rule arr[RULELIST_LEN];
	int num;
}RuleList;

RuleList rlist;

// chu y vi ky hieu Terminal tinh tu hang so NONTERMINAL nen
// chi so i=symbol-NONTERMINAL
int stable[TABLE_N][TABLE_T];

//==============================================================
// MOT SO HAM THAO TAC TREN XAU KY TU

// tra ve 1 neu c la mot ky tu trong s
// tra ve 0 neu trai lai
int IsIn(int c, char *s)
{	
	if(s==NULL) return 0;
	for(unsigned int i=0;i<strlen(s);i++)
		if(c==s[i]) return 1;
	return 0;
}


// kiem tra xem 1 xau co ky tu dau tien viet hoa khong
// tu to loai nay mac dinh la Nonterminal
int IsCapitalAtFist(char *s)
{	
	if(s==NULL) return 0;
	else return isupper(s[0]);
}

//==============================================
// MOT SO HAM THAO TAC TREN FILE

// ham doc mot tu tu file
// f: con tro file
// s: xau
// max: so ky tu lon nhat trong 1 tu
// tra ve so ky tu doc duoc
int GetWord(FILE *f,char *s, int max)
{	s[0]=0;
	int c,i=0;
	char *xau1=" \n\r\t";
	c=getc(f);
	while(!feof(f) && IsIn(c,xau1))// ky hieu dieu khien
		c=getc(f);
	while(c!=EOF && !IsIn(c,xau1) && i<max)
	{	s[i++]=c;
		c=getc(f);
	}
	s[i]=0;// ket thuc xau
	return i; // neu i=0 la ket thuc xau
}

//===============================================
// add token vao danh sach tu to
// k=1 la Nonterminal
// k=0 la Terminal
void AddToken(char word[TOKEN_LEN],int k)
{
	// neu danh sach rong
	if(firsttoken==NULL)
	{	firsttoken=new TokenNode;
		strcpy(firsttoken->s,word);
		if(k==1) firsttoken->num=nonternum++;
		else firsttoken->num=ternum++;
		firsttoken->next=NULL;
		return;
	}

	TokenNode *p,*q,*tk;
	p=firsttoken;
	while(p)
	{
		if(strcmp(word,p->s)==0) return;		
		q=p;
		p=p->next;	
	}
	if(p==NULL)
	{	tk=new TokenNode;
		strcpy(tk->s,word);
		if(k==1) tk->num=nonternum++;
		else tk->num=ternum++;
		tk->next=NULL;
		q->next=tk;
	}
}

// ham lay danh sach cac ma hoa cua cac tu to
// chu y file nay co cau truc gom cac cap 2 tu (ten,num)
// chu y la neu file co cau truc khac thi ham nay se chay khong dung
void GetTokenList(const char *rulefilename)
{
	if(rulefilename==NULL) return ;
	FILE *f=fopen(rulefilename,"rt");
	if(f==NULL)
	{	printf("\nKhong ton tai file: \"%s\"",rulefilename);
		return;
	}	
	char word[TOKEN_LEN];
	// lay tat ca cac NonTerminal
	nonternum=0;
	int start=1;
	while(!feof(f))
	{	if(GetWord(f,word,TOKEN_LEN)==0) break;
		if(start==1)
			AddToken(word,1);
		if(strcmp(word,"@")==0)//ket thuc mot luat
			start=1;					
		else 
			start=0;		
	}
	
	// lay Terminal
	ternum=NONTERMINAL;
	start=1;
	fseek(f,0,SEEK_SET);// chuyen ve dau tep
	while(!feof(f))
	{	if(GetWord(f,word,TOKEN_LEN)==0) break;		
		if(start==0&&strcmp(word,"->")!=0)
			AddToken(word,0);
		if(strcmp(word,"@")==0)//ket thuc mot luat
			start=1;					
		else 
			start=0;		
	}

	fclose(f);
}

// ham tra ve ma cua mot tu to
int GetTokenCode(const char *token,TokenNode *first)
{
	if(token==NULL || first==NULL) return -1;
	TokenNode *p=first;
	while(p)
	{	if(strcmp(p->s,token)==0)
			return p->num;
		p=p->next;
	}
	return -1;
}

// ham tra ve gia tri cua mot tu to thong qua ma
void GetTokenStr(char *token, int code, TokenNode *first)
{
	token[0]=0;
	if(code==epsilon)
		strcpy(token,"epsilon");
	else if(code==dola)
		strcpy(token,"$");
	TokenNode *p=first;
	while(p)
	{	if(p->num==code)
		{	strcpy(token,p->s);
			return;
		}
		p=p->next;
	}
}

//================================================
// kiem tra mot ky hieu co phai la Terminla khong
// neu trai lai la Nonterminal
int IsTerminal(int symbol)
{
	return symbol>=NONTERMINAL;
}

// ham doc lay tap luat tu file
// moi luat duoc ghi tren mot dong co dang:
// A -> B C D. . . ;
// chu y: co dau @ o cuoi moi luat
void GetRule(RuleList &rulelist,const char *rulefilename,TokenNode *first)
{
	if(rulefilename==NULL) return;
	FILE *f=fopen(rulefilename,"rt");


	if(f==NULL)
	{	printf("\nKhong ton tai file: \"%s\"",rulefilename);
		return;
	}
	int i;
	int nlist=0;//so luong luat
	int rulenum=0;// so luong tu to trong luat
	Rule rule;
	char word[TOKEN_LEN];
	while(!feof(f))
	{	if(GetWord(f,word,TOKEN_LEN)==0) break;
		if(strcmp(word,"@")==0)//ket thuc mot luat
		{	// copy luat
			for(i=0;i<rulenum;i++)
				rulelist.arr[nlist].arr[i]=rule.arr[i];
			rulelist.arr[nlist].num=rulenum;
			rulenum=0; 
			nlist++;
		}
		else if(strcmp(word,"->")!=0)
		{	int k=GetTokenCode(word,first);		
			if(k==-1)
			{	printf("\nKhong ton tai tu to: \"%s\"",word);
				exit(1); 
			}
			rule.arr[rulenum++]=k;
		}
	}
	rulelist.num=nlist;
	fclose(f);
}

// ham hoan doi 2 luat
void SwapRule(Rule &r1, Rule &r2)
{
	Rule rtemp;
	rtemp=r1; r1=r2;r2=rtemp;
}

// ham sap xep luat theo ve trai
void RuleListSort(RuleList &rlist)
{	
	int n=rlist.num;
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{	if(rlist.arr[i].arr[0]>rlist.arr[j].arr[0])
				SwapRule(rlist.arr[i],rlist.arr[j]);
		}
}

//===================================================
// sinh first va follow cho cac ky hieu khong ket thuc
//  Tinh First
//	1. Xet tung luat, neu X->epsilon thi epsilon thuoc first(X)
//	2. neu X->Y1Y2..Yk, Y1 thuoc first(X), neu epsilon thuoc first(Y1)
//		thi first(y2) thuoc first(X)
// ky hieu epsilon la -1

// add mot ky hieu vao tap first cua mot ky hieu
// neu add duoc tra ve 1, trai lai neu ton tai roi thi tra ve 0
int AddFirst(FirstFollowSet *ffset, int nsymbol, int firstsym)
{	
	FirstFollowSet *p=ffset;
	while(p)
	{	if(p->symbol==nsymbol)
		{	//add firstsym vao neu khong trung
			for(int i=0;i<p->firstset.num;i++)
			{	if(p->firstset.arr[i]==firstsym)// trung
					return 0;
			// khong co phan tu nao trung
			p->firstset.arr[i]=firstsym;
			p->firstset.num++;
			return 1;
			}
		}
		p=p->next;
	}
	return 0;
}

// add mot tap first cua mot ky hieu vao mot tap first cua mot ky hieu khac
// first(sym2) vao first(sym1)
int AddFirstSet(FirstFollowSet *ffset, int sym1, int sym2)
{
	int count=0;
	FirstFollowSet *p=ffset;
	while(p)
	{	if(p->symbol==sym2)
		{	//add firstsym vao neu khong trung
			for(int i=0;i<p->firstset.num;i++)
				count+=AddFirst(ffset,sym1,p->firstset.arr[i]);
			break;
		}
		p=p->next;
	}
	return count;
}

// kiem tra xem ky tu firstsym thuoc mot tap first cua sym khong
int IsFirstIn(FirstFollowSet *ffset, int sym, int firstsym)
{
	FirstFollowSet *p=ffset;
	while(p)
	{	if(p->symbol==sym)
		{	//add firstsym vao neu khong trung
			for(int i=0;i<p->firstset.num;i++)
				if(p->firstset.arr[i]==firstsym)
					return 1;
		}
		p=p->next;
	}
	return 0;
}

// ham khoi tao tap cac ky hieu khong ket thuc
FirstFollowSet* InitNonterminalSet(TokenNode *tokennode)
{	
	FirstFollowSet *p,*q,*first=NULL;
	while(tokennode)
	{	if(IsTerminal(tokennode->num))// ky hieu khong ket thuc
		{	tokennode=tokennode->next;	
			continue;	
		}
		p=new FirstFollowSet;
		p->symbol=tokennode->num;
		p->next=NULL;
		p->firstset.num=0;
		p->followset.num=0;
		if(!first) {first=p;q=p;}
		else {q->next=p; q=p;}
		tokennode=tokennode->next;
	}
	return first;
}

void GetFirst(FirstFollowSet *ffset,RuleList &rlist)
{	// duyet qua cac luat cho den khi khong them duoc ky tu nao nua
	int i;
	int count=1;
	while(count)
	{	count=0;
		for(i=0;i<rlist.num;i++)// duyet qua tung luat
		{	Rule &r=rlist.arr[i];
			if(r.num==1)// luat rong
				count+=AddFirst(ffset,r.arr[0],epsilon);
			else// luat X->Y1Y2 . . . Yk
			{	int k=1,ok=1;
				while(k<r.num && ok)
				{	if(IsTerminal(r.arr[k]))
					{	count+=AddFirst(ffset,r.arr[0],r.arr[k]);
						break;// ket thuc
					}
					else// Nonterminal
					{	count+=AddFirstSet(ffset,r.arr[0],r.arr[k]);
						if(IsFirstIn(ffset,r.arr[k],epsilon))
							k++;
						else
							break;
					}
				}
				
			}
		}
	}	
}

// kiem tra xem mot ky hieu co thuoc first cua mot chuoi x khong
// x chua trong symlist voi so luong ky hieu la num
// ki hieu can xet la firstsym
// tap cac first va follow nam trong ffset
int IsInFirstSet(int symlist[RULE_LEN],int num,int firstsym, FirstFollowSet *ffset)
{
	for(int i=0;i<num;i++)
	{
		if(IsTerminal(symlist[i]))
			if(firstsym==symlist[i]) return 1;
			else return 0;
		else// Nonterminal
			if(IsFirstIn(ffset,symlist[i],firstsym))
				return 1;
			else if(!IsFirstIn(ffset,symlist[i],epsilon))
				break;// thoat
	}
	return 0;
}

// add sym vao list co do dai len voi dieu kien khong trung
// neu add duoc thi tra ve 1
// trai lai tra ve 0
int AddSym(int sym,int *list,int &len)
{
	for(int i=0;i<len;i++)
		if(sym==list[i]) return 0;
	list[len++]=sym;
	return 1;
}

// ham tinh first cua mot xau x
// dau vao la symlist[] va symnum
// ket qua tra ve la firstlist[] va firstnum
void GetFirstofSet(int *firstlist,int &firstnum, 
				   int *symlist, int symnum, FirstFollowSet *ffset)
{		
	firstnum=0;
	for(int i=0;i<symnum;i++)
	{	if(IsTerminal(symlist[i]))
		{	firstlist[firstnum++]=symlist[i];
			return;
		}			
		else// Nonterminal
		{	while(ffset)
			{	if(ffset->symbol==symlist[i])
				{	for(int j=0;j<ffset->firstset.num;j++)
						AddSym(ffset->firstset.arr[j],firstlist,firstnum);
					break;
				}
				ffset=ffset->next;
			}
			
			if(!IsFirstIn(ffset,symlist[i],epsilon))
				break;// thoat

		}
		
	}
}

//===============================================================
// Tinh FOLLOW
// add followsym vao follow(sym)
// neu add duoc thi tra ve 1
// trai lai tra ve 0
int AddFollow(FirstFollowSet *ffset, int sym, int followsym)
{
	if(followsym==epsilon)//epsilon
		return 0;
	FirstFollowSet *p=ffset;
	while(p)
	{	if(p->symbol==sym)
		{	for(int i=0;i<p->followset.num;i++)
				{ if(followsym==p->followset.arr[i])
					return 0;
			p->followset.arr[i]=followsym;
			p->followset.num++;			
			return 1;
			}
		}
		p=p->next;
	}
	return 0;
}

// add trong follow(sym2) vao follow(sym1)
// neu add duoc thi tra ve 1
// trai lai thi tra ve 0
int AddFollowSet(FirstFollowSet *ffset,int sym1, int sym2)
{
	int count=0;
	FirstFollowSet *p=ffset;
	while(p)
	{	if(p->symbol==sym2)
		{	for(int i=0;i<p->followset.num;i++)
				count+=AddFollow(ffset,sym1,p->followset.arr[i]);
			break;
		}
		p=p->next;
	}
	return count;

}

// 1.neu S la ky hieu xuat phat(=0) thi them $(-2) vao follow(S)
// 2.neu A->xBy thi add first(y) vao follow(B) neu B la ky hieu Nonterminal
// 3.neu A->xB thi add follow(A) vao follow(B)
// 4.neu A->xBy va y=>epsilon thi add follow(A) vao follow(B)
void GetFollow(FirstFollowSet *ffset,RuleList &rlist)
{	// duyet qua cac luat cho den khi khong them duoc ky tu nao nua
	int i,k,j;
	int count=1;
	// ap dung qui tac 1
	AddFollow(ffset,0,dola);
	while(count)
	{	count=0;
		for(i=0;i<rlist.num;i++)// duyet qua tung luat
		{	Rule &r=rlist.arr[i];
			// ap dung luat 2
			for(k=1;k<r.num-1;k++)
				if(!IsTerminal(r.arr[k]))// tim B
				{	// xac dinh y
					int y[SYMBOL_LEN], ynum=0;
					for(j=k+1;j<r.num;j++)
						y[ynum++]=r.arr[j];
					int firstlist[SYMBOL_LEN],firstnum;
					GetFirstofSet(firstlist,firstnum,y,ynum,ffset);
					// add ket qua vao follow(B)
					for(j=0;j<firstnum;j++)
						count+=AddFollow(ffset,r.arr[k],firstlist[j]);
					//==================
					// ap dung luat 4
					if(IsInFirstSet(y,ynum,epsilon,ffset))
						count+=AddFollowSet(ffset,r.arr[k],r.arr[0]);
				}
			// ap dung luat 3
			if(!IsTerminal(r.arr[r.num-1]))//A->xB
				count+=AddFollowSet(ffset,r.arr[r.num-1],r.arr[0]);

		}
	}	
}

// sinh FIRST cho cac ve phai
// get first for right hand side
void GetFirstforRHS(FirstFollowSet *ffset,RuleList &rlist)
{
	for(int i=0;i<rlist.num;i++)
	{	Rule &r=rlist.arr[i];
		int symlist[RULE_LEN],symnum=0;
		for(int k=1;k<r.num;k++)
			symlist[symnum++]=r.arr[k];
		GetFirstofSet(r.firstset.arr,r.firstset.num,symlist,symnum,ffset);
	}
}


// Ham in mot luat
// i la chi so luat
void PrintRule(int i,RuleList &rlist)
{
	Rule &r=rlist.arr[i];
	char word[TOKEN_LEN];
	for(int j=0;j<r.num;j++)
	{	GetTokenStr(word,r.arr[j],firsttoken);
		printf("%s  ",word);
		if(j==0) printf("->  ");
	}

}


//=============================================================
// Sinh bang phan tich LL(1)
// Duyet qua tat ca cac luat
// 1. Voi luat A->x thi voi moi a thuoc first(x), ta add table[A,a]=A->x
// 2. Neu A->epsilon thi voi moi a thuoc follow(A), ta add table[A,a]=epsilon

// tra ve 0 neu la van pham LL(1)
// tra ve <>0 neu trai lai
int GetTableLL1(FirstFollowSet *ffset)
{
	int count=0;
	// khoi tao bang ban dau:
	int i,j;
	for(i=0;i<TABLE_N;i++)
	for(j=0;j<TABLE_T;j++)
		stable[i][j]=-1;// error
	//
	for(i=0;i<rlist.num;i++)
	{	Rule &r=rlist.arr[i];
		// Voi luat A->x thi voi moi a thuoc first(x), ta add table[A,a]=A->x
		for(j=0;j<r.firstset.num;j++)
			if((r.firstset.arr[j]!=-1)&&(r.firstset.arr[j]!=epsilon))
			{	int a=r.firstset.arr[j]-NONTERMINAL;
				if(stable[r.arr[0]][a]!=-1)// loi, trung
				{	count++;
					printf("\nxung dot tai luat:\n");
					PrintRule(stable[r.arr[0]][a],rlist);
					printf("\n");
					PrintRule(i,rlist);
					getch();
				}
				
				stable[r.arr[0]][a]=i;
			}
		// Neu A->epsilon thi voi moi a thuoc follow(A), ta add table[A,a]=epsilon
		if(r.num==1)// A->epsilon
		{	FirstFollowSet *pset=ffset;
			while(pset)
			{	if(pset->symbol==r.arr[0])
				{	for(int k=0;k<pset->followset.num;k++)
					{	
                         if(stable[r.arr[0]][pset->followset.arr[k]]==i);
                         count++; 	// tang so lan trung,khong phai LL1
                         stable[r.arr[0]][pset->followset.arr[k]-NONTERMINAL]=i;

					 }
					break;
				}
				pset=pset->next;
			}
			
		}
	}
	return count;	
}


/****************************************************************/
int main()
{
	int i,j;
	firsttoken=NULL;
	GetTokenList("rule.txt");
	// thu nghiem file luat	
	char word[TOKEN_LEN];	
	
	GetRule(rlist,"rule.txt",firsttoken);
	RuleListSort(rlist);
	printf("\n\nBo luat:");
	for(i=0;i<rlist.num;i++)
	{	printf("\n");
		for(j=0;j<rlist.arr[i].num;j++)
		{	GetTokenStr(word,rlist.arr[i].arr[j],firsttoken);
			printf("%s  ",word);
			if(j==0) printf("->  ");
		}
	}

	// Sinh first va follow cua cac ky hieu nonterminal
	FirstFollowSet *ffset,*pset;
		
	ffset=InitNonterminalSet(firsttoken);
	GetFirst(ffset,rlist);
	GetFollow(ffset,rlist);
	pset=ffset;
	char token[TOKEN_LEN];
	printf("\n\nTinh first cho cac ky hieu khong ket thuc:");
	while(pset)
	{	printf("\n");
		GetTokenStr(token,pset->symbol,firsttoken); 
		printf("(%s)  First= ",token);
		for(i=0;i<pset->firstset.num;i++)
		{	GetTokenStr(token,pset->firstset.arr[i],firsttoken); 
			printf("%s  ",token);
		}
		printf("   Follow= ");
		for(i=0;i<pset->followset.num;i++)
		{	GetTokenStr(token,pset->followset.arr[i],firsttoken); 
			printf("%s  ",token);
		}
		pset=pset->next;
	}

	// Sinh tap first cua ve phai cua cac luat
	GetFirstforRHS(ffset,rlist);
	printf("\n\nTap first cho ve phai cac luat:");
	for(i=0;i<rlist.num;i++)
	{	printf("\n");
		Rule &r=rlist.arr[i];
		for(j=0;j<r.num;j++)
		{	GetTokenStr(word,r.arr[j],firsttoken);
			printf("%s  ",word);
			if(j==0) printf("->  ");
		}
		// in tap first
		printf("\n First = ");
		for(j=0;j<r.firstset.num;j++)
		{	GetTokenStr(word,r.firstset.arr[j],firsttoken);
			printf("%s  ",word);
		}
	}

	// Sinh bang LL(1)
	int k;
	if((k=GetTableLL1(ffset))!=0)
	{	printf("\n\nDAY KHONG PHAI LL(1)!\n");
		printf("co %d vi tri loi!\n",k);
	}
	printf("\n\nBang phan tich LL(1):\n");
	for(i=0;i<TABLE_N;i++)
		for(j=0;j<TABLE_T;j++)
		if(stable[i][j]>-1)
		{	char str1[TOKEN_LEN],str2[TOKEN_LEN];
			GetTokenStr(str1,i,firsttoken);
			GetTokenStr(str2,j+NONTERMINAL,firsttoken);
			printf("\nTable(%s,%s)=",str1,str2);			
			PrintRule(stable[i][j],rlist);
		}
	printf("\n");	
	getch();
	return 0;
}

Đây là cả một chương trình phân tích cú pháp nên hơi dài, các bạn chịu khó giúp mình nha