syntaxanalysis.c

编译原理的语法分析器

#include<string.h>
#define NONE -1
#define EOS '\0'

//
#define STRMAX 3000
#define SYMMAX 300
#define SIZE 3000
#define BSIZE 150

/*TERMINAL TOKEN*/
#define IF 129
#define THEN 130
#define ELSE 131
#define WHILE 132
#define DO 133
#define BEGIN 134
#define END 135

char buffer[SIZE];           // 缓冲区
char lexemes[STRMAX];
char digit[BSIZE];  //to store digit
char alp[BSIZE];    //to store alphabet
char c;             //currently reading char

int lastentry = 0;
int state=0,start=0;
int d=0;a=0;
int isk=0;

char* forward;           // 向前指针
char* lexeme_beginning;  // 词素开始指针
char *parent;            //parsing tree beginning POINTER

/* 定义符号表 */
struct entry
{
    char *lexptr;
    int token;
}symtable[SYMMAX];
//struct entry symtable[SYMMAX];

//TERMINAL TOKEN entry
struct entry terminal[]=  
{
	"if",IF,
	"then",THEN,
	"else",ELSE,
	"while",WHILE,
	"do",DO,
	"begin",BEGIN,
	"end",END,	
	"no",NONE
};

/* 回退amount个位置 */
char retract(int amount)  //retract the POINTER forward.
{ 
	if(*forward != '\x0')
	{
		forward -= amount;
	}
	return *forward;
}

/* 返回超前扫描字符 */
char nextchar()           //to read the nextchar.
{
    if(forward == NULL)  
    {
        forward = buffer; //*forward also point to the beginning of buffer
    }
    else forward++;        
    
    if(*forward == '\x0') //Indicate that the current position of *forward is at the end of your input
    {
        if( forward == &(buffer[SIZE - 1]) )
        {
            buffer[SIZE - 1] = '\x0';  //setting the end of buffer '\0'
            forward = buffer;          //point to the beginning of buffer again
            return *forward;           //return the position of *forward
        }
        else return '\x0';  //if the *forward is '\0'
		                    //and it's position is not beyond the size of buffer 
		                    //suggested it's the end of the buffer     
    }	
    return *forward;
}

/* 将关键字填入符号表 */
void init()       //read the TERMINAL token and insert into symtable.
{
    struct entry *p;
    for(p = terminal; p->token != NONE; p++)  //p point into the beginning of struct entry terminal.
    {
        insert(p->lexptr, p->token);
    }
}
/* 将标识符插入符号表中 */
int insert(char s[], int tok) //insert the TERMINAL token you defined into symtalbe.
{
    int len,lastchar=-1;      //lastchar, to return the position of current char.
    len = strlen(s);
    if(lastentry + 1 >= SYMMAX)       {printf("symtable full\n"); exit(0);}
    if(lastchar + len + 1 >= STRMAX)  {printf("lexemes array full\n");exit(0);}
	
    lastentry++;   //lastentry is the counter,to count the number of the TERMINAL token you defined in struct entry terminal.
    symtable[lastentry].token = tok;
    symtable[lastentry].lexptr = &lexemes[lastchar+1];
	
    lastchar = lastchar+len+1;  
    strcpy(symtable[lastentry].lexptr, s);//insert the token into symtable by copy the char
    return lastentry;      //return the number of the TERMINAL token.
}

/* 插入符号表，这里只是简单输出 */
int install_id() 
{
    int i,scmp;
	for(i = 0; i <lastentry; i++)//here lastentry is the number of your TERMINAL token in symtable
	{
		scmp =strcmp(terminal[i].lexptr, alp);//Compare your input with TERMINAL token in symtable.
		if(scmp!=0)       //not TERMINAL token, consider as ID.
		{   
			isk=1;       
		}
		else if(scmp==0)  //string compare return 0 indicated your input is TERMINAL token. 
		{ 
			isk=2;    
			break;
		}
	}		
	lexeme_beginning = forward;
}

/* 当前模式匹配失败，开始下一轮匹配 */
int fail()
{
    forward = lexeme_beginning;
    if(*forward == '\x0')
    {
       //add some statement here..
    }
    retract(1);
	
    switch(start)
    {
        case 9:  start= 12;  break;
		case 12: start= 20;  break;
		case 20: start= 25;  break;
    	case 25: start= 28;  break;   
        default:
            printf("Fail...\n");
            exit(0);      
    }
    return start;
}

/* 得到文件的下一个词素 */
char nexttoken()   //the state diagram
{
	while(1) {
		switch (state) 
			{   
			//alphabet
			case 9:  c = nextchar();    a=0; alp[a]=c; a++;                       
					if (isalpha(c)) 	state = 10;
					else {
						a--;
						state=fail();
					}
					break;
												
			case 10: c = nextchar();               alp[a]=c;  a++;		                             
					if (isalpha(c) || isdigit(c))  state = 10; 						
					else state = 11;
					break;

			case 11:
					c=retract(1);  alp[a-1]='\0';	                             
					install_id();	
					return c;	//return ID;

					
			//digit.digitE+-digit
			case 12: c=nextchar();   d=0;	digit[d]=c;d++;
				if(isdigit(c))
				{
					state=13;
				}
				else {
					d--;
					state=fail();
				}
			    break;

			case 13: c=nextchar();
				digit[d]=c;d++;
				if(isdigit(c))	    state = 13;
				else if(c == '.')	state = 14;
				else if(c == 'E')	state=16;
				else {
					d--;
					state=fail();
				}
				break;


			case 14: c=nextchar();    digit[d]=c;d++;
				if(isdigit(c))        state=15;
				else{
					d--;
					state=fail();
				}
				break;

			case 15: c=nextchar();  digit[d]=c;d++;
				if(isdigit(c))      state=15;
				else if (c=='E')    state=16;
				else{
					d--;
					state=fail();
				}
				break;

			case 16: c=nextchar();     digit[d]=c;d++;
				if(c=='+'||c=='-')     state=17;
				else if (c=isdigit(c)) state=18;
				else {
					d--;
					state=fail();
				}
				break;

			case 17: c=nextchar();   digit[d]=c;d++;
				if(isdigit(c))       state=18;
				else{
					d--;
					state=fail();
				}
				break;

			case 18: c=nextchar();  digit[d]=c;d++;
				if(isdigit(c))      state=18;
				else //state=19;     
				{			
					digit[d-1]='\0';
					c=retract(1);
					return c;    // return NUM;
				}
				break;

			//digit.digit
			case 20: c=nextchar();  d=0; digit[d]=c;  d++;     
				if(isdigit(c)) 	    state=21;
				else {
					d--;
					state=fail();
				}
				break;

			case 21: c=nextchar();  digit[d]=c;d++;
				if(isdigit(c))      state=21;
				else if (c=='.')    state=22;
				else {
					d--;
					state=fail();
				}
				break;

			case 22: c=nextchar();  digit[d]=c;d++;
				if(isdigit(c))      state=23;
				else {
					d--;
					state=fail();
				}
				break;

			case 23: c=nextchar();   digit[d]=c; d++;
				if (isdigit(c))	     state=23;
		/**/	else if(c=='E')
				{
                    c=retract(1);
					while(isdigit(c)|c=='.'){c=retract(1);}
					                  state=12;
				}
				else  //state=24;          
				{		
					digit[d-1]='\0';
					c=retract(1);
					return c;      // return NUM;
				}
				break;

            //digit 
			case 25: c=nextchar();   d=0; digit[d]=c; d++;
				if(isdigit(c)) 	     state=26;      
				else {
					d--;
					state=fail();
				}
				break;

			case 26: c=nextchar();  digit[d]=c; d++; 
				if(isdigit(c)) 	    state=26;       
		/***/	else if(c=='.')
				{
                    c=retract(1);
					while(isdigit(c)){c=retract(1);}
					                state=20;
				}	
		/***/	else if(c=='E')
				{
                    c=retract(1);
					while(isdigit(c)){c=retract(1);}
					                 state=12;
				}
				else//state=27
				{	
					digit[d-1]='\0';                	
					c=retract(1);  
					return c;   //return NUM;     
				}
				break;
		
			default: c=nextchar();	
				return c;
				break;
		}		
	}
}

#include "ParsingTree.h"  //INSERT PARSING TREE HERE

int main()
{
	int completed = 0;


	printf("list -> list ; stmt | stmt\n");
    printf("stmt -> IF expr THEN stmt\n");
	printf("      | IF expr THEN stmt ELSE stmt\n");
	printf("      | WHILE expr DO stmt\n");
	printf("      | BEGIN list END\n");
    printf("      | ID := expr\n");
	printf("expr -> expr + term | term\n");
	printf("term -> term * factor | factor\n");
	printf("factor -> (expr) | ID | NUM\n");

	printf("\nPLS INPUT:\n");
    init();                     //insert the terminal token into symtable.
	gets(buffer);               //put your input into buffer.
    forward = NULL;             //initialize the pointer forward.
    lexeme_beginning = buffer;  //*lexeme_beginning point to the beginning of buffer.
    
    while(!completed)
    {
	start = 9;
    printf("\nCONSTRUCT PARSING TREE FORM LIST...\n\n");
    parent=list();              //create parsing tree here.
	printf("\n\nfinished!\n");
	return;                     //the parsing tree has been created.
    }	
	free(lexemes);
	free(symtable);
	free(buffer);
	free(parent);
	
    getch();
}