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

void e();                     //E
void f();                     //F
void t();                     //T
void t1();                    //T'
void e1();                    //E'

char ch;
int Judg;                     //判斷是否為空

struct CSstrchar{
	char char_ch;
	struct CSstrchar *next;
}CSstrchar,*bb,*cc,*Temp;          //輸入串結構體定義     鏈:字符|指針 bb實體指針;cc替換存儲



//************************************************************************
void e(void)                       // E->TE'
{
	t();                          
	e1(); 
}

void t(void)
{
	f();
	t1();                          //T->FT'
}



//*********************************************************************
void e1(void)                       //E'->+TE'|ε
{
	if(bb->char_ch=='+')
	{
		bb=bb->next;
		t();
		e1();
	}
	else
		if(bb->char_ch=='#'||bb->char_ch==')')
			return;
		else
			Judg=0;
}

void f()
{
	if(bb->char_ch=='i')
		bb=bb->next;
	else
		if(bb->char_ch=='(')
		{
			bb=bb->next;
			e();
			if(bb->char_ch==')')
				bb=bb->next;
			else
				Judg=0;
		}
		else
			Judg=0;
}

void t1(void)                      //T'->*FT'|ε
{
	if(bb->char_ch=='*')
	{
		bb=bb->next;
		f();
		t1();
	}
	else
		if(bb->char_ch!='#' && bb->char_ch!=')' && bb->char_ch!='+')
			Judg=0;
}
//***********************************************************************



void main(void)
{   printf("\n________________________________________________________________________________\n                               語法分析器 V1.0\n________________________________________________________________________________\n");
    printf("根據文法4.2 :E->E+T|T\n             T->T*F|F\n             F->(E)|i\n編譯以下程序\n"); 
    printf("\n輸入一個字符串 :\n例如 :i+i,i*i    并已#號結束\n");
	
	Judg=1;	
	bb=malloc(sizeof(CSstrchar));
	bb->next=NULL;
	cc=bb; //bb輸入字符串指針 ;cc是替換存儲指針;
	do{
		ch=getchar();
		putchar(ch);
		if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')
		{
			Temp=malloc(sizeof(CSstrchar));
			Temp->next=NULL;
			Temp->char_ch=ch;
			bb->next=Temp;
			bb=bb->next;
		}
		else
		{
			Temp=cc->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!='#');
	cc=cc->next;
	bb=cc;
	e();
	if(bb->char_ch=='#'&&Judg)
		printf("\nOK!\n");
	else
		printf("\nError!\n");
}


















	
/*文法4.2存在左遞歸
直接消除左遞歸后變成：
            E->TE'
			E'->+TE'|ε
			T->FT'
            T'->*FT'|ε
			F->(E)|i
*/
/*
FIRST(F)={ (，i } 
FIRST(T’)={*,ε} 
FIRST(T)=FIRST(F)-{ε}={ (，i} 
FIRST(E’)={+,ε} 
FIRST(E)= FIRST(T)-{ε}={(，i} 
∴FIRST(TE’)=FIRST(T)-{ε}={(，i} 
    FIRST(+TE’)={+}           FIRST(ε)={ε} 
    FIRST(FT’)= FIRST(F)-{ε}={(，i} 
    FIRST(*FT’)={*}            FIRST(ε)={ε} 
    FIRST((E))={(}               FIRST(i)={i}

*/