parsell_1.cpp

词法分析

#include "parseLL_1.h"
bool first[GrammarTokenNum][TmlTypeNum];
bool follow[GrammarTokenNum][TmlTypeNum+1];//增加最后一项为$
bool changesAnyFollow=true;
int p;//指针求stringFrist
int M[NontmlTypeNum][TmlTypeNum+1];//加上$ 分析表
bool currentGrammarFrist[TmlTypeNum]={0};
bool contineFrist;
bool changesAnyFrist=true;
int analyseStack[MaxStackDepth + 1]; /*分析栈*/
int linespStack[MaxStackDepth + 1];//记录当前token的linesp
StreeNode *str[MaxStackDepth + 1];  //纪录语法树的节点
int linesp=0;//
int topAnalyse; /*分析栈顶*/
TokenType currToken;


int Grammar [GrammarNum][GrammarMaxLength]={   
	{program ,declaration_list},
	{declaration_list , declaration, declaration_list_ },
	{declaration_list_ , declaration ,declaration_list_ },
	{declaration_list_ ,EMPTY},
	{declaration ,INT, ID, declaration_ },//
	{declaration ,fun_declaration_ },//
//	{declaration , var_declaration},
//	{declaration , fun_declaration},
    {declaration_ , var_declaration},//+declaration_ 
    {declaration_ , fun_declaration},//
//	{var_declaration,type_specifier, ID, var_declaration_},//-type_specifier
	{var_declaration,SEMI},//-var_declaration_
//	{type_specifier ,  INT },//-type_specifier
//	{type_specifier ,  VOID},
//	{fun_declaration ,  type_specifier ,ID ,LPAREN , params ,RPAREN },
//	{fun_declaration ,  compound_stmt},
	{var_declaration,LINDEX,NUM,RINDEX,SEMI},      //
    {fun_declaration ,LPAREN , params ,RPAREN ,compound_stmt},//
	{fun_declaration_ ,VOID,ID,LPAREN , params ,RPAREN ,compound_stmt},//+fun_declaration_ 
	{params ,  param_list},
	{params ,  VOID},
	{param_list , param, param_list_},
	{param_list_ , COMMA, param ,param_list_ },
	{param_list_ , EMPTY },
//	{param , type_specifier, ID, param_},
    {param , INT, ID, param_ },//
	{param_ , LINDEX, RINDEX},
	{param_ , EMPTY},
	{compound_stmt ,  LBRACE ,local_declarations, statement_list,RBRACE },
//	{local_declarations , var_declaration, local_declarations },
	{local_declarations , INT,ID,var_declaration, local_declarations },//
	{local_declarations , EMPTY},
	{statement_list ,   statement,  statement_list },
	{statement_list ,   EMPTY},
	{statement ,  expression_stmt},
	{statement ,  compound_stmt },
	{statement ,  selection_stmt},
	{statement ,   iteration_stmt },
	{statement ,   return_stmt},
	{expression_stmt ,  expression,SEMI},
	{expression_stmt ,  SEMI },
	{selection_stmt , IF, LPAREN,  expression ,RPAREN  ,statement  ,selection_stmt_},
	{selection_stmt_ , EMPTY},//保证悬挂else问题的解决
	{selection_stmt_ , ELSE, statement},
	{iteration_stmt , WHILE,LPAREN, expression,RPAREN ,statement},
	{return_stmt , RETURN ,return_stmt_},
	{return_stmt_ , SEMI },
	{return_stmt_ , expression,SEMI},
	{expression ,  var, ASSIGN ,expression },
	{expression ,  simple_expression},
	{var , ID ,var_},
	{var_ , LINDEX, expression,RINDEX },
	{var_ , EMPTY},
	{simple_expression ,  additive_expression ,simple_expression_},
	{simple_expression_ , relop, additive_expression},
	{simple_expression_ , EMPTY},
	{relop , LT },
	{relop , GT  },
	{relop , LE },
	{relop , GE },
	{relop , EQ},
	{relop , NOEQ },
	{additive_expression , term, additive_expression_},
	{additive_expression_ , addop, term ,additive_expression_   },
	{additive_expression_ , EMPTY },
	{addop ,  PLUS },
	{addop ,  MINUS},
	{term ,   factor, term_},
	{term_ ,  mulop, factor, term_},
	{term_ ,   EMPTY},
	{mulop ,  TIMES},
	{mulop ,  OVER},
	{factor ,  LPAREN, expression,RPAREN  },
	{factor ,   var },
	{factor ,  call },
	{factor ,  NUM},
	{call ,  ID,LPAREN ,args,RPAREN },
	{args ,  arg_list},
	{args ,  EMPTY},
	{arg_list , expression, arg_list_},
	{arg_list_ , COMMA ,expression, arg_list_ },
	{arg_list_ , EMPTY}
};
void InitStack()
{
	int i;
	/*分析栈的初始化*/
	for(i = 0; i < MaxStackDepth; i++)
		analyseStack[i] = -1;
	analyseStack[0] = ENDFILE; /*ENDFILE()入栈*/
	analyseStack[1] = program; /*初始符入栈*/
	linespStack[0]=0;
	linespStack[1]=0;
	topAnalyse = 1;
}
void printGrammar()
{ int i=0,j=0;
for (i=0;i<GrammarNum;i++)
{   printf("%d ->",Grammar[i][0]);
for(j=1;(Grammar[i][j]!=0);j++)
printf("%d  ",Grammar[i][j]);

printf("\n");
}
}
void printToken1(int i)
{
	switch(i)
	{
	case program : printf("program");break;
    case declaration_list:printf("declaration_list");break;
	case declaration_list_  : printf("declaration_list_ ");break;
    case declaration:printf("declaration");break;
	case var_declaration : printf("var_declaration");break;
 //   case var_declaration_ :printf("var_declaration_ ");break;
	case declaration_      :printf("declaration_  ");break;//
    case fun_declaration_  :printf("fun_declaration_  ");break;//
//	case type_specifier : printf("type_specifier");break;
    case fun_declaration:printf("fun_declaration");break;
	case params : printf("params");break;
    case param_list :printf("param_list");break;
	case param_list_:printf("param_list_");break;
	case param : printf("param");break;
    case param_:printf("param_");break;
    case compound_stmt:printf("compound_stmt");break;
	case local_declarations : printf("local_declarations");break;
    case statement_list:printf("statement_list");break;
	case statement : printf("statement");break;
    case expression_stmt:printf("expression_stmt");break;
	case selection_stmt : printf("selection_stmt");break;
    case selection_stmt_:printf("selection_stmt_");break;
	case iteration_stmt : printf("iteration_stmt");break;
    case return_stmt:printf("return_stmt");break;
	case return_stmt_:printf("return_stmt_");break;
	case expression:printf("expression");break;
    case var:printf("var");break;
	case var_:printf("var_");break;
	case simple_expression:printf("simple_expression");break;
	case simple_expression_:printf("simple_expression_");break;
	case relop:printf("relop");break;
	case additive_expression:printf("additive_expression");break;
	case additive_expression_:printf("additive_expression_");break;
	case addop:printf("addop");break;
	case term:printf("term");break;
	case term_:printf("term_");break;
	case mulop:printf("mulop");break;
	case factor:printf("factor");break;
	case call:printf("call");break;
	case args:printf("args");break;
	case arg_list:printf("arg_list");break;
	case arg_list_:printf("arg_list_");break;
	case ENDFILE:printf("ENDFILE");break;
	case ERROR:printf("ERROR");break;
	case IF:printf("if");break;
	case ELSE:printf("else");break;
	case INT:printf("int");break;
	case RETURN:printf("return");break;
	case VOID:printf("void");break;
	case WHILE:printf("while");break;
	case ID:printf("ID");break;
	case NUM:printf("NUM");break;
	case ASSIGN:printf("=");break;
	case EQ:printf("==");break;
	case LT:printf("<");break;
	case GT:printf(">");break;
	case PLUS:printf("+");break;
	case MINUS:printf("-");break;
	case TIMES:printf("*");break;
	case OVER:printf("/");break;
	case LPAREN:printf("(");break;
	case RPAREN:printf(")");break;
	case SEMI:printf(";");break;
	case COMMA:printf(",");break;
	case LINDEX:printf("[");break;
	case RINDEX:printf("]");break;
	case LE:printf("<=");break;
	case GE:printf(">=");break;
	case LBRACE:printf("{");break;
	case RBRACE:printf("}");break;
	case NOEQ:printf("!=");break;
	case EMPTY:printf("empty");break;
	case 70:printf("$");break;
	default :printf("BIGWRONG!");
	}

}
void printToken2(int i)
{
	switch(i+ENDFILE)
	{
	case ENDFILE:printf("ENDFILE");break;
	case ERROR:printf("ERROR");break;
	case IF:printf("if");break;
	case ELSE:printf("else");break;
	case INT:printf("int");break;
	case RETURN:printf("return");break;
	case VOID:printf("void");break;
	case WHILE:printf("while");break;
	case ID:printf("ID");break;
	case NUM:printf("NUM");break;
	case ASSIGN:printf("=");break;
	case EQ:printf("==");break;
	case LT:printf("<");break;
	case GT:printf(">");break;
	case PLUS:printf("+");break;
	case MINUS:printf("-");break;
	case TIMES:printf("*");break;
	case OVER:printf("/");break;
	case LPAREN:printf("(");break;
	case RPAREN:printf(")");break;
	case SEMI:printf(";");break;
	case COMMA:printf(",");break;
	case LINDEX:printf("[");break;
	case RINDEX:printf("]");break;
	case LE:printf("<=");break;
	case GE:printf(">=");break;
	case LBRACE:printf("{");break;
	case RBRACE:printf("}");break;
	case NOEQ:printf("!=");break;
	case EMPTY:printf("empty");break;
	case 70:printf("$");break;
	default :printf("BIGWRONG!");
	}

}
void printToken3(int i)
{
	switch(i)
	{
	case program : fprintf(parse,"program");break;
    case declaration_list:fprintf(parse,"declaration_list");break;
	case declaration_list_  :fprintf(parse,"declaration_list_ ");break;
    case declaration:fprintf(parse,"declaration");break;
	case var_declaration : fprintf(parse,"var_declaration");break;
//    case var_declaration_ :fprintf(parse,"var_declaration_ ");break;
    case declaration_  :fprintf(parse,"declaration_  ");break;
    case fun_declaration_  :fprintf(parse,"fun_declaration_  ");break;
//	case type_specifier : fprintf(parse,"type_specifier");break;
    case fun_declaration:fprintf(parse,"fun_declaration");break;
	case params : fprintf(parse,"params");break;
    case param_list :fprintf(parse,"param_list");break;
	case param_list_:fprintf(parse,"param_list_");break;
	case param :fprintf(parse,"param");break;
    case param_:fprintf(parse,"param_");break;
    case compound_stmt:fprintf(parse,"compound_stmt");break;
	case local_declarations : fprintf(parse,"local_declarations");break;
    case statement_list:fprintf(parse,"statement_list");break;
	case statement : fprintf(parse,"statement");break;
    case expression_stmt:fprintf(parse,"expression_stmt");break;
	case selection_stmt : fprintf(parse,"selection_stmt");break;
    case selection_stmt_:fprintf(parse,"selection_stmt_");break;
	case iteration_stmt : fprintf(parse,"iteration_stmt");break;
    case return_stmt:fprintf(parse,"return_stmt");break;
	case return_stmt_:fprintf(parse,"return_stmt_");break;
	case expression:fprintf(parse,"expression");break;
    case var:fprintf(parse,"var");break;
	case var_:fprintf(parse,"var_");break;
	case simple_expression:fprintf(parse,"simple_expression");break;
	case simple_expression_:fprintf(parse,"simple_expression_");break;
	case relop:fprintf(parse,"relop");break;
	case additive_expression:fprintf(parse,"additive_expression");break;
	case additive_expression_:fprintf(parse,"additive_expression_");break;
	case addop:fprintf(parse,"addop");break;
	case term:fprintf(parse,"term");break;
	case term_:fprintf(parse,"term_");break;
	case mulop:fprintf(parse,"mulop");break;
	case factor:fprintf(parse,"factor");break;
	case call:fprintf(parse,"call");break;
	case args:fprintf(parse,"args");break;
	case arg_list:fprintf(parse,"arg_list");break;
	case arg_list_:fprintf(parse,"arg_list_");break;
	case ENDFILE:fprintf(parse,"ENDFILE");break;
	case ERROR:fprintf(parse,"ERROR");break;
	case IF:fprintf(parse,"if");break;
	case ELSE:fprintf(parse,"else");break;
	case INT:fprintf(parse,"int");break;
	case RETURN:fprintf(parse,"return");break;
	case VOID:fprintf(parse,"void");break;
	case WHILE:fprintf(parse,"while");break;
	case ID:fprintf(parse,"ID");break;
	case NUM:fprintf(parse,"NUM");break;
	case ASSIGN:fprintf(parse,"=");break;
	case EQ:fprintf(parse,"==");break;
	case LT:fprintf(parse,"<");break;
	case GT:fprintf(parse,">");break;
	case PLUS:fprintf(parse,"+");break;
	case MINUS:fprintf(parse,"-");break;
	case TIMES:fprintf(parse,"*");break;
	case OVER:fprintf(parse,"/");break;
	case LPAREN:fprintf(parse,"(");break;
	case RPAREN:fprintf(parse,")");break;
	case SEMI:fprintf(parse,";");break;
	case COMMA:fprintf(parse,",");break;
	case LINDEX:fprintf(parse,"[");break;
	case RINDEX:fprintf(parse,"]");break;
	case LE:fprintf(parse,"<=");break;
	case GE:fprintf(parse,">=");break;
	case LBRACE:fprintf(parse,"{");break;
	case RBRACE:fprintf(parse,"}");break;
	case NOEQ:fprintf(parse,"!=");break;
	case EMPTY:fprintf(parse,"empty");break;
	case 70:fprintf(parse,"$");break;
	default :fprintf(parse,"BIGWRONG!");//Never happen
	}

}
void printToken4(int i,const char* tokenString )
{
	switch(i)
	{
	case program : fprintf(stree,"program");break;
    case declaration_list:fprintf(stree,"declaration_list");break;
	case declaration_list_  : fprintf(stree,"declaration_list_ ");break;
    case declaration:fprintf(stree,"declaration");break;
	case var_declaration : fprintf(stree,"var_declaration");break;
//    case var_declaration_ :printf("var_declaration_ ");break;
	case declaration_       :fprintf(stree,"declaration_  ");break;
    case fun_declaration_  :fprintf(stree,"fun_declaration_  ");break;
//	case type_specifier : printf("type_specifier");break;
    case fun_declaration:fprintf(stree,"fun_declaration");break;
	case params : fprintf(stree,"params");break;
    case param_list :fprintf(stree,"param_list");break;
	case param_list_:fprintf(stree,"param_list_");break;
	case param : fprintf(stree,"param");break;
    case param_:fprintf(stree,"param_");break;
    case compound_stmt:fprintf(stree,"compound_stmt");break;
	case local_declarations : fprintf(stree,"local_declarations");break;
    case statement_list:fprintf(stree,"statement_list");break;
	case statement : fprintf(stree,"statement");break;
    case expression_stmt:fprintf(stree,"expression_stmt");break;
	case selection_stmt : fprintf(stree,"selection_stmt");break;
    case selection_stmt_:fprintf(stree,"selection_stmt_");break;
	case iteration_stmt : fprintf(stree,"iteration_stmt");break;
    case return_stmt:fprintf(stree,"return_stmt");break;
	case return_stmt_:fprintf(stree,"return_stmt_");break;
	case expression:fprintf(stree,"expression");break;
    case var:fprintf(stree,"var");break;
	case var_:fprintf(stree,"var_");break;
	case simple_expression:fprintf(stree,"simple_expression");break;
	case simple_expression_:fprintf(stree,"simple_expression_");break;
	case relop:fprintf(stree,"relop");break;
	case additive_expression:fprintf(stree,"additive_expression");break;
	case additive_expression_:fprintf(stree,"additive_expression_");break;
	case addop:fprintf(stree,"addop");break;
	case term:fprintf(stree,"term");break;
	case term_:fprintf(stree,"term_");break;
	case mulop:fprintf(stree,"mulop");break;
	case factor:fprintf(stree,"factor");break;
	case call:fprintf(stree,"call");break;
	case args:fprintf(stree,"args");break;
	case arg_list:fprintf(stree,"arg_list");break;
	case arg_list_:fprintf(stree,"arg_list_");break;
	case IF:
    case ELSE:
    case INT:
    case RETURN:
    case VOID:
    case WHILE:
      fprintf(stree,
         "reserved word: %s",tokenString);
      break;
    case ASSIGN: fprintf(stree,"="); break;
    case LT: fprintf(stree,"<"); break;
	case GT: fprintf(stree,"<="); break;
	case LE: fprintf(stree,">"); break;
	case GE: fprintf(stree,">="); break;
    case EQ: fprintf(stree,"=="); break;
    case NOEQ: fprintf(stree,"!="); break;
    case LPAREN: fprintf(stree,"("); break;
    case RPAREN: fprintf(stree,")"); break;
    case LINDEX: fprintf(stree,"["); break;
    case RINDEX: fprintf(stree,"]"); break;
    case LBRACE: fprintf(stree,"{"); break;
    case RBRACE: fprintf(stree,"}"); break;
	case COMMA: fprintf(stree,","); break;
    case SEMI: fprintf(stree,";"); break;
    case PLUS: fprintf(stree,"+"); break;
    case MINUS: fprintf(stree,"-"); break;
    case TIMES: fprintf(stree,"*"); break;
    case OVER: fprintf(stree,"/"); break;
    case ENDFILE: fprintf(stree,"EOF"); break;
    case NUM:
     fprintf(stree,
          "NUM, val= %s",tokenString);
      break;
    case ID:
      fprintf(stree,
          "ID, name= %s",tokenString);
      break;
    case ERROR:
      fprintf(stree,
          "ERROR: %s",tokenString);
      break;
    default: /* should never happen */
      fprintf(stree,"Unknown token: %d\n",i);
	}
}
void printFirstSet()
{ int i=0,j=0;
printf("\n");
for (i=0;i<GrammarTokenNum;i++)//不打印$
{   	printf("%d first(",i);
	    printToken1(i);
		printf("):	");
	for(j=0;j<TmlTypeNum;j++)
	{
		if (first[i][j]==1)
		{
			printToken2(j);
			printf("   ");
		}
	}	printf("\n");
}
getchar();


}
void getfirst()//求非终结符first set 
{    /*************初始化终结符的Fisrt***********/ 
	for ( int tmlnum=ENDFILE;tmlnum <= EMPTY;tmlnum++)
	{	first[tmlnum][tmlnum-ENDFILE]=true;}
	/* printf("first[%d][%d]=%d  ",tmlnum,tmlnum-ENDFILE,1);
	   }
	printFirstSet();*/
	while(changesAnyFrist==true)
	{ 
		changesAnyFrist=false;
		for (int GrammarChoice=0;GrammarChoice<GrammarNum ;GrammarChoice++)
		{
			int A=Grammar[GrammarChoice][0];
			int k=1;
			contineFrist=true;
			while( contineFrist==true&&Grammar[GrammarChoice][k]!=0)
			{
				/******ADD First(Xk)-{empty} to First(A) (A->X1X2..Xk)****/
				for (int j=0;j!=EMPTY-NontmlTypeNum;j++)
				{  if(first[A][j]!=(first[A][j]|first[Grammar[GrammarChoice][k]][j]))
				{
					first[A][j]=first[A][j]|first[Grammar[GrammarChoice][k]][j];
					changesAnyFrist=true;
				//	printf("first[%d][%d]=%d 所在的%d语法，在第%d终结符 \n ",A,j+1,first[A][j],GrammarChoice+2,k);	
				}  
				}