yyparse.cpp

语法分析器lex和词法分析器yacc的C++语言实现 1.Lex （1）Lex输入文件的解析 （2）正规表达式的解析 （3）一个正规表达式到NFA的转换算法实现 （4）多个NFA的合并

#include<iostream>
#include<hash_map>
#include<stack>
#include<fstream>
#include<string>
#define E 40000
#define ACCEPT 0
#define SOURCE_END 40001
union SV
{

	int ival;
};
SV u[10];
SV yyval;
using namespace std;
extern int analysis(char *yytext,int n);
struct Sym
{
	int symbol;
	int state;
};
hash_map<int,int> signalTable;
int producerN[40]={1,6,5,1,1,1,1,1,1,1,1,1,1,4,2,3,1,2,1,1,1,2,2,3,1,1,1,1,2,4,4,4,3,5,3,1,1,1,1,5};
int pLeftSection[40]={34999,35000,35000,35001,35001,35001,35001,35001,35001,35001,35001,35002,35005,35003,35003,35004,35006,35006,35007,35007,35007,35008,35008,35011,35013,35013,35013,35013,35012,35012,35012,35012,35012,35009,35014,35015,35015,35015,35015,35010};
ifstream fin;
int actionTable[80][46]=
		{		{E,E,E,E,E,8,3,1,4,9,5,2,6,E,E,E,E,E,7,10,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-5,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-9,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-4,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-6,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-8,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-10,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,0},
		{-3,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-7,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{11,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,12,E,E,E,E,13,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,14,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-11,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,17,E,E,16,15,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,19,E,E,18,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,20,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{21,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,22,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{30,E,24,33,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,27,E,E,E,E,E,28,E,E,25,E,23,31,29,26,34,E,32,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-2},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,35,E,E,18,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,-12,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-14,E,E,36,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-16,E,-16,-16,E,-16,-16,-16,-16,-16,-16,-16,-16,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-16,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,37,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{30,E,24,33,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,27,E,E,E,E,E,28,E,E,E,39,38,31,29,26,34,E,32,E,E,E,E,E,E,E,E,E},
		{-20,E,-20,-20,E,-20,-20,-20,-20,-20,-20,-20,-20,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-20,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{40,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,41,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,44,45,42,46,43,47,E,E,E},
		{-19,E,-19,-19,E,-19,-19,-19,-19,-19,-19,-19,-19,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-19,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,-12,-12,-12,-12,E,E,E},
		{-18,E,-18,-18,E,-18,-18,-18,-18,-18,-18,-18,-18,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-18,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,48,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,49,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,50,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-1},
		{E,E,E,E,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,17,E,E,51,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{52,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,53,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,54,E,E},
		{-17,E,-17,-17,E,-17,-17,-17,-17,-17,-17,-17,-17,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-17,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-15},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,E,E,E,E,-12,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-28,E,E,E,E,E,E,55,E,E,E},
		{-25,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-27,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{56,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,57,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-24,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-26,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{58,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,59,E,E,E,E,E,E,E,E,60,E,E,E,E,E,E,E,E,E,E,E},
		{-22,E,-22,-22,E,-22,-22,-22,-22,-22,-22,-22,-22,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-22,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{52,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,53,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,61,E,E},
		{-21,E,-21,-21,E,-21,-21,-21,-21,-21,-21,-21,-21,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-21,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-13,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,-12,-12,-12,-12,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,62,65,63,66,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,64,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,67,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{68,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,69,E,E,E,E,E,E,E,70,E,E,E,E,E,E,E,E,71,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-23,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,-12,-12,-12,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,44,45,42,46,43,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-32,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,72,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-35,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-37,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{73,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,74,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-36,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-38,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,76,E,E,75,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,-12,-12,-12,-12,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-29,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-30,E,44,45,42,46,43,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-31,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,77,E,E,75,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-12,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-34,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{30,E,24,33,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,27,E,E,E,E,E,28,E,E,78,E,23,31,29,26,34,E,32,E,E,E,E,E,E,E,E,E},
		{-39,E,-39,-39,E,-39,-39,-39,-39,-39,-39,-39,-39,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-39,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{-33,E,-33,-33,E,-33,-33,-33,-33,-33,-33,-33,-33,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-33,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E},
		{30,E,24,33,E,8,3,1,4,9,5,2,6,E,E,E,E,E,E,27,E,E,E,E,E,28,E,E,E,79,38,31,29,26,34,E,32,E,E,E,E,E,E,E,E,E},
		{-15,E,-15,-15,E,-15,-15,-15,-15,-15,-15,-15,-15,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,-15,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E,E}};
int searchTable(int cstate,char symbol)
{
	return actionTable[cstate][symbol];
}

int readToken()
{
	if(fin.eof())
		return SOURCE_END;
	char buf[256];//不支持超过256个字符的符号
	int pos=0;
	bool isEnd=false;
	bool isToken=false;//与isOperator互斥
	bool isOperator=false;
	string ops("!@#$%^&*()+-=|[]{};':\",.<>/?");
	string wss("\t\n\r ");
	string letter("_0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");
	char c=fin.get();
	while(c==' '||c=='\t'||c=='\n'||c=='\r') c=fin.get();//滤掉空白符
	while(!isEnd)
	{
		if(c==-1)
		{
			buf[pos]='\0';
			isEnd=true;
			continue;
		}		if(ops.find(c)>=0&&ops.find(c)<ops.size())//表示当c不是正常字符时。
		{
			//进入非正常字符的处理过程
			if(isToken)
			{
				fin.unget();
				buf[pos]='\0';
				isEnd=true;
			}
			else
			{
				isOperator=true;
				buf[pos]=c;
				pos++;
				c=fin.get();
			}
			continue;
		}
		if(letter.find(c)>=0&&letter.find(c)<letter.size())
		{
			if(isOperator)
			{
				fin.unget();
				buf[pos]='\0';
				isEnd=true;
			}
			else
			{
				isToken=true;
				buf[pos]=c;
				pos++;
				c=fin.get();
			}
			continue;
		}
		if(wss.find(c)>=0&&wss.find(c)<wss.size())
		{
			buf[pos]='\0';
			isEnd=true;
		}
		
		
		else return -1;
	}
	return analysis(buf,strlen(buf));
}
void runaction(int num)
{
	switch(num)
	{
	}
}
void getvalue(int symbol,SV & val)
{
	switch(symbol)
	{
	case 30007:val.ival=30007;break;
	case 30015:val.ival=30015;break;
	case 30006:val.ival=30006;break;
	case 30014:val.ival=30014;break;
	case 30005:val.ival=30005;break;
	case 30013:val.ival=30013;break;
	case 30004:val.ival=30004;break;
	case 30012:val.ival=30012;break;
	case 30003:val.ival=30003;break;
	case 30011:val.ival=30011;break;
	case 30002:val.ival=30002;break;
	case 30010:val.ival=30010;break;
	case 30001:val.ival=30001;break;
	case 30009:val.ival=30009;break;
	case 30017:val.ival=30017;break;
	case 30000:val.ival=30000;break;
	case 30008:val.ival=30008;break;
	case 30016:val.ival=30016;break;
	}
}
int parse()
{