C++写的一个简单的语法分析器(分析C语言)

作者: niuox
发布时间:2015-06-11 20:23:59

本程序实现一个分析C语言的词法分析+语法分析。

注意:

1.文法简略,没有实现的部分,可以在此文法的基础上进行扩充,本程序的采用自顶向下的LL(1)文法。

2.可以自动实现求First 集和 Follow 集。

3.处终结符外(有些硬编码的成分),终结符的文法可以自定义,也就是说读者可以自定义文法。

4.为方便理解,C语言的文法描述写成中文。

5.程序将词法分析和语法分析结合起来,词法分析的结果作为语法分析的输入。

6.最终结果在控制台显示的有:词法分析、First集、Follow集、Select集,在preciateResult.txt 中写入了语法分析结果,在preciateTable.txt 中写入了预测分析表。

7.文法的词素之间必须有空格分开。

项目结构如下:


文法如下:

wenfa.txt:

<函数定义> -> <修饰词闭包> <类型> <变量> ( <参数声明> ) { <函数块> } <修饰词闭包> -> <修饰词> <修饰词闭包> | $ <修饰词> -> describe <类型> -> type <取地址> <取地址> -> <星号闭包> <星号闭包> -> <星号> <星号闭包> | $ <星号> -> * <变量> -> <标志符> <数组下标> <标志符> -> id <数组下标> -> [ <因式> ] | $ <因式> -> ( <表达式> ) | <变量> | <数字> <数字> -> digit <表达式> -> <因子> <项> <因子> -> <因式> <因式递归> <因式递归> -> * <因式> <因式递归> | / <因式> <因式递归> | $ <项> -> + <因子> <项> | - <因子> <项> | $ <参数声明> -> <声明> <声明闭包> | $ <声明> -> <修饰词闭包> <类型> <变量> <赋初值> <赋初值> -> = <右值> | $ <右值> -> <表达式> | { <多个数据> } <多个数据> -> <数字> <数字闭包> <数字闭包> -> , <数字> <数字闭包> | $ <声明闭包> -> , <声明> <声明闭包> | $ <函数块> -> <声明语句闭包> <函数块闭包> <声明语句闭包> -> <声明语句> <声明语句闭包> | $ <声明语句> -> <声明> ; <函数块闭包> -> <赋值函数> <函数块闭包> | <for循环> <函数块闭包> | <条件语句> <函数块闭包> | <函数返回> <函数块闭包> | $ <赋值函数> -> <变量> <赋值或函数调用> <赋值或函数调用> -> = <右值> ; | ( <参数列表> ) ; <参数列表> -> <参数> <参数闭包> <参数闭包> -> , <参数> <参数闭包> | $ <参数> -> <标志符> | <数字> | <字符串> <字符串> -> string <for循环> -> for ( <赋值函数> <逻辑表达式> ; <后缀表达式> ) { <函数块> } <逻辑表达式> -> <表达式> <逻辑运算符> <表达式> <逻辑运算符> -> < | > | == | != <后缀表达式> -> <变量> <后缀运算符> <后缀运算符> -> ++ | -- <条件语句> -> if ( <逻辑表达式> ) { <函数块> } <否则语句> <否则语句> -> else { <函数块> } | $ <函数返回> -> return <因式> ; 


词法分析头文件:

LexAnalysis.h

//LexAnalysis.h #ifndef _LEXANALYSIS_H #define _LEXANALYSIS_H  //关键字 #define AUTO 1 #define BREAK 2 #define CASE 3 #define CHAR 4 #define CONST 5 #define CONTINUE 6 #define DEFAULT 7 #define DO 8 #define DOUBLE 9 #define ELSE 10 #define ENUM 11 #define EXTERN 12 #define FLOAT 13 #define FOR 14 #define GOTO 15 #define IF 16 #define INT 17 #define LONG 18 #define REGISTER 19 #define RETURN 20 #define SHORT 21 #define SIGNED 22 #define SIZEOF 23 #define STATIC 24 #define STRUCT 25 #define SWITCH 26 #define TYPEDEF 27 #define UNION 28 #define UNSIGNED 29 #define VOID 30 #define VOLATILE 31 #define WHILE 32 #define KEY_DESC "关键字"  //标志符 #define IDENTIFER 40 #define IDENTIFER_DESC "标志符"  //常量 #define INT_VAL 51 //整形常量 #define CHAR_VAL 52 //字符常量 #define FLOAT_VAL 53 //浮点数常量 #define STRING_VAL 54 //双精度浮点数常量 #define MACRO_VAL 55 //宏常量 #define CONSTANT_DESC "常量"  //运算符 #define NOT 61   // ! #define BYTE_AND 62 //& #define COMPLEMENT 63 // ~ #define BYTE_XOR  64 // ^ #define MUL 65 // * #define DIV 66// / #define MOD 67 // % #define ADD 68 // + #define SUB 69 // - #define LES_THAN 70 // < #define GRT_THAN 71 // > #define ASG 72 // = #define ARROW 73 // -> #define SELF_ADD 74 // ++ #define SELF_SUB 75 // -- #define LEFT_MOVE 76 // << #define RIGHT_MOVE 77 // >> #define LES_EQUAL 78 // <= #define GRT_EQUAL 79 // >= #define EQUAL 80 // == #define NOT_EQUAL 81 // != #define AND 82 // && #define OR 83 // || #define COMPLETE_ADD 84 // += #define COMPLETE_SUB 85 // -= #define COMPLETE_MUL 86 // *= #define COMPLETE_DIV 87 // /= #define COMPLETE_BYTE_XOR 88 // ^= #define COMPLETE_BYTE_AND 89 // &= #define COMPLETE_COMPLEMENT 90 // ~= #define COMPLETE_MOD 91 //%= #define BYTE_OR 92 // |  #define OPE_DESC "运算符"  //限界符 #define LEFT_BRA 100 // ( #define RIGHT_BRA 101 // ) #define LEFT_INDEX 102 // [ #define RIGHT_INDEX 103 // ] #define L_BOUNDER 104 //  { #define R_BOUNDER 105 // } #define POINTER 106 // . #define JING 107 // # #define UNDER_LINE 108 // _ #define COMMA 109 // , #define SEMI 110 // ; #define SIN_QUE 111 // ' #define DOU_QUE 112 // "  #define CLE_OPE_DESC "限界符"  #define NOTE1 120 // "/**/"注释 #define NOTE2 121 // "//"注释 #define NOTE_DESC "注释"   #define HEADER 130 //头文件 #define HEADER_DESC "头文件"  //错误类型 #define FLOAT_ERROR "float表示错误" #define FLOAT_ERROR_NUM 1 #define DOUBLE_ERROR "double表示错误" #define DOUBLE_ERROR_NUM 2 #define NOTE_ERROR "注释没有结束符" #define NOTE_ERROR_NUM 3 #define STRING_ERROR "字符串常量没有结束符" #define STRING_ERROR_NUM 4 #define CHARCONST_ERROR "字符常量没有结束符" #define CHARCONST_ERROR_NUM 5 #define CHAR_ERROR "非法字符" #define CHAR_ERROR_NUM 6 #define LEFT_BRA_ERROR "'('没有对应项" #define LEFT_BRA_ERROR_NUM 7 #define RIGHT_BRA_ERROR "')'没有对应项" #define RIGHT_BRA_ERROR_NUM 8 #define LEFT_INDEX_ERROR "'['没有对应项" #define LEFT_INDEX_ERROR_NUM 9 #define RIGHT_INDEX_ERROR "']'没有对应项" #define RIGHT_INDEX_ERROR_NUM 10 #define L_BOUNDER_ERROR "'{'没有对应项" #define L_BOUNDER_ERROR_NUM 11 #define R_BOUNDER_ERROR "'}'没有对应项" #define R_BOUNDER_ERROR_NUM 12 #define PRE_PROCESS_ERROR "预处理错误" //头文件或者宏定义错误 #define PRE_PROCESS_ERROR_NUM  13  #define _NULL "无"  #define DESCRIBE 4000 #define TYPE 4001 #define STRING 4002 #define DIGIT 4003  struct NormalNode {     char content[30];//内容     char describe[30];//描述     int type;//种别码     int addr;//入口地址     int line;//所在行数     NormalNode * next;//下一个节点 };  void initKeyMapping(); void initOperMapping(); void initLimitMapping();  void initNode(); void createNewNode(char * content,char *descirbe,int type,int addr,int line); void createNewError(char * content,char *descirbe,int type,int line); int createNewIden(char * content,char *descirbe,int type,int addr,int line); void printNodeLink(); void printErrorLink(); void printIdentLink(); int mystrlen(char * word); void preProcess(char * word,int line); void close(); int seekKey(char * word); void scanner(); void BraMappingError();   #endif 

语法分析头文件:

SynAnalysis.h

//SynAnalysis.h #ifndef _SYNANALYSIS_H #define _SYNANALYSIS_H  #define GRAMMAR_ARROW 2000 //-> #define GRAMMAR_OR 2001 // | #define GRAMMAR_NULL 2002 //空值 #define GRAMMAR_SPECIAL 2003 //特殊符号# #define GRAMMAR_BASE 2010 //动态生成的基值  #define Stack_Size 5000  typedef struct {     int elem[Stack_Size];     int top; } SeqStack;  void initGrammer(); int seekCodeNum(char * word); void ceshi(); void First(); void Follow(); void Select(); void MTable(); void Analysis(); #endif 

词法分析Cpp文件:(与先前写过的一片博客相类似,改了部分)

LexAnalysis.cpp

//LexAnalysis.cpp #include <iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <vector> #include <iomanip> #include "LexAnalysis.h"  using namespace std;  int leftSmall = 0;//左小括号 int rightSmall = 0;//右小括号 int leftMiddle = 0;//左中括号 int rightMiddle = 0;//右中括号 int leftBig = 0;//左大括号 int rightBig = 0;//右大括号 int lineBra[6][1000] = {0};//括号和行数的对应关系,第一维代表左右6种括号 int static_iden_number = 0;//模拟标志符的地址,自增 //Token节点   NormalNode * normalHead;//首结点  //错误节点 struct ErrorNode {     char content[30];//错误内容     char describe[30];//错误描述     int type;     int line;//所在行数     ErrorNode * next;//下一个节点 };  ErrorNode * errorHead;//首节点  //标志符节点 struct IdentiferNode {     char content[30];//内容     char describe[30];//描述     int type;//种别码     int addr;//入口地址     int line;//所在行数     IdentiferNode * next;//下一个节点 }; IdentiferNode * idenHead;//首节点  vector<pair<const char *,int> > keyMap; vector<pair<const char *,int> > operMap; vector<pair<const char *,int> > limitMap;    //初始化C语言的关键字的集合 void initKeyMapping() {     keyMap.clear();     keyMap.push_back(make_pair("auto",AUTO));     keyMap.push_back(make_pair("break",BREAK));     keyMap.push_back(make_pair("case",CASE));     keyMap.push_back(make_pair("char",CHAR));     keyMap.push_back(make_pair("const",CONST));     keyMap.push_back(make_pair("continue",CONTINUE));     keyMap.push_back(make_pair("default",DEFAULT));     keyMap.push_back(make_pair("do",DO));     keyMap.push_back(make_pair("double",DOUBLE));     keyMap.push_back(make_pair("else",ELSE));     keyMap.push_back(make_pair("enum",ENUM));     keyMap.push_back(make_pair("extern",EXTERN));     keyMap.push_back(make_pair("float",FLOAT));     keyMap.push_back(make_pair("for",FOR));     keyMap.push_back(make_pair("goto",GOTO));     keyMap.push_back(make_pair("if",IF));     keyMap.push_back(make_pair("int",INT));     keyMap.push_back(make_pair("long",LONG));     keyMap.push_back(make_pair("register",REGISTER));     keyMap.push_back(make_pair("return",RETURN));     keyMap.push_back(make_pair("short",SHORT));     keyMap.push_back(make_pair("signed",SIGNED));     keyMap.push_back(make_pair("sizeof",SIZEOF));     keyMap.push_back(make_pair("static",STATIC));     keyMap.push_back(make_pair("struct",STRUCT));     keyMap.push_back(make_pair("switch",SWITCH));     keyMap.push_back(make_pair("typedef",TYPEDEF));     keyMap.push_back(make_pair("union",UNION));     keyMap.push_back(make_pair("unsigned",UNSIGNED));     keyMap.push_back(make_pair("void",VOID));     keyMap.push_back(make_pair("volatile",VOLATILE));     keyMap.push_back(make_pair("while",WHILE));      keyMap.push_back(make_pair("describe",DESCRIBE));     keyMap.push_back(make_pair("type",TYPE));     keyMap.push_back(make_pair("string",STRING));     keyMap.push_back(make_pair("digit",DIGIT)); } void initOperMapping() {     operMap.clear();     operMap.push_back(make_pair("!",NOT));     operMap.push_back(make_pair("&",BYTE_AND));     operMap.push_back(make_pair("~",COMPLEMENT));     operMap.push_back(make_pair("^",BYTE_XOR));     operMap.push_back(make_pair("*",MUL));     operMap.push_back(make_pair("/",DIV));     operMap.push_back(make_pair("%",MOD));     operMap.push_back(make_pair("+",ADD));     operMap.push_back(make_pair("-",SUB));     operMap.push_back(make_pair("<",LES_THAN));     operMap.push_back(make_pair(">",GRT_THAN));     operMap.push_back(make_pair("=",ASG));     operMap.push_back(make_pair("->",ARROW));     operMap.push_back(make_pair("++",SELF_ADD));     operMap.push_back(make_pair("--",SELF_SUB));     operMap.push_back(make_pair("<<",LEFT_MOVE));     operMap.push_back(make_pair(">>",RIGHT_MOVE));     operMap.push_back(make_pair("<=",LES_EQUAL));     operMap.push_back(make_pair(">=",GRT_EQUAL));     operMap.push_back(make_pair("==",EQUAL));     operMap.push_back(make_pair("!=",NOT_EQUAL));     operMap.push_back(make_pair("&&",AND));     operMap.push_back(make_pair("||",OR));     operMap.push_back(make_pair("+=",COMPLETE_ADD));     operMap.push_back(make_pair("-=",COMPLETE_SUB));     operMap.push_back(make_pair("*=",COMPLETE_MUL));     operMap.push_back(make_pair("/=",COMPLETE_DIV));     operMap.push_back(make_pair("^=",COMPLETE_BYTE_XOR));     operMap.push_back(make_pair("&=",COMPLETE_BYTE_AND));     operMap.push_back(make_pair("~=",COMPLETE_COMPLEMENT));     operMap.push_back(make_pair("%=",COMPLETE_MOD));     operMap.push_back(make_pair("|",BYTE_OR)); } void initLimitMapping() {     limitMap.clear();     limitMap.push_back(make_pair("(",LEFT_BRA));     limitMap.push_back(make_pair(")",RIGHT_BRA));     limitMap.push_back(make_pair("[",LEFT_INDEX));     limitMap.push_back(make_pair("]",RIGHT_INDEX));     limitMap.push_back(make_pair("{",L_BOUNDER));     limitMap.push_back(make_pair("}",R_BOUNDER));     limitMap.push_back(make_pair(".",POINTER));     limitMap.push_back(make_pair("#",JING));     limitMap.push_back(make_pair("_",UNDER_LINE));     limitMap.push_back(make_pair(",",COMMA));     limitMap.push_back(make_pair(";",SEMI));     limitMap.push_back(make_pair("'",SIN_QUE));     limitMap.push_back(make_pair("\"",DOU_QUE)); } void initNode() {     normalHead = new NormalNode();     strcpy(normalHead->content,"");     strcpy(normalHead->describe,"");     normalHead->type = -1;     normalHead->addr = -1;     normalHead->line = -1;     normalHead->next = NULL;      errorHead = new ErrorNode();     strcpy(errorHead->content,"");     strcpy(errorHead->describe,"");     errorHead->line = -1;     errorHead->next = NULL;      idenHead = new IdentiferNode();     strcpy(idenHead->content,"");     strcpy(idenHead->describe,"");     idenHead->type = -1;     idenHead->addr = -1;     idenHead->line = -1;     idenHead->next = NULL; }  void createNewNode(char * content,char *descirbe,int type,int addr,int line) {     NormalNode * p = normalHead;     NormalNode * temp = new NormalNode();      while(p->next!=NULL)     {         p = p->next;     }      strcpy(temp->content,content);     strcpy(temp->describe,descirbe);     temp->type = type;     temp->addr = addr;     temp->line = line;     temp->next = NULL;      p->next = temp; } void createNewError(char * content,char *descirbe,int type,int line) {     ErrorNode * p = errorHead;     ErrorNode * temp = new ErrorNode();      strcpy(temp->content,content);     strcpy(temp->describe,descirbe);     temp->type = type;     temp->line = line;     temp->next = NULL;     while(p->next!=NULL)     {         p = p->next;     }     p->next = temp; } //返回值是新的标志符的入口地址 int createNewIden(char * content,char *descirbe,int type,int addr,int line) {     IdentiferNode * p = idenHead;     IdentiferNode * temp = new IdentiferNode();     int flag = 0;     int addr_temp = -2;     while(p->next!=NULL)     {         if(strcmp(content,p->next->content) == 0)         {             flag = 1;             addr_temp = p->next->addr;         }         p = p->next;     }     if(flag == 0)     {         addr_temp = ++static_iden_number;//用自增来模拟入口地址     }     strcpy(temp->content,content);     strcpy(temp->describe,descirbe);     temp->type = type;     temp->addr = addr_temp;     temp->line = line;     temp->next = NULL;     p->next = temp;     return addr_temp; }  void printNodeLink() {     NormalNode * p = normalHead;     p = p->next;     cout<<"************************************分析表******************************"<<endl<<endl;     cout<<setw(30)<<"内容"<<setw(10)<<"描述"<<"\t"<<"种别码"<<"\t"<<"地址"<<"\t"<<"行号"<<endl;     while(p!=NULL)     {         if(p->type == IDENTIFER)         {             cout<<setw(30)<<p->content<<setw(10)<<p->describe<<"\t"<<p->type<<"\t"<<p->addr<<"\t"<<p->line<<endl;         }         else         {             cout<<setw(30)<<p->content<<setw(10)<<p->describe<<"\t"<<p->type<<"\t"<<"\t"<<p->line<<endl;         }         p = p->next;     }     cout<<endl<<endl; } /* 错误种类: 1.float表示错误 2.double表示错误 3.注释没有结束符 4.字符串常量没有结束符 5.字符常量没有结束符 6.非法字符 7.'('没有对应项 8.预处理错误 */ void printErrorLink() {     ErrorNode * p = errorHead;     p = p->next;     cout<<"************************************错误表******************************"<<endl<<endl;     cout<<setw(10)<<"内容"<<setw(30)<<"描述"<<"\t"<<"类型"<<"\t"<<"行号"<<endl;     while(p!=NULL)     {         cout<<setw(10)<<p->content<<setw(30)<<p->describe<<"\t"<<p->type<<"\t"<<p->line<<endl;         p = p->next;     }     cout<<endl<<endl; } //标志符表,有重复部分,暂不考虑 void printIdentLink() {     IdentiferNode * p = idenHead;     p = p->next;     cout<<"************************************标志符表******************************"<<endl<<endl;     cout<<setw(30)<<"内容"<<setw(10)<<"描述"<<"\t"<<"种别码"<<"\t"<<"地址"<<"\t"<<"行号"<<endl;     while(p!=NULL)     {         cout<<setw(30)<<p->content<<setw(10)<<p->describe<<"\t"<<p->type<<"\t"<<p->addr<<"\t"<<p->line<<endl;         p = p->next;     }     cout<<endl<<endl; } int mystrlen(char * word) {     if(*word == '\0')     {         return 0;     }     else     {         return 1+mystrlen(word+1);     } } //预处理,处理头文件和宏定义 void preProcess(char * word,int line) {     const char * include_temp = "include";     const char * define_temp = "define";     char * p_include,*p_define;     int flag = 0;     p_include = strstr(word,include_temp);     if(p_include!=NULL)     {         flag = 1;         int i;         for(i=7;;)         {             if(*(p_include+i) == ' ' || *(p_include+i) == '\t')             {                 i++;             }             else             {                 break;             }         }         createNewNode(p_include+i,HEADER_DESC,HEADER,-1,line);     }     else     {         p_define = strstr(word,define_temp);         if(p_define!=NULL)         {             flag = 1;             int i;             for(i=7;;)             {                 if(*(p_define+i) == ' ' || *(p_define+i) == '\t')                 {                     i++;                 }                 else                 {                     break;                 }             }             createNewNode(p_define+i,CONSTANT_DESC,MACRO_VAL,-1,line);         }     }     if(flag == 0)     {         createNewError(word,PRE_PROCESS_ERROR,PRE_PROCESS_ERROR_NUM,line);     } }  void close() {     //delete idenHead;     //delete errorHead;     //delete normalHead; }  int seekKey(char * word) {     for(int i=0; i<keyMap.size(); i++)     {         if(strcmp(word,keyMap[i].first) == 0)         {             return i+1;         }     }     return IDENTIFER; }  void scanner() {     char filename[30];     char ch;     char array[30];//单词长度上限是30     char * word;     int i;     int line = 1;//行数       FILE * infile;     printf("请输入要进行语法分析的C语言程序:\n");     scanf("%s",filename);     infile = fopen(filename,"r");     while(!infile)     {         printf("打开文件失败!\n");         return;     }     ch = fgetc(infile);     while(ch!=EOF)     {          i = 0;         //以字母或者下划线开头,处理关键字或者标识符         if((ch>='A' && ch<='Z') || (ch>='a' && ch<='z') || ch == '_')         {             while((ch>='A' && ch<='Z')||(ch>='a' && ch<='z')||(ch>='0' && ch<='9') || ch == '_')             {                 array[i++] = ch;                 ch = fgetc(infile);             }             word = new char[i+1];             memcpy(word,array,i);             word[i] = '\0';             int seekTemp = seekKey(word);             if(seekTemp!=IDENTIFER)             {                 createNewNode(word,KEY_DESC,seekTemp,-1,line);             }             else             {                 int addr_tmp = createNewIden(word,IDENTIFER_DESC,seekTemp,-1,line);                 createNewNode(word,IDENTIFER_DESC,seekTemp,addr_tmp,line);             }             fseek(infile,-1L,SEEK_CUR);//向后回退一位         }         //以数字开头,处理数字         else if(ch >='0' && ch<='9')         {             int flag = 0;             int flag2 = 0;             //处理整数             while(ch >='0' && ch<='9')             {                 array[i++] = ch;                 ch = fgetc(infile);             }             //处理float             if(ch == '.')             {                 flag2 = 1;                 array[i++] = ch;                 ch = fgetc(infile);                 if(ch>='0' && ch<='9')                 {                     while(ch>='0' && ch<='9')                     {                         array[i++] = ch;                         ch = fgetc(infile);                     }                 }                 else                 {                     flag = 1;                 }                  //处理Double                 if(ch == 'E' || ch == 'e')                 {                     array[i++] = ch;                     ch = fgetc(infile);                     if(ch == '+' || ch == '-')                     {                         array[i++] = ch;                         ch = fgetc(infile);                     }                     if(ch >='0' && ch<='9')                     {                         array[i++] = ch;                         ch = fgetc(infile);                     }                     else                     {                         flag = 2;                     }                 }              }             word = new char[i+1];             memcpy(word,array,i);             word[i] = '\0';             if(flag == 1)             {                 createNewError(word,FLOAT_ERROR,FLOAT_ERROR_NUM,line);             }             else if(flag == 2)             {                 createNewError(word,DOUBLE_ERROR,DOUBLE_ERROR_NUM,line);             }             else             {                 if(flag2 == 0)                 {                     createNewNode(word,CONSTANT_DESC,INT_VAL,-1,line);                 }                 else                 {                     createNewNode(word,CONSTANT_DESC,FLOAT_VAL,-1,line);                 }             }             fseek(infile,-1L,SEEK_CUR);//向后回退一位         }         //以"/"开头         else if(ch == '/')         {             ch = fgetc(infile);             //处理运算符"/="             if(ch == '=')             {                 createNewNode("/=",OPE_DESC,COMPLETE_DIV,-1,line);             }             //处理"/**/"型注释             else if(ch == '*')             {                 ch =  fgetc(infile);                 while(1)                 {                     while(ch != '*')                     {                         if(ch == '\n')                         {                             line++;                         }                         ch = fgetc(infile);                         if(ch == EOF)                         {                             createNewError(_NULL,NOTE_ERROR,NOTE_ERROR_NUM,line);                             return;                         }                     }                     ch = fgetc(infile);                     if(ch == '/')                     {                         break;                     }                     if(ch == EOF)                     {                         createNewError(_NULL,NOTE_ERROR,NOTE_ERROR_NUM,line);                         return;                     }                 }                 createNewNode(_NULL,NOTE_DESC,NOTE1,-1,line);             }             //处理"//"型注释             else if(ch == '/')             {                 while(ch!='\n')                 {                     ch = fgetc(infile);                     if(ch == EOF)                     {                         createNewNode(_NULL,NOTE_DESC,NOTE2,-1,line);                         return;                     }                 }                 line++;                 createNewNode(_NULL,NOTE_DESC,NOTE2,-1,line);                 if(ch == EOF)                 {                     return;                 }             }             //处理除号             else             {                 createNewNode("/",OPE_DESC,DIV,-1,line);             }         }         //处理常量字符串         else if(ch == '"')         {             createNewNode("\"",CLE_OPE_DESC,DOU_QUE,-1,line);             ch = fgetc(infile);             i = 0;             while(ch!='"')             {                 array[i++] = ch;                 if(ch == '\n')                 {                     line++;                 }                 ch = fgetc(infile);                 if(ch == EOF)                 {                     createNewError(_NULL,STRING_ERROR,STRING_ERROR_NUM,line);                     return;                 }             }             word = new char[i+1];             memcpy(word,array,i);             word[i] = '\0';             createNewNode(word,CONSTANT_DESC,STRING_VAL,-1,line);             createNewNode("\"",CLE_OPE_DESC,DOU_QUE,-1,line);         }         //处理常量字符         else if(ch == '\'')         {             createNewNode("\'",CLE_OPE_DESC,SIN_QUE,-1,line);             ch = fgetc(infile);             i = 0;             while(ch!='\'')             {                 array[i++] = ch;                 if(ch == '\n')                 {                     line++;                 }                 ch = fgetc(infile);                 if(ch == EOF)                 {                     createNewError(_NULL,CHARCONST_ERROR,CHARCONST_ERROR_NUM,line);                     return;                 }             }             word = new char[i+1];             memcpy(word,array,i);             word[i] = '\0';             createNewNode(word,CONSTANT_DESC,CHAR_VAL,-1,line);             createNewNode("\'",CLE_OPE_DESC,SIN_QUE,-1,line);         }         else if(ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n')         {             if(ch == '\n')             {                 line++;             }         }         else         {             if(ch == EOF)             {                 return;             }             //处理头文件和宏常量(预处理)             else if(ch == '#')             {                 while(ch!='\n' && ch!=EOF)                 {                     array[i++] = ch;                     ch = fgetc(infile);                 }                 word = new char[i+1];                 memcpy(word,array,i);                 word[i] = '\0';                 preProcess(word,line);                  fseek(infile,-1L,SEEK_CUR);//向后回退一位             }             //处理-开头的运算符             else if(ch == '-')             {                 array[i++] = ch;                 ch = fgetc(infile);                 if(ch >='0' && ch<='9')                 {                     int flag = 0;                     int flag2 = 0;                     //处理整数                     while(ch>='0' && ch<='9')                     {                         array[i++] = ch;                         ch = fgetc(infile);                     }                     //处理float                     if(ch == '.')                     {                         flag2 = 1;                         array[i++] = ch;                         ch = fgetc(infile);                         if(ch>='0' && ch<='9')                         {                             while(ch>='0' && ch<='9')                             {                                 array[i++] = ch;                                 ch = fgetc(infile);                             }                         }                         else                         {                             flag = 1;                         }                         //处理Double                         if(ch == 'E' || ch == 'e')                         {                             array[i++] = ch;                             ch = fgetc(infile);                             if(ch == '+' || ch == '-')                             {                                 array[i++] = ch;                                 ch = fgetc(infile);                             }                             if(ch >='0' && ch<='9')                             {                                 array[i++] = ch;                                 ch = fgetc(infile);                             }                             else                             {                                 flag = 2;                             }                         }                     }                     word = new char[i+1];                     memcpy(word,array,i);                     word[i] = '\0';                     if(flag == 1)                     {                         createNewError(word,FLOAT_ERROR,FLOAT_ERROR_NUM,line);                     }                     else if(flag == 2)                     {                         createNewError(word,DOUBLE_ERROR,DOUBLE_ERROR_NUM,line);                     }                     else                     {                         if(flag2 == 0)                         {                             createNewNode(word,CONSTANT_DESC,INT_VAL,-1,line);                         }                         else                         {                             createNewNode(word,CONSTANT_DESC,FLOAT_VAL,-1,line);                         }                     }                     fseek(infile,-1L,SEEK_CUR);//向后回退一位                 }                 else if(ch == '>')                 {                     createNewNode("->",OPE_DESC,ARROW,-1,line);                 }                 else if(ch == '-')                 {                     createNewNode("--",OPE_DESC,SELF_SUB,-1,line);                 }                 else if(ch == '=')                 {                     createNewNode("--",OPE_DESC,SELF_SUB,-1,line);                 }                 else                 {                     createNewNode("-",OPE_DESC,SUB,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理+开头的运算符             else if(ch == '+')             {                 ch = fgetc(infile);                 if(ch == '+')                 {                     createNewNode("++",OPE_DESC,SELF_ADD,-1,line);                 }                 else if(ch == '=')                 {                     createNewNode("+=",OPE_DESC,COMPLETE_ADD,-1,line);                 }                 else                 {                     createNewNode("+",OPE_DESC,ADD,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理*开头的运算符             else if(ch == '*')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("*=",OPE_DESC,COMPLETE_MUL,-1,line);                 }                 else                 {                     createNewNode("*",OPE_DESC,MUL,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理按^开头的运算符             else if(ch == '^')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("^=",OPE_DESC,COMPLETE_BYTE_XOR,-1,line);                 }                 else                 {                     createNewNode("^",OPE_DESC,BYTE_XOR,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理%开头的运算符             else if(ch == '%')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("%=",OPE_DESC,COMPLETE_MOD,-1,line);                 }                 else                 {                     createNewNode("%",OPE_DESC,MOD,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理&开头的运算符             else if(ch == '&')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("&=",OPE_DESC,COMPLETE_BYTE_AND,-1,line);                 }                 else if(ch == '&')                 {                     createNewNode("&&",OPE_DESC,AND,-1,line);                 }                 else                 {                     createNewNode("&",OPE_DESC,BYTE_AND,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理~开头的运算符             else if(ch == '~')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("~=",OPE_DESC,COMPLETE_COMPLEMENT,-1,line);                 }                 else                 {                     createNewNode("~",OPE_DESC,COMPLEMENT,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理!开头的运算符             else if(ch == '!')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("!=",OPE_DESC,NOT_EQUAL,-1,line);                 }                 else                 {                     createNewNode("!",OPE_DESC,NOT,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理<开头的运算符             else if(ch == '<')             {                 ch = fgetc(infile);                 if(ch == '<')                 {                     createNewNode("<<",OPE_DESC,LEFT_MOVE,-1,line);                 }                 else if(ch == '=')                 {                     createNewNode("<=",OPE_DESC,LES_EQUAL,-1,line);                 }                 else                 {                     createNewNode("<",OPE_DESC,LES_THAN,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理>开头的运算符             else if(ch == '>')             {                 ch = fgetc(infile);                 if(ch == '>')                 {                     createNewNode(">>",OPE_DESC,RIGHT_MOVE,-1,line);                 }                 else if(ch == '=')                 {                     createNewNode(">=",OPE_DESC,GRT_EQUAL,-1,line);                 }                 else                 {                     createNewNode(">",OPE_DESC,GRT_THAN,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             //处理|开头的运算符             else if(ch == '|')             {                 ch = fgetc(infile);                 if(ch == '|')                 {                     createNewNode("||",OPE_DESC,OR,-1,line);                 }                 else                 {                     createNewNode("|",OPE_DESC,BYTE_OR,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             else if(ch == '=')             {                 ch = fgetc(infile);                 if(ch == '=')                 {                     createNewNode("==",OPE_DESC,EQUAL,-1,line);                 }                 else                 {                     createNewNode("=",OPE_DESC,ASG,-1,line);                     fseek(infile,-1L,SEEK_CUR);                 }             }             else if(ch == '(')             {                 leftSmall++;                 lineBra[0][leftSmall] = line;                 createNewNode("(",CLE_OPE_DESC,LEFT_BRA,-1,line);             }             else if(ch == ')')             {                 rightSmall++;                 lineBra[1][rightSmall] = line;                 createNewNode(")",CLE_OPE_DESC,RIGHT_BRA,-1,line);             }             else if(ch == '[')             {                 leftMiddle++;                 lineBra[2][leftMiddle] = line;                 createNewNode("[",CLE_OPE_DESC,LEFT_INDEX,-1,line);             }             else if(ch == ']')             {                 rightMiddle++;                 lineBra[3][rightMiddle] = line;                 createNewNode("]",CLE_OPE_DESC,RIGHT_INDEX,-1,line);             }             else if(ch == '{')             {                 leftBig++;                 lineBra[4][leftBig] = line;                 createNewNode("{",CLE_OPE_DESC,L_BOUNDER,-1,line);             }             else if(ch == '}')             {                 rightBig++;                 lineBra[5][rightBig] = line;                 createNewNode("}",CLE_OPE_DESC,R_BOUNDER,-1,line);             }             else if(ch == '.')             {                 createNewNode(".",CLE_OPE_DESC,POINTER,-1,line);             }             else if(ch == ',')             {                 createNewNode(",",CLE_OPE_DESC,COMMA,-1,line);             }             else if(ch == ';')             {                 createNewNode(";",CLE_OPE_DESC,SEMI,-1,line);             }             else             {                 char temp[2];                 temp[0] = ch;                 temp[1] = '\0';                 createNewError(temp,CHAR_ERROR,CHAR_ERROR_NUM,line);             }         }         ch = fgetc(infile);     } } void BraMappingError() {     if(leftSmall != rightSmall)     {         int i = (leftSmall>rightSmall) ? (leftSmall-rightSmall) : (rightSmall - leftSmall);         bool  flag = (leftSmall>rightSmall) ? true : false;         if(flag)         {             while(i--)             {                 createNewError(_NULL,LEFT_BRA_ERROR,LEFT_BRA_ERROR_NUM,lineBra[0][i+1]);             }         }         else         {             while(i--)             {                 createNewError(_NULL,RIGHT_BRA_ERROR,RIGHT_BRA_ERROR_NUM,lineBra[1][i+1]);             }         }     }     if(leftMiddle != rightMiddle)     {         int i = (leftMiddle>rightMiddle) ? (leftMiddle-rightMiddle) : (rightMiddle - leftMiddle);         bool flag = (leftMiddle>rightMiddle) ? true : false;         if(flag)         {             while(i--)             {                 createNewError(_NULL,LEFT_INDEX_ERROR,LEFT_INDEX_ERROR_NUM,lineBra[2][i+1]);             }         }         else         {             while(i--)             {                 createNewError(_NULL,RIGHT_INDEX_ERROR,RIGHT_INDEX_ERROR_NUM,lineBra[3][i+1]);             }         }     }     if(leftBig != rightBig)     {         int i = (leftBig>rightBig) ? (leftBig-rightBig) : (rightBig - leftSmall);         bool flag = (leftBig>rightBig) ? true : false;         if(flag)         {             while(i--)             {                 createNewError(_NULL,L_BOUNDER_ERROR,L_BOUNDER_ERROR_NUM,lineBra[4][i+1]);             }         }         else         {             while(i--)             {                 createNewError(_NULL,R_BOUNDER_ERROR,R_BOUNDER_ERROR_NUM,lineBra[5][i+1]);             }         }     } }  

语法分析Cpp代码:

//SynAnalysis.cpp #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> #include <fstream> #include <vector> #include <conio.h> #include "LexAnalysis.h" #include "SynAnalysis.h"  using namespace std;  #define Max_Proc 500 #define Max_Length 500  #define Max_NonTer 60 #define Max_Ter 60 #define Max_Length2 100  int procNum = 0; //proc的维数都是从1开始的 int proc[Max_Proc][Max_Length];//产生式的数组,里边存储了终结符或者非终结符对应的编号 int first[Max_Proc][Max_Length]; int follow[Max_Proc][Max_Length]; int select[Max_Proc][Max_Length]; int M[Max_NonTer][Max_Ter][Max_Length2];  int connectFirst[Max_Length];//将某些First集结合起来的集合   int firstVisit[Max_Proc];//记录某非终结符的First集是否已经求过 int followVisit[Max_Proc];//记录某非终结符的Follow集是否已经求过  int empty[Max_Proc];//可推出空的非终结符的编号 int emptyRecu[Max_Proc];//在求可推出空的非终结符的编号集时使用的防治递归的集合 int followRecu[Max_Proc];//在求Follow集时使用的防治递归的集合  //extern的部分代表可能出现的终结符和其编号 extern vector<pair<const char *,int> > keyMap; extern vector<pair<const char *,int> > operMap; extern vector<pair<const char *,int> > limitMap;  extern NormalNode * normalHead;//首结点  fstream resultfile;  vector<pair<const char *,int> > nonTerMap;//非终结符映射表,不可重复的 vector<pair<const char *,int> > terMap;//终结符映射表,不可重复的 vector<pair<const char *,int> > specialMap;//文法中的特殊符号映射表,包括-> | $(空)   void initSpecialMapping() {     specialMap.clear();     specialMap.push_back(make_pair("->",GRAMMAR_ARROW));     specialMap.push_back(make_pair("|",GRAMMAR_OR));     specialMap.push_back(make_pair("$",GRAMMAR_NULL));     specialMap.push_back(make_pair("#",GRAMMAR_SPECIAL));  } const char * searchMapping(int num) {     //标志符     if(num == IDENTIFER)     {         return "id";     }     //处理文法中的特殊符号     for(int i = 0; i<specialMap.size(); i++)     {         if(specialMap[i].second == num)         {             return specialMap[i].first;         }     }     //处理非终结符     for(int i=0; i<nonTerMap.size(); i++)     {         if(nonTerMap[i].second == num)         {             return nonTerMap[i].first;         }     }     //处理终结符     for(int i=0; i<terMap.size(); i++)     {         if(terMap[i].second == num)         {             return terMap[i].first;         }     }  }  //动态生成非终结符,在基点的基础上,确保不和终结符冲突 int dynamicNonTer(char *word) {     int i = 0;     int dynamicNum;     for(i=0; i<nonTerMap.size(); i++)     {         if(strcmp(word,nonTerMap[i].first) == 0)         {             return nonTerMap[i].second;         }     }     if(i == nonTerMap.size())     {         if(i == 0)         {             dynamicNum = GRAMMAR_BASE;             nonTerMap.push_back(make_pair(word,dynamicNum));         }         else         {             dynamicNum = nonTerMap[nonTerMap.size()-1].second + 1;             nonTerMap.push_back(make_pair(word,dynamicNum));         }     }     return dynamicNum; } //判断某个标号是不是非终结符的标号,1代表是,0代表否 int inNonTer(int n) {     for(int i=0; i<nonTerMap.size(); i++)     {         if(nonTerMap[i].second == n)         {             return 1;         }     }     return 0; } //判断某个标号是不是终结符的标号,1代表是,0代表否 int inTer(int n) {     for(int i=0; i<terMap.size(); i++)     {         if(terMap[i].second == n)         {             return 1;         }     }     return 0; } //判断某个标号在不在此时的empty集中,1代表是,0代表否 int inEmpty(int n) {     //当前Empty集的长度     int emptyLength = 0;     for(emptyLength = 0;; emptyLength++)     {         if(empty[emptyLength] == -1)         {             break;         }     }     for(int i = 0; i<emptyLength; i++)     {         if(empty[i] == n)         {             return 1;         }     }     return 0;  } //判断某个标号在不在此时的emptyRecu集中,1代表是,0代表否 int inEmptyRecu(int n) {     //当前Empty集的长度     int emptyLength = 0;     for(emptyLength = 0;; emptyLength++)     {         if(emptyRecu[emptyLength] == -1)         {             break;         }     }     for(int i = 0; i<emptyLength; i++)     {         if(emptyRecu[i] == n)         {             return 1;         }     }     return 0; } //判断某个标号在不在此时的followRecu集中,1代表是,0代表否 int inFollowRecu(int n) {     int followLength = 0;     for(followLength = 0;; followLength++)     {         if(followRecu[followLength] == -1)         {             break;         }     }     for(int i = 0; i<followLength; i++)     {         if(followRecu[i] == n)         {             return 1;         }     }     return 0; }  //判断某个标号是不是在产生式的右边 int inProcRight(int n,int * p) {     //注意这里默认是从3开始     for(int i=3;; i++)     {         if(p[i] == -1)         {             break;         }         if(p[i] == n)         {             return 1;         }     }     return 0; }  int seekCodeNum(char * word) {     //处理文法中的特殊符号     for(int i = 0; i<specialMap.size(); i++)     {         if(strcmp(word,specialMap[i].first) == 0)         {             return specialMap[i].second;         }     }     //先搜索终结符映射表中有没有此终结符     for(int i=0; i<terMap.size(); i++)     {         if(strcmp(word,terMap[i].first) == 0)         {             return terMap[i].second;         }     }     for(int i = 0; i<keyMap.size(); i++)     {         if(strcmp(word,keyMap[i].first) == 0)         {             terMap.push_back(make_pair(word,keyMap[i].second));             return keyMap[i].second;         }     }      for(int i = 0; i<operMap.size(); i++)     {         if(strcmp(word,operMap[i].first) == 0)         {             terMap.push_back(make_pair(word,operMap[i].second));             return operMap[i].second;         }     }      for(int i = 0; i<limitMap.size(); i++)     {         if(strcmp(word,limitMap[i].first) == 0)         {             terMap.push_back(make_pair(word,limitMap[i].second));             return limitMap[i].second;         }     }      if(strcmp(word,"id")==0)     {         //处理标志符         terMap.push_back(make_pair(word,IDENTIFER));         return IDENTIFER;     }     else     {         //处理关键字、运算符、限界符表,即非终结符         return dynamicNonTer(word);     } } //分割" | "文法 void splitProc(int p[][Max_Length],int &line,int orNum) {     if(p[line][1] == -1 || orNum == 0)     {         return;     }     int head = p[line][1];     int push = p[line][2];     int length = 0;     int right,left;     int lineTrue = line + orNum;     for(length = 3;;length++)     {         if(p[line][length] == -1)         {             break;         }     }     length--;     for(left = length,right = length;left>=2;)     {         if(p[line][left] == GRAMMAR_OR || left == 2)         {             p[line + orNum][1] = head;             p[line + orNum][2] = push;             for(int i=left+1;i<=right;i++)             {                 p[line+orNum][i-left+2] = p[line][i];             }             p[line+orNum][right-left+3] = -1;             right = left = left-1;             orNum--;         }         else         {             left--;         }     }     line = lineTrue; } void initGrammer() {     FILE * infile;     char ch;     char array[30];     char * word;     int i;     int codeNum;     int line = 1;     int count = 0;     int orNum = 0;     infile = fopen("wenfa.txt","r");     if(!infile)     {         printf("文法打开失败!\n");         return;     }     initSpecialMapping();     nonTerMap.clear();     terMap.clear();      memset(proc,-1,sizeof(proc));     memset(first,-1,sizeof(first));     memset(follow,-1,sizeof(follow));     memset(select,-1,sizeof(select));      memset(connectFirst,-1,sizeof(connectFirst));      memset(firstVisit,0,sizeof(firstVisit));//非终结符的first集还未求过     memset(followVisit,0,sizeof(followVisit));//非终结符的follow集还未求过      memset(empty,-1,sizeof(empty));     memset(emptyRecu,-1,sizeof(emptyRecu));     memset(followRecu,-1,sizeof(followRecu));      memset(M,-1,sizeof(M));      ch = fgetc(infile);     i = 0;     while(ch!=EOF)     {         i = 0;         while(ch == ' ' || ch == '\t')         {             ch = fgetc(infile);         }         while(ch!=' ' && ch!= '\n' && ch!=EOF)         {             array[i++] = ch;             ch = fgetc(infile);         }         while(ch == ' ' || ch == '\t')         {             ch = fgetc(infile);         }         word = new char[i+1];         memcpy(word,array,i);         word[i] = '\0';         codeNum = 0;         codeNum = seekCodeNum(word);         if(codeNum!=0)         {             count++;             if(codeNum == GRAMMAR_OR)             {                 orNum++;             }             proc[line][count] = codeNum;          }         //原本需要回退一个字符,由于是冗余字符,不回退         if(ch == '\n')         {             splitProc(proc,line,orNum);//将" | "文法进行拆分             count = 0;             orNum = 0;             line++;             ch = fgetc(infile);         }     }     procNum = line - 1;     printf("************************************C语言文法******************************\n\n");     for(int i=1; i<line; i++)     {         for(int j=1; j<Max_Length; j++)         {             if(proc[i][j]!=-1)             {                 printf("%s ",searchMapping(proc[i][j]));             }             else             {                 break;             }         }         printf("\n");     }     printf("\n************************************文法终结符******************************\n\n");     for(int i=0; i<terMap.size(); i++)     {         printf("%s ",terMap[i].first);     }     printf("\n");     printf("\n************************************文法非终结符******************************\n\n");     for(int i=0; i<nonTerMap.size(); i++)     {         printf("%s ",nonTerMap[i].first);     }     printf("\n"); } //将s集合合并至d集合中,type = 1代表包括空($),type = 2代表不包括空 void merge(int *d,int *s,int type) {     int flag = 0;     for(int i = 0;; i++)     {         flag = 0;         if(s[i] == -1)         {             break;         }         int j = 0;         for(j = 0;; j++)         {             if(d[j] == -1)             {                 break;             }             if(d[j] == s[i])             {                 flag = 1;                 break;             }         }         if(flag == 1)         {             continue;         }         if(type == 1)         {             d[j] = s[i];         }         else         {             if(s[i] != GRAMMAR_NULL)             {                 d[j] = s[i];             }         }         d[j + 1] = -1;     } }  void nullSet(int currentNum) {     int temp[2];     for(int j = 1; j<=procNum; j++)     {         //如果右边的第一个是该字符,并且长度只有1         if(proc[j][3] == currentNum && proc[j][4] == -1)         {             temp[0] = proc[j][1];             temp[1] = -1;             merge(empty,temp,1);             nullSet(proc[j][1]);         }     } } //判断该非终结符是否能推出空,但终结符也可能传入,但没关系 int reduNull(int currentNon) {     int temp[2];     int result = 1;     int mark = 0;     temp[0] = currentNon;     temp[1] = -1;     merge(emptyRecu,temp,1);//先将此符号并入防递归集合中     if(inEmpty(currentNon) == 1)     {         return 1;     }      for(int j = 1; j<=procNum; j++)     {         if(proc[j][1] == currentNon)         {             int rightLength = 0;             //先求出右部的长度             for(rightLength = 3;; rightLength++)             {                 if(proc[j][rightLength] == -1)                 {                     break;                 }             }             rightLength--;             //如果长度为1,并且已经求过             if(rightLength - 2 == 1 && inEmpty(proc[j][rightLength]))             {                 return 1;             }             //如果长度为1,并且是终结符             else if(rightLength -2 == 1 && inTer(proc[j][rightLength]))             {                 return 0;             }             //如果长度超过了2             else             {                 for(int k=3; k<=rightLength; k++)                 {                     if(inEmptyRecu(proc[j][k]))                     {                         mark = 1;                     }                 }                 if(mark == 1)                 {                     continue;                 }                 else                 {                     for(int k=3; k<=rightLength; k++)                     {                         result*= reduNull(proc[j][k]);                         temp[0] = proc[j][k];                         temp[1] = -1;                         merge(emptyRecu,temp,1);//先将此符号并入防递归集合中                     }                 }             }             if(result == 0)             {                 continue;             }             else if(result == 1)             {                 return 1;             }         }     }     return 0; }  //求first集,传入的参数是在非终结符集合中的序号 void firstSet(int i) {     int k = 0;     int currentNon = nonTerMap[i].second;//当前的非终结符标号     //依次遍历全部产生式     for(int j = 1; j<=procNum; j++) //j代表第几个产生式     {         //找到该非终结符的产生式         if(currentNon == proc[j][1])//注意从1开始         {             //当右边的第一个是终结符或者空的时候             if(inTer(proc[j][3]) == 1 || proc[j][3] == GRAMMAR_NULL)             {                 //并入当前非终结符的first集中                 int temp[2];                 temp[0] = proc[j][3];                 temp[1] = -1;//其实是模拟字符串操作的手段                 merge(first[i],temp,1);             }             //当右边的第一个是非终结符的时候             else if(inNonTer(proc[j][3]) == 1)             {                 //如果遇到左递归形式的,直接放过?                 if(proc[j][3] == currentNon)                 {                     continue;                 }                 //记录下右边第一个非终结符的位置                 for(k=0;; k++)                 {                     if(nonTerMap[k].second == proc[j][3])                     {                         break;                     }                  }                 //当右边第一个非终结符还未访问过的时候                 if(firstVisit[k] == 0)                 {                     firstSet(k);                     firstVisit[k] = 1;                 }                 merge(first[i],first[k],2);//如果first[k]此时有空值的话,暂时不把空值并入first[i]中                 int rightLength = 0;                 //先求出右部的长度                  for(rightLength = 3;; rightLength++)                 {                     if(proc[j][rightLength] == -1)                     {                         break;                     }                 }                 //到目前为止,只求出了右边的第一个(还不包括空的部分),For循环处理之后的                 for(k = 3; k<rightLength; k++)                 {                     emptyRecu[0] = -1;//相当于初始化这个防递归集合                      //如果右部的当前字符能推出空并且还不是最后一个字符,就将之后的一个字符并入First集中                     if(reduNull(proc[j][k]) == 1 && k<rightLength -1)                     {                         int u = 0;                         for(u=0;; u++)                         {                             //注意是记录下一个符号的位置                             if(nonTerMap[u].second == proc[j][k+1])                             {                                 break;                             }                         }                         if(firstVisit[u] == 0)                         {                             firstSet(u);                             firstVisit[u] = 1;                         }                         merge(first[i],first[u],2);                     }                     //到达最后一个字符,并且产生式右部都能推出空,将$并入First集中                     else if(reduNull(proc[j][k]) == 1 && k == rightLength -1)                     {                         int temp[2];                         temp[0] = GRAMMAR_NULL;                         temp[1] = -1;//其实是模拟字符串操作的手段                         merge(first[i],temp,1);                     }                     else                     {                         break;                     }                 }             }         }     }     firstVisit[i] = 1; } void First() {     //先求出能直接推出空的非终结符集合     nullSet(GRAMMAR_NULL);     printf("\n");     for(int i=0; i<nonTerMap.size(); i++)     {         firstSet(i);     }     printf("\n************************************First集******************************\n\n");     for(int i=0; i<nonTerMap.size(); i++)     {         printf("First[%s] = ",nonTerMap[i].first);         for(int j=0;; j++)         {             if(first[i][j] == -1)             {                 break;             }             printf("%s ",searchMapping(first[i][j]));         }         printf("\n");     } } //将First结合起来的函数 void connectFirstSet(int *p) {     int i = 0;     int flag = 0;     int temp[2];     //如果P的长度为1     if(p[1] == -1)     {         if(p[0] == GRAMMAR_NULL)         {             connectFirst[0] = GRAMMAR_NULL;             connectFirst[1] = -1;         }         else         {             for(i=0; i<nonTerMap.size(); i++)             {                 if(nonTerMap[i].second == p[0])                 {                     flag = 1;                     merge(connectFirst,first[i],1);                     break;                 }             }             //也可能是终结符             if(flag == 0)             {                 for(i=0; i<terMap.size(); i++)                 {                     if(terMap[i].second == p[0])                     {                         temp[0] = terMap[i].second;                         temp[1] = -1;                         merge(connectFirst,temp,2);//终结符的First集就是其本身                         break;                     }                 }             }         }     }     //如果p的长度大于1     else     {         for(i=0; i<nonTerMap.size(); i++)         {             if(nonTerMap[i].second == p[0])             {                 flag = 1;                 merge(connectFirst,first[i],2);                 break;             }         }         //也可能是终结符         if(flag == 0)         {             for(i=0; i<terMap.size(); i++)             {                 if(terMap[i].second == p[0])                 {                     temp[0] = terMap[i].second;                     temp[1] = -1;                     merge(connectFirst,temp,2);//终结符的First集就是其本身                     break;                 }             }         }         flag = 0;         int length = 0;         for(length = 0;; length++)         {             if(p[length] == -1)             {                 break;             }         }         for(int k=0; k<length; k++)         {             emptyRecu[0] = -1;//相当于初始化这个防递归集合              //如果右部的当前字符能推出空并且还不是最后一个字符,就将之后的一个字符并入First集中             if(reduNull(p[k]) == 1 && k<length -1)             {                 int u = 0;                 for(u=0; u<nonTerMap.size(); u++)                 {                     //注意是记录下一个符号的位置                     if(nonTerMap[u].second == p[k+1])                     {                         flag = 1;                         merge(connectFirst,first[u],2);                         break;                     }                 }                 //也可能是终结符                 if(flag == 0)                 {                     for(u=0; u<terMap.size(); u++)                     {                         //注意是记录下一个符号的位置                         if(terMap[u].second == p[k+1])                         {                             temp[0] = terMap[i].second;                             temp[1] = -1;                             merge(connectFirst,temp,2);                             break;                         }      
                    

标签: C++ C语言
来源:http://blog.csdn.net/niuox/article/details/8216186

推荐: