/****************************************/
/*	程序名稱：	LR(0)分析程序			*/
/*	程序用途：	編譯原理實驗(五)		*/
/*	編寫日期：	2005年11月22日			*/
/*	實驗題目：	對下列文法				*/
/*				E->E+T|T				*/
/*				T->T*F|F				*/
/*				F->(E)|i				*/
/*				LR(0)分析程序			*/
/*	程序版本：	1.0	Final				*/
/*	程序作者：	黃記瑤 B0226047			*/
/*	作者郵箱：	hjy2920@163.com			*/
/****************************************/

/********************************************************/
/*		            程序相關說明						*/
/*      	0=+ 1=* 2=( 3=) 4=i 5=# 6=E 7=T 8=F			*/
/*														*/
/*			        	LR(0)分析表						*/
/*	--|----|----|----|-----|----|-----|---|----|----|	*/
/*	  |  + |  * |  ( |  )  |  i |  #  | E |  T | F  | 	*/
/*	0 |    |    | S4 |     | S5 |     | 1 |  2 | 3  |	*/
/*	1 | S6 |    |    |     |    | Acc |   |    |    |	*/
/*	2 | R2 | S7 | R2 | R2  | R2 | R2  |   |    |	|	*/
/*	3 | R4 | R4 | R4 | R4  | R4 | R4  |   |    |	|	*/
/*	4 |    |    | S4 |     | S5 |     | 8 |  2 | 3  |	*/
/*	5 | R6 | R6 | R6 | R6  | R6 | R6  |   |    |	|	*/
/*	6 |    |    | S4 |     | S5 |     |   |  9 | 3  |	*/
/*	7 |    |    | S4 |     | S5 |     |   |    | 10 |	*/
/*	8 | S6 |    |    | S11 |    |     |   |    |	|	*/
/*	9 | R1 | S7 | R1 | R1  | R1 | R1  |   |    |	|	*/
/* 10 | R3 | R3 | R3 | R3  | R3 | R3  |   |    |	|	*/
/* 11 | R5 | R5 | R5 | R5  | R5 | R5  |   |    |	|	*/
/*	--|----|----|----|-----|----|-----|---|----|----|	*/
/********************************************************/

#include "stdio.h"
#include "malloc.h"
#include "math.h"

struct Lchar{
	char char_ch;
	struct Lchar *next;
}Lchar,*p,*h,*temp,*top,*base;
struct Lint{
	int int_t;
	struct Lint *next;
}Lint,*itop,*ibase,*itemp;

int table[12][9]={{0,0,-4,0,-5,0,1,2,3},
				{-6,0,0,0,0,100,0,0,0},
				{12,-7,12,12,12,12,0,0,0},
				{14,14,14,14,14,14,0,0,0},
				{0,0,-4,0,-5,0,8,2,3},
				{16,16,16,16,16,16,0,0,0},
				{0,0,-4,0,-5,0,0,9,3},
				{0,0,-4,0,-5,0,0,0,10},
				{-6,0,0,-11,0,0,0,0,0},
				{11,-7,11,11,11,11,0,0,0},
				{13,13,13,13,13,13,0,0,0},
				{15,15,15,15,15,15,0,0,0}};
/*存儲LR(0)分析表，大于10為歸約，小于0為進棧，0表示出錯，1到10表示狀態轉移，100表示接受*/

char curchar;
char curtocmp;
int curstate;
int right;/*設置開關項，當出錯時為0*/
int i,j;

void push(char pchar)/*字符棧入棧函數*/
{
	temp=malloc(sizeof(Lchar));
	temp->char_ch=pchar;
	temp->next=top;
	top=temp;
}

void pop(void)/*字符棧出棧函數*/
{
	if(top->next!=NULL)
		top=top->next;
}

void ipop(void)/*狀態棧出棧函數*/
{
	if(itop->next!=NULL)
		itop=itop->next;
}

void ipush(int pint)
{
	itemp=malloc(sizeof(Lint));
	itemp->int_t=pint;
	itemp->next=itop;
	itop=itemp;
}

int changchartoint(char ch)/*將字符轉為數字，以得到算符優先值*/
{
	int t;
	switch(ch)
	{
		case '+':t=0;break;
		case '*':t=1;break;
		case '(':t=2;break;
		case ')':t=3;break;
		case 'i':t=4;break;
		case '#':t=5;break;
		case 'E':t=6;break;
		case 'T':t=7;break;
		case 'F':t=8;break;
	}
	return t;
}

void doforpush(int t)
{
	switch(t)
	{
	case 1:push('E');break;
	case 2:push('E');break;
	case 3:push('T');break;
	case 4:push('T');break;
	case 5:push('F');break;
	case 6:push('F');
	}
}

void dosome(void)
{
	int t;
	printf("\nCharStack\tCharLink\tStateStack\n");
	for(;;)
	{
		curchar=h->char_ch;
		curtocmp=top->char_ch;
		curstate=itop->int_t;
		i=changchartoint(curchar);
		t=table[curstate][i];		
		temp=top;
		printf("\n");
		for(;;)/*打印棧*/
		{
			printf("%c",temp->char_ch);
			if(temp->char_ch=='#')
				break;
			else
				temp=temp->next;
		}
		printf("\t");
		temp=h;
		for(;;)/*打印待比較的字符*/
		{
			printf("%c",temp->char_ch);		
			if(temp->char_ch=='#')
				break;
			else
				temp=temp->next;
		}
		printf("\t");
		itemp=itop;
		for(;;)/*打印狀態棧*/
		{
			printf("%d",itemp->int_t);		
			if(itemp->next==NULL)
				break;
			else
				itemp=itemp->next;
		}
		printf("\t");
		if(t==0)/*LR(0)分析表為0，出錯*/
		{
			right=0;
			break;			
		}
		else/*LR(0)分析表不為0*/
		{
			if(t<0)/*LR(0)分析表小于0，入棧*/
			{
				push(curchar);  /*字符入字符棧*/
				ipush(abs(t));  /*狀態棧入棧*/
				h=h->next;
			}
			else/*LR(0)分析表大于0，歸約*/
			{
				if(t==100)/*LR(0)分析表等于100，正確*/
					break;
				if(t==12||t==14||t==16)/*產生式右部和狀態出棧*/
				{
					pop();
					ipop();
				}
				else
				{
					pop();pop();pop();
					ipop();ipop();ipop();
				}                      /*產生式右部和狀態出棧*/
				doforpush(t-10);/*產生式左部出棧*/
				j=changchartoint(top->char_ch);
				curstate=itop->int_t;
				ipush(table[curstate][j]);/*狀態轉移，狀態入棧*/
			}
		}
	}
}
void main(void)
{
	char ch;
	base=malloc(sizeof(Lchar));
	base->next=NULL;
	base->char_ch='#';
	top=base;/*初始化字符棧*/
	ibase=malloc(sizeof(Lint));
	ibase->int_t=0;
	ibase->next=NULL;
	itop=ibase;/*初始化狀態棧*/
	h=malloc(sizeof(Lchar));
	h->next=NULL;
	p=h;
	do{				/*輸入待比較字符串，以'#'結束*/
		ch=getch();
		putch(ch);
		if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')/*輸入合法字符串*/
		{
			temp=malloc(sizeof(Lchar));
			temp->next=NULL;
			temp->char_ch=ch;
			h->next=temp;
			h=h->next;
		}
		else/*輸入不合法字符串*/
		{
			temp=p->next;
			printf("\nInput a wrong char!Input again:\n");
			for(;;)/*打印當前字符串*/
			{				
				if (temp!=NULL)
					printf("%c",temp->char_ch);						
				else
					break;
				temp=temp->next;
			}
		}
	}while(ch!='#');/*輸入待比較字符串，以'#'結束*/
	p=p->next;
	h=p;
	right=1;/*初始化開關項*/
	dosome();/*開始識別*/
	if(right)
		printf("\nOK!\n");
	else
		printf("\nError!\n");
	getch();
}