parsingtree.h

编译原理的语法分析器

#ifndef ParsingTree
#define ParsingTree

char list();
char list1();   
char stmt();
char expr();
char expr1();
char term();
char term1();
char factor();
void MatchBeginEnd();
void MatchIfThenElse();
char ignorspace(c);
char match(c1);


//function will be used here.
char ignorspace(char c) //read the next char ignor the space.
{
	while(isspace(c)) {c=nextchar();} //c point to the next char while it's space.
	return c;
}

char match(char c1) //to check if c match the passing parameter c1.
{   
	char tempchar;  //to momerize the latest char while it's error.
	c=nextchar();  
	c=ignorspace(c);

	if(c==c1)
	{
		printf("< TERMINAL,%c>\n",c); //if match,it's TERMINAL token , print it.
	}
	else 
	{	
		tempchar=retract(1); //if not match let tempchar momerize it
		while(isspace(tempchar)){tempchar=retract(1);}		
		printf("\nError after CHRACTER '%c' !\n\n",tempchar);
		exit(0);
	}
	return c;
}


int matchend=0;
int matchdo=0;
int matchthen=0;
int matchelse=0;

/***********************CONSTRUCT THE PARSING TREE HERE*************************************/
//--------------------list()  decompose to  stmt() list'()----------------------------------
char list()               
{
	printf("list->stmt list'\n");
    //----------here is to read the next char, Ignor the space between them
	state=9;                  
	c=nextchar();
	c=ignorspace(c);
	c=retract(1);
	c=nexttoken();
    //-----------
	stmt();                                   //stmt     
	c=nextchar();
	list1();                                  //list'

	return c;
}

//--------------------list'()  decompose to  <1> ; stmt() list'()  OR  <2> ε---------------
char list1()             
{
	c=ignorspace(c);                  
	if(c=='\0')         //End of char
	{
		printf("list'->ε\n");                    //ε
	}
	else if(c==';')
	{
		c=retract(1);
		printf("list->; stmt list'\n");
		match(';');                               // ; 
	   //------------
		state=9;                  
		c=nextchar();
		c=ignorspace(c);
		if(c=='\0')
		{
			printf("\n\nYou have printed';' at the end of list,\npls construct another list OR erase ';'\n\n");
			exit(0);
		}
		c=retract(1);
		c=nexttoken();

		stmt();                                  //stmt
		c=nextchar();
		list1();                                 //list'
	}	
	else if(isalpha(c)&&(matchend>0)) 
	{
		c=retract(1); 
        printf("list'->ε\n");                   //ε
	}
	else               //(!isalpha(c))  //if it's not alphabet  e.g the character like '!@#$%^'
	{
		printf("\n\nError CHARACTER '%c' !\n",c);
		printf("To recover this mistake..\nYou can match ';' between two CHARACTERS to construct another statement,\nOr erase the space between them!\n");
		exit(0);	
	}
	return c;
}

//--------------------stmt()  decompose to four statement ---------------------------------
char stmt()
{
	//.................If expr THEN stmt (ELSE stmt)..........//
    if(strcmp(alp,"if")==0)   //to match IF
	{          
		MatchIfThenElse();
	}

	//..................stmt->WHILE expr DO stmt...............//
	else if(strcmp(alp,"while")==0)//to match WHILE
	{                  	
		matchdo=1;   //prepare to match do
		printf("stmt->WHILE expr DO stmt\n");             
		printf("< TERMINAL,%s>\n",alp);                //WHILE

			c=nextchar();
	        c=ignorspace(c);
			expr();                                     //expr

			state=9;                      
			c=nextchar();
			c=ignorspace(c);
			c=retract(1);
			c=nexttoken();
			if(matchdo) //match do while it have read TERMINAL 'WHILE' in previous.
			{
				if(strcmp(alp,"do")==0) 
				{
					printf("< TERMINAL,%s>\n",alp);     //DO
					matchdo=0;//match do over.set it

					state=9;                  
					c=nextchar();
					c=ignorspace(c);
					c=retract(1);
					c=nexttoken();
					stmt();                             //stmt
				}
				else //if there's no matched 'DO'
				{
					printf("\n\nError!\nPls match 'do' before '%s%s' to construct another statement,\nOr erase the space between them!\n",alp,digit);
					exit(0);
				}
			}		
	}

	//....................stmt->BEGIN list END................//
	else if(strcmp(alp,"begin")==0) //to match BEGIN      
	{
		 MatchBeginEnd();		
	}

	//....................stmt->ID:=expr........................//
	else if(isk==1)                              
	{		  
		      printf("stmt->ID:=expr\n");
		      printf("< ID,%s>\n",alp);        //ID
			  match(':');                      //match(':')
			  match('=');                      //mathc('=')
			  c=nextchar();
			  expr();		                   //expr()
	}
	return c;
}

//--------------------expr() decompose to  term() expr()-----------------------------------
char expr()         
{
	printf("expr->term expr'\n");
    term();                                      //term
	c=nextchar();
    expr1();                                     //expr'
	return c;
}

//--------------------expr'() decompose to  <1> + term() expr'() OR <2> ε------------------
char expr1()                    
{                        
    c=ignorspace(c);
	if(c=='+') {
		printf("expr'->+ term expr'\n");
		c=retract(1);
		match('+');                              // +
		c=nextchar();
		term();                                  //term()
		c=nextchar();
		expr1();                                 //expr'()
	}
	else  
	{
		printf("expr'->ε\n");                   //ε
		c=retract(1);	            
	}
	return c;
}

//--------------------term() decompose to  factor() term'()------------------------------------
char term()                
{
	printf("term->factor term'\n");
    factor();                                    //factor
    c=nextchar();
	term1();                                     //term'
	return c;
}

//--------------------term'() decompose to <1> * factor() term'() OR <2> ε---------------------
char term1()
{
	c=ignorspace(c);
	if(c=='*')
	{
		printf("term'->* factor term'\n");
		c=retract(1);
		match('*');                                // *
		c=nextchar();
		factor();                                  //factor()
		c=nextchar();
		term1();                                   //term'()
	}
	else //not '*' ,consider as ε,and  just skip it     
	{	
		printf("term'->ε\n");                     //ε
		c=retract(1);
	}   
    return c;
}

//--------------------factor decompose to <1> NUM <2> ID <3> '(' expr() ')'--------------------
char factor()                       
{  
	c=ignorspace(c);                                         
	if(isdigit(c)){	                                                          
		printf("factor->NUM\n");
		
		c=retract(1);                                  
		state=25;     //12  20  25     	 		
		c=nexttoken();
		printf("< NUM,%s>\n",digit);               //NUM                    	
	}
	else if(isalpha(c))                             
	{	            
		printf("factor->ID\n");
		c=retract(1);	
		state=9;    
		c=nexttoken();     
		if(isk==1)
		{
			printf("< ID,%s>\n",alp);              //ID
		}
		else
		{
			printf("\n'%s' is keyword or illegal!\n",alp);
			exit(0);
		}
	}
	else if(c=='(')                                // ( expr )
	{
		printf("factor->( expr )\n");
		c=retract(1);
		match('(');                                // ( 

		c=nextchar();	                  
		expr();                                    //expr
                            		
		c=nextchar();
		c=retract(1);                     
		match(')');	                               // ) 
	}
	else //not '(' ,alphabet , digit
	{
		printf("\nError on evaluation!\nPls use alphabet as ID ,digit as NUM,\nOr MATCHED PARENTHESIS to construct some expressions\n");    //evaluation wrong 
		exit(0);
	}
	return c;
}

/****************************SOME MATCH FUNCTIONS**************************************/
//---------------------match begin list() end--------------------------------------
void MatchBeginEnd()
{
	matchend++;//if matched BEGIN
	printf("stmt->BEGIN list END\n");
	printf("< TERMINAL,%s>\n",alp);
	list();                                        //list

	if(matchend!=0)  //To match END
	{
		state=9;
		c=nexttoken();
		c=ignorspace(c);
		if(strcmp(alp,"end")==0) //match END
		{
			printf("< TERMINAL,%s>\n",alp);         //END
			matchend--; //matched 'END'
		}
		else //if the character is alphabet but there's space between them (except 'end')
		{
			printf("\n\nError on Spacekey!\nPls match ';' between two CHARACTERS to construct another statement,\nOr erase the space between them!\n");
			exit(0);
		}
	}	
}

//---------------------match if expr() then stmt() <else stmt()>-----------------------------------
void MatchIfThenElse()
{
	printf("stmt->IF expr THEN stmt elsestmt\n"); 
	matchthen=1; //if matched IF
	printf("< TERMINAL,%s>\n",alp);                  //IF
	c=nextchar();
	c=ignorspace(c);
	expr();                                          //expr
	
	state=9;                      
	c=nextchar();
	c=ignorspace(c);
	c=retract(1);
	c=nexttoken();
	//...................THEN stmt <ELSE stmt>.....................................//
	if(matchthen!=0) //exist IF in previous,
	{	
		if(strcmp(alp,"then")==0)                
		{
			printf("< TERMINAL,%s>\n",alp);          //THEN
			matchthen=0;
			matchelse++;
			
			//printf("stmt->IF expr THEN stmt\n\;n")
			//-------------
			state=9;                  
			c=nextchar();
			c=ignorspace(c);
			c=retract(1);
			c=nexttoken();
			stmt();                                  //stmt
    //................<ELSE stmt>.................................//if possible
			if(matchelse!=0)//to match else 
			{
				c=nextchar();
				c=ignorspace(c);
			    //if(strcmp(alp,"else")==0)
          /* --------------------------------------
		      Here stupid method to match ELSE,
			  char to char ,one by one ...
	          No much better method have I thought,
			  But it's works   
		  ----------------------------------------*/
				if(c=='e')				
				{ c=nextchar();
					if(c=='l')
					{	c=nextchar();
						if(c=='s')
						{	c=nextchar();
							if(c=='e')
							{	c=nextchar();
								if(isspace(c))
								{
				       //printf("stmt->IF expr THEN stmt ELSE stmt\n\n");
				        printf("elsestmt->else stmt\n");		
						printf("< TERMINAL,else>\n");   //ELSE 
						matchelse--;

						//------------
					    state=9;                  
					    c=nextchar();
					    c=ignorspace(c);
					    c=retract(1);
					    c=nexttoken();
					    stmt();
								}
								else//not spacekey
								{	c=retract(5);
									printf("elsestmt->ε\n");
								}
							}
							else// not e
							{	c=retract(4);
								printf("elsestmt->ε\n"); 
							}
						}
						else//not s
						{   c=retract(3);
							printf("elsestmt->ε\n"); 
						}
					}
					else//not l
					{   c=retract(2);
                        printf("elsestmt->ε\n");
					}
				}//not e
				 else
				 {  c=retract(1);
				   printf("elsestmt->ε\n");   
				}
			}
            //else  no 'else' to match ,it's OK...
			//.............end ELSE stmt....................................//
		}
		else 
		{
			printf("\n\nError!\nPls match 'then' before '%s%s' to construct another statement,\nOr erase the space between them!\n",alp,digit);
			exit(0);
		}
	}
   //...........................end THEN stmt <ELSE stmt>...............................//	
}
#endif