lalr.cpp

为L语言设计一个语法分析器。 读入源程序

#include <stdlib.h>
#include<stdio.h>
#include <iostream.h>
#include <fstream.h>
#include<string.h>
FILE *fps;

char action_new[100][27][5]; 
int goto_new1[100][10]; 
//---------------------------------------------------------------
//----------------------ListNode链表节点类-----------------------
//---------------------------------------------------------------
template<class Type> class List;				
template<class Type>
class ListNode
{
friend class List<Type>;
friend class CGRAMMAR;						
public:
	ListNode():link(NULL){ }							
	ListNode(const Type &item):data(item),link(NULL){ }	
private:
	Type data;

	ListNode<Type> *link;
};
//---------------------------------------------------------------
//----------------------ListNode链表节点类-----------------------
//---------------------------------------------------------------

//---------------------------------------------------------------
//----------------------List链表类-------------------------------
//---------------------------------------------------------------
template<class Type>
class List
{
friend class CGRAMMAR;
public:
	List():first(NULL),last(NULL){ }				

	void MakeEmpty()								
	{
		ListNode<Type> *q;
		while(first!=NULL){
			q=first;
			first=q->link;
			delete q;
		}
		delete first;
	}

	int Length() const								
	{
		int i(0);
		for(ListNode<Type> *p=first;p;p=p->link) i++;
		return i;
	}

	ListNode<Type> *Find(Type value)				
	{
			ListNode<Type> *p=first->link;
		while(p!=NULL&&p->data!=value)	p=p->link;
		return p;
	}

	void Insert(Type value)								
	{	
		if(first==NULL)								
		{
			first=last=new ListNode<Type>(value);
			last->link=NULL;
		}
		else
		{
			ListNode<Type> *temp=new ListNode<Type>(value);
			last->link=temp;
			last=last->link;
			last->link=NULL;
		}
	}

	void Remove(Type value)								
	{
		ListNode<Type> *p;
		if(first==NULL) return;
		if(first->data==value){							
			p=first;							
			first=first->link;
			delete p;
			return ;
		}
		else{										
			for(ListNode<Type> *q=first;q->link;q=q->link)	
				if(q->link->data==value){
					p=q->link;
					q->link=p->link;
					delete p;
					return ;
				}
		}
	}

	void Print()									
	{
		for(ListNode<Type> *p=first;p;p=p->link)
			cout<<p->data;
	}

	void PutToArray(char *&buf)						
	{
		int len=Length();
		buf=new char[len];
		int i=0;
		for(ListNode<Type> *p=first;p;p=p->link)
		{
			buf[i]=p->data;
			i++;
		}
	}

	void DelRepeated()								
	{
		ListNode<Type> *q,*t,*p;
		for(q=first;q;q=q->link)
		{
			p=q;
			while(p->link){
				if(p->link->data==q->data){
					t=p->link;
					p->link=t->link;
					delete t;
					}
				else p=p->link;
			}
		}
	}

	int Contains(Type value)						
	{
		for(ListNode<Type> *p=first;p;p=p->link)
			if(p->data==value)
				return 1;
		return 0;
	}

	int GetCode(Type value)							
	{
		int i=0;
		for(ListNode<Type> *p=first;p;p=p->link,i++)
			if(p->data==value)
				return i;
		return 0;
	}

	int operator == (List<Type> &right)					
	{
		ListNode<Type> *p;
		for(p=first;p;p=p->link)
			if(right.Contains(p->data)==0)
				return 0;
		for(p=right.first;p;p=p->link)
			if(Contains(p->data)==0)
				return 0;
		return 1;
	}

	List<Type> &operator = (const List<Type> &right)	
	{
		MakeEmpty();
		Add(right);
		return *this;
	}

	int IsEmpty()									
	{
		if(Length()==0)
			return 1;
		return 0;
	}

	void Add(const List<Type> &right)						
	{
		for(ListNode<Type> *p=right.first;p;p=p->link)
		{
			if(!Contains(p->data))
			 Insert(p->data);
		}
	}

	int MergeString(List<Type> &right)						
	{
		int len1=this->Length();
		int len2=right.Length();
		int ret=0;
		ListNode<Type> *p,*q;
		if(len1==len2){
			for(p=this->first,q=right.first;p;p=p->link,q=q->link)
			{	
				if(q->data.string==p->data.string) continue;
				if(q->data.string.IsEmpty()) continue;
				if(p->data.Merge(q->data)==1) ret=1;
			}
		}
		return ret;
	}
private:
	ListNode<Type> *first,*last;
};
//---------------------------------------------------------------
//----------------------List类-------------------------------
//---------------------------------------------------------------

//---------------------------------------------------------------
//----------------------Queue类------------------------------
//---------------------------------------------------------------
const int QueueMaxSize=100;

template<class Type>
class Queue{
public:
	Queue(){count=0;front=rear=0;}
	~Queue(){front=rear=0;}
	int QueueEmpty(){return front==rear;}
	void QInsert(Type &item)        
	{
		if(count==QueueMaxSize)
		{
			cerr<<"Queue overflow!"<<endl;
			exit(1);
		}
		rear=(rear+1)%QueueMaxSize;				
		queue[rear]=item;
		count++;
	}
	Type QDelete()             
	{
		if(count==0)
		{
			cerr<<"Queue is empty!"<<endl;
			exit(1);
		}
		front=(front+1)%QueueMaxSize;
		count--;
		return queue[front];
	}
	int Contains(Type &elem)
	{
		if(elem.IsEmpty()) return 0;
		for(int i=front;i<=rear;i++)
			if(queue[i]==elem)
				return 1;
		return 0;
	}
	int GetCode(Type elem)
	{
		for(int i=front+1;i<=rear;i++)
			if(queue[i]==elem)
				return i;
		return 0;
	}
	Type queue[QueueMaxSize];
	int front,rear;
	int count;
};
//---------------------------------------------------------------
//----------------------Queue类------------------------------
//---------------------------------------------------------------

//---------------------------------------------------------------
//----------------------CItem类---------------------------------
//---------------------------------------------------------------
const int END=1000;
class CItem
{
public:
	CItem(){string.MakeEmpty();}
	int operator == (CItem &right)				
	{
		int pos1=this->GetDotPos();
		int pos2=right.GetDotPos();
		if(this->vn==right.vn&&pos1==pos2)
			if(this->sentence[pos1+1]==right.sentence[pos2+1]
				&&this->sentence[pos1-1]==right.sentence[pos2-1])
				return 1;
		return 0;
	}
	CItem &operator = (CItem &right)			
	{
		vn=right.vn;
		for(int i=0;right.sentence[i]!=END;i++);
		sentence=new int[i+1];
		sentence[i]=END;
		for(i=0;right.sentence[i]!=END;i++)
			sentence[i]=right.sentence[i];
		string.Add(right.string);
		return *this;
	}
	int IsForReduce()							
	{
		int pos=GetDotPos();
		if(sentence[pos+1]<0)
			return 1;
		return 0;
	}
	int IsAccept()								
	{
		int pos=GetDotPos();
		if(vn==-5&&sentence[pos+1]==END)
			return 1;
		return 0;
	}
	int IsShift()									
	{
		int pos=GetDotPos();
		if(sentence[pos+1]>0)
			return 1;
		return 0;
	}
	int IsReduce()									
	{
		int pos=GetDotPos();
		if(pos==0) return 0;
		if(sentence[pos+1]==END)
			return 1;
		return 0;
	}
	int GetDotPos()									
	{
		for(int i=0;sentence[i]!=END;i++)
			if(sentence[i]==1) break;
		return i;
	}
	int Merge(CItem &item)							
	{
		int len1=string.Length();
		string.Add(item.string);
		int len2=string.Length();
		if(len2-len1>0)
			return 1;
		return 0;
	}
public:
	int vn;
	int *sentence;
	List<int> string;
};
//---------------------------------------------------------------
//----------------------CItem类END-------------------------------
//---------------------------------------------------------------

//---------------------------------------------------------------
//----------------------Gener类----------------------------------
//---------------------------------------------------------------
class Gener										
{
public:
	int GetRightLength( )						
	{
		int count(0);
		while(1){
			if(sentence[count]==END) break;
			count++;
			}
		return count;
	}
	void InsertDot(int *array,int len,int pos)	
	{
		for(int i=len;i>=pos;i--)				
			array[i+1]=array[i];
		array[pos]=1;								
	}
	void GenToItem(List<CItem> &list,int len)		
	{
		if(sentence[1]==END&&sentence[0]==0)
		{		//A->$的情况
			CItem item;
			item.vn=vn;
			item.sentence=new int[2];
			item.sentence[0]=1;
			item.sentence[1]=END;
			list.Insert(item);
			return;
		}
		for(int i=0;i<len+1;i++)
		{
			CItem item;
			item.vn=vn;
			item.sentence=new int[len+2];
			for(int j=0;j<len;j++)
				item.sentence[j]=sentence[j];
			InsertDot(item.sentence,len,i);
			item.sentence[len+1]=END;
			list.Insert(item);
		}
	}
public:
	int vn;										
    int* sentence;								
};
//---------------------------------------------------------------
//----------------------Gener类END-------------------------------
//---------------------------------------------------------------

//---------------------------------------------------------------
//----------------------CGRAMMAR类---------------------------------
//---------------------------------------------------------------
class CGRAMMAR 
{
public:
	void PrintTable();								//打印ACTION，GOTO表
	void FirstX(int *array,List<int> &first_set);	
	void First(int symbol,List<int> &first_set);	
	void PrintRuleTable();							//打印规则表
	char Decode(int num);							
	void OutPut(List<CItem> &list);					
	void GetSymbol(List<CItem> &item_set,List<int> &symbol_list);
	void PrintDFA();								//打印DFA
	void FromItoJ(CItem &item,List<CItem> &J);		
	int GO(const List<CItem> &I,int X,List<CItem> &J);	//GO(I,X)函数
	void ToItemSet();							
	void Closure(List<CItem> &kernel);				//COLSURE(I)
	int EncodeVn(char ch);						
	int EncodeVt(char ch);						
	void Encode(char *&buf);						//编码
	CGRAMMAR();										//默认构造函数
	virtual ~CGRAMMAR();
protected:
	int	*vt;										
	int	*vn;										
    char *vtstring;								
    char *vnstring;								
    int gncount;									
	List<Gener> gn_list;