本程序實現一個分析C語言的詞法分析+語法分析。
注意：
1.文法簡略，沒有實現的部分，可以在此文法的基礎上進行擴充，本程序的采用自頂向下的LL(1)文法。
2.可以自動實現求First 集和 Follow 集。
3.處終結符外（有些硬編碼的成分），終結符的文法可以自定義，也就是說讀者可以自定義文法。
4.為方便理解，C語言的文法描述寫成中文。
5.程序將詞法分析和語法分析結合起來，詞法分析的結果作為語法分析的輸入。
6.最終結果在控制台顯示的有：詞法分析、First集、Follow集、Select集，在preciateResult.txt 中寫入了語法分析結果，在preciateTable.txt 中寫入了預測分析表。
7.文法的詞素之間必須有空格分開。
項目結構如下：
文法如下：
wenfa.txt:
[plain]
<函數定義> -> <修飾詞閉包> <類型> <變量> ( <參數聲明> ) { <函數塊> }
<修飾詞閉包> -> <修飾詞> <修飾詞閉包> | $
<修飾詞> -> describe
<類型> -> type <取地址>
<取地址> -> <星號閉包>
<星號閉包> -> <星號> <星號閉包> | $
<星號> -> *
<變量> -> <標志符> <數組下標>
<標志符> -> id
<數組下標> -> [ <因式> ] | $
<因式> -> ( <表達式> ) | <變量> | <數字>
<數字> -> digit
<表達式> -> <因子> <項>
<因子> -> <因式> <因式遞歸>
<因式遞歸> -> * <因式> <因式遞歸> | / <因式> <因式遞歸> | $
<項> -> + <因子> <項> | - <因子> <項> | $
<參數聲明> -> <聲明> <聲明閉包> | $
<聲明> -> <修飾詞閉包> <類型> <變量> <賦初值>
<賦初值> -> = <右值> | $
<右值> -> <表達式> | { <多個數據> }
<多個數據> -> <數字> <數字閉包>
<數字閉包> -> , <數字> <數字閉包> | $
<聲明閉包> -> , <聲明> <聲明閉包> | $
<函數塊> -> <聲明語句閉包> <函數塊閉包>
<聲明語句閉包> -> <聲明語句> <聲明語句閉包> | $
<聲明語句> -> <聲明> ;
<函數塊閉包> -> <賦值函數> <函數塊閉包> | <for循環> <函數塊閉包> | <條件語句> <函數塊閉包> | <函數返回> <函數塊閉包> | $
<賦值函數> -> <變量> <賦值或函數調用>
<賦值或函數調用> -> = <右值> ; | ( <參數列表> ) ;
<參數列表> -> <參數> <參數閉包>
<參數閉包> -> , <參數> <參數閉包> | $
<參數> -> <標志符> | <數字> | <字符串>
<字符串> -> string
<for循環> -> for ( <賦值函數> <邏輯表達式> ; <後綴表達式> ) { <函數塊> }
<邏輯表達式> -> <表達式> <邏輯運算符> <表達式>
<邏輯運算符> -> < | > | == | !=
<後綴表達式> -> <變量> <後綴運算符>
<後綴運算符> -> ++ | --
<條件語句> -> if ( <邏輯表達式> ) { <函數塊> } <否則語句>
<否則語句> -> else { <函數塊> } | $
<函數返回> -> return <因式> ;
詞法分析頭文件：
LexAnalysis.h
[cpp]
//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
[cpp]
//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
[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)
{ www.2cto.com
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代碼：
[cpp] view plaincopy
//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;
}
}
}
flag = 0;
}
//到達最後一個字符，並且產生式右部都能推出空,將$並入First集中
else if(reduNull(p[k]) == 1 && k == length -1)
{
temp[0] = GRAMMAR_NULL;
temp[1] = -1;//其實是模擬字符串操作的手段
merge(connectFirst,temp,1);
}
else
{
break;
}
}
}
}
void followSet(int i)
{
int currentNon = nonTerMap[i].second;//當前的非終結符標號
int temp[2];
int result = 1;
temp[0] = currentNon;
temp[1] = -1;
merge(followRecu,temp,1);//將當前標號加入防遞歸集合中
//如果當前符號就是開始符號,把特殊符號加入其Follow集中
if(proc[1][1] == currentNon)
{
temp[0] = GRAMMAR_SPECIAL;//這個也是要處理的
temp[1] = -1;
merge(follow[i],temp,1);
}
for(int j = 1; j<=procNum; j++) //j代表第幾個產生式
{
//如果該非終結符在某個產生式的右部存在
if(inProcRight(currentNon,proc[j]) == 1)
{
int rightLength = 1;
int k = 0;//k為該非終結符在產生式右部的序號
int flag = 0;
int leftNum = proc[j][1];//產生式的左邊
int h = 0;
int kArray[Max_Length2];
memset(kArray,-1,sizeof(kArray));
for(h = 0; h < nonTerMap.size(); h++)
{
if(nonTerMap[h].second == leftNum)
{
break;
}
}
for(rightLength = 1;; rightLength++)
{
if(currentNon == proc[j][rightLength+2])
{
kArray[k++] = rightLength;
}
if(proc[j][rightLength+2] == -1)
{
break;
}
}
rightLength--;
for(int y=0;; y++)
{
if(kArray[y] == -1)
{
break;
}
//如果該非終結符在右部產生式的最後
if(kArray[y] == rightLength)
{
if(inFollowRecu(leftNum) == 1)
{
merge(follow[i],follow[h],1);
continue;
}
if(followVisit[h] == 0)
{
followSet(h);
followVisit[h] = 1;
}
merge(follow[i],follow[h],1);
}
//如果不在最後
else
{
int n = 0;
result = 1;//這是關鍵的，曾在這裡失誤過
for(n=kArray[y]+1; n<=rightLength; n++)
{
emptyRecu[0] = -1;
result *= reduNull(proc[j][n+2]);
}
if(result == 1)
{
if(inFollowRecu(leftNum) == 1)
{
merge(follow[i],follow[h],1);
continue;
}
if(followVisit[h] == 0)
{
followSet(h);
followVisit[h] = 1;
}
merge(follow[i],follow[h],1);
}
int temp2[Max_Length];
memset(temp2,-1,sizeof(temp2));
for(n=kArray[y]+1; n<=rightLength; n++)
{
temp2[n-kArray[y]-1] = proc[j][n+2];
}
temp2[rightLength-kArray[y]] = -1;
connectFirst[0] = -1;//應該重新初始化一下
connectFirstSet(temp2);
merge(follow[i],connectFirst,2);
}
}
}
}
followVisit[i] = 1;
}
//求所有非終結符的Follow集
void Follow()
{
for(int i=0; i<nonTerMap.size(); i++)
{
followRecu[0] = -1;
followSet(i);
}
printf("\n************************************Follow集******************************\n\n");
for(int i=0; i<nonTerMap.size(); i++)
{
printf("Follow[%s] = ",nonTerMap[i].first);
for(int j=0;; j++)
{
if(follow[i][j] == -1)
{
break;
}
printf("%s ",searchMapping(follow[i][j]));
}
printf("\n");
}
}
//求已經分解的產生式對應的Select集,注意Select集中不能含有空($),因而Type=2
void Select()
{
for(int i = 1; i<=procNum; i++) //j代表第幾個產生式
{
int leftNum = proc[i][1];//產生式的左邊
int h = 0;
int result = 1;
for(h = 0; h < nonTerMap.size(); h++)
{
if(nonTerMap[h].second == leftNum)
{
break;
}
}
int rightLength = 1;
for(rightLength = 1;; rightLength++)
{
if(proc[i][rightLength+2] == -1)
{
break;
}
}
rightLength--;
//如果右部推出式的長度為1並且是空,select[i-1] = follow[左邊]
if(rightLength == 1 && proc[i][rightLength + 2] == GRAMMAR_NULL)
{
merge(select[i-1],follow[h],2);
}
//如果右部不是空的時候,select[i-1] = first[右部全部]
//如果右部能夠推出空，select[i-1] = first[右部全部] ^ follow[左邊]
else
{
int temp2[Max_Length];
int n = 0;
memset(temp2,-1,sizeof(temp2));
for(n=1; n<=rightLength; n++)
{
temp2[n-1] = proc[i][n+2];
}
temp2[rightLength] = -1;
connectFirst[0] = -1;//應該重新初始化一下
connectFirstSet(temp2);
merge(select[i-1],connectFirst,2);
for(n=1; n<=rightLength; n++)
{
emptyRecu[0] = -1;
result *= reduNull(proc[i][n+2]);
}
//如果右部能推出空，將follow[左邊]並入select[i-1]中
if(result == 1)
{
merge(select[i-1],follow[h],2);
}
}
}
printf("\n************************************Select集******************************\n\n");
for(int i=0; i<procNum; i++)
{
printf("Select[%d] = ",i+1);
for(int j=0;; j++)
{
if(select[i][j] == -1)
{
break;
}
printf("%s ",searchMapping(select[i][j]));
}
printf("\n");
}
}
//輸出預測分析表
void MTable()
{
fstream outfile;
outfile.open("preciateTable.txt",ios::out);
for(int i=0; i<procNum; i++)
{
int m = 0;//非終結符的序號
for(int t=0; t<nonTerMap.size(); t++)
{
if(nonTerMap[t].second == proc[i+1][1])
{
m = t;
break;
}
}
for(int j=0;; j++)
{
if(select[i][j] == -1)
{
break;
}
for(int k=0; k<terMap.size(); k++)
{
if(terMap[k].second == select[i][j])
{
int n = 0;
for(n=1; n<=Max_Length2; n++)
{
M[m][k][n-1] = proc[i+1][n];
if(proc[i+1][n] == -1)
{
break;
}
}
break;
}
}
}
}
//printf("\n*********************************預測分析表******************************\n\n");
outfile<<endl<<"*********************************預測分析表******************************"<<endl;
for(int i=0; i<nonTerMap.size(); i++)
{
for(int j=0; j<terMap.size(); j++)
{
outfile<<"M["<<nonTerMap[i].first<<"]["<<terMap[j].first<<"] = ";
//printf("M[%s][%s] = ",nonTerMap[i].first,terMap[j].first);
for(int k=0;; k++)
{
if(M[i][j][k] == -1)
{
break;
}
outfile<<searchMapping(M[i][j][k]);
//printf("%s ",searchMapping(M[i][j][k]));
}
outfile<<endl;
//printf("\n");
}
outfile<<endl<<endl;
//printf("\n\n");
}
outfile.close();
}
void InitStack(SeqStack *S) /*初始化順序棧*/
{
S->top = -1;
}
int Push(SeqStack *S,int x) /*進棧*/
{
if(S->top ==Stack_Size-1)
return 0;
S->top++;
S->elem[S->top]=x;
return 1;
}
int Pop(SeqStack *S) /*出棧*/
{
if(S->top==-1)
return 0;
else
{
S->top--;
return 1;
}
}
int GetTop(SeqStack *S,int *x) /*取棧頂元素*/
{
if(S->top==-1)
return 0;
else
{
*x=S->elem[S->top];
return 1;
}
}
void ShowStack1(SeqStack *S) /*顯示棧的字符，先輸出棧底元素*/
{
int i;
for(i=S->top; i>=0; i--)
{
//printf("%s ",searchMapping(S->elem[i]));
resultfile<<searchMapping(S->elem[i])<<" ";
}
}
void ShowStack2(SeqStack *S) /*顯示棧的字符，先輸出棧頂元素*/
{
int i;
for(i=S->top; i>=0; i--)
{
//printf("%s ",searchMapping(S->elem[i]));
resultfile<<searchMapping(S->elem[i])<<" ";
}
}
//分析源程序
void Analysis()
{
//分析結果輸出
resultfile.open("preciateResult.txt",ios::out);
SeqStack s1,s2;
int c1,c2;
int i = 0;
int reserve[Stack_Size];//符號棧反向入棧
NormalNode * p = normalHead;
int s1Length = 0;
memset(reserve,-1,sizeof(reserve));
InitStack(&s1); /*初始化符號棧和輸入串*/
InitStack(&s2);
Push(&s1,GRAMMAR_SPECIAL);
Push(&s1,proc[1][1]);
Push(&s2,GRAMMAR_SPECIAL);
p = p->next;
while(p!=NULL)
{
if(p->type == AUTO || p->type == CONST || p->type == UNSIGNED || p->type == SIGNED
|| p->type ==STATIC || p->type == VOLATILE )
{
reserve[i++] = DESCRIBE;
//Push(&s2,DESCRIBE);
}
else if(p->type == INT_VAL)
{
reserve[i++] = DIGIT;
//Push(&s2,DIGIT);
}
else if(p->type == CHAR || p->type == DOUBLE || p->type == FLOAT || p->type == INT ||
p->type == LONG || p->type == SHORT || p->type == VOID)
{
reserve[i++] = TYPE;
//Push(&s2,TYPE);
}
else if(p->type == STRING_VAL)
{
reserve[i++] = STRING;
//Push(&s2,STRING);
}
else if(p->type == DOU_QUE || p->type == SIN_QUE)
{
}
else
{
reserve[i++] = p->type;
//Push(&s2,p->type);
}
p = p->next;
}
//求左邊棧的長度
for(s1Length = 0;; s1Length++)
{
if(reserve[s1Length] == -1)
{
break;
}
}
//反向入棧
for(i = s1Length; i>0; i--)
{
Push(&s2,reserve[i-1]);
}
for(i=0;; i++) /*分析*/
{
//getch();
int flag = 0;
int h1;
int h2;
//printf("第%d步：\n",i+1); /*輸出該步的相應信息*/
resultfile<<"第"<<i + 1<<"步"<<endl;
//printf("符號棧:");
resultfile<<"符號棧:";
ShowStack1(&s1);
//printf("\n");
resultfile<<endl;
//printf("輸入棧:");
resultfile<<"輸入棧:";
ShowStack2(&s2);
//printf("\n");
resultfile<<endl;
GetTop(&s1,&c1); /*取棧頂元素，記為c1，c2*/
GetTop(&s2,&c2);
if(c1 == GRAMMAR_SPECIAL && c2 == GRAMMAR_SPECIAL) /*當符號棧和輸入棧都剩余#時，分析成功*/
{
//printf("成功!\n");
resultfile<<"成功!"<<endl;
break;
}
if(c1 == GRAMMAR_SPECIAL && c2!= GRAMMAR_SPECIAL) /*當符號棧剩余#，而輸入串未結束時，分析失敗 */
{
//printf("失敗!\n");
resultfile<<"失敗!"<<endl;
break;
}
if(c1 == c2)/*符號棧的棧頂元素和輸入串的棧頂元素相同時，同時彈出*/
{
Pop(&s1);
Pop(&s2);
flag = 1;
}
else /*查預測分析表*/
{
//記錄下非終結符的位置
for(h1=0; h1<nonTerMap.size(); h1++)
{
if(nonTerMap[h1].second == c1)
{
break;
}
}
//記錄下終結符的位置
for(h2=0; h2<terMap.size(); h2++)
{
if(terMap[h2].second == c2)
{
break;
}
}
if(M[h1][h2][0] == -1)
{
//printf("Error\n");
resultfile<<"Error"<<endl;
break;//如果錯誤的話，直接終止分析
}
else
{
int length = 0;
//記錄下推導式的長度
for(length = 0;; length++)
{
if(M[h1][h2][length] == -1)
{
break;
}
}
Pop(&s1);
//如果不是空的話，反向入棧
if(M[h1][h2][2] != GRAMMAR_NULL)
{
for(int k = length-1; k>=2; k--)
{
Push(&s1,M[h1][h2][k]);
}
}
}
}
if(flag == 1)
{
//printf("匹配！\n");
resultfile<<"匹配!"<<endl;
}
else
{
resultfile<<"所用推出式：";
//printf("所用推出式：");
int w = 0;
//記錄下推導式的長度
for(w = 0;; w++)
{
if(M[h1][h2][w] == -1)
{
break;
}
//printf("%s ",searchMapping(M[h1][h2][w]));
resultfile<<searchMapping(M[h1][h2][w]);
}
//printf("\n\n");
resultfile<<endl<<endl;
}
}
resultfile.close();
}
主文件：
main.cpp
[cpp]
//main.cpp
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include "LexAnalysis.h"
#include "SynAnalysis.h"
int main()
{
//詞法分析部分
initKeyMapping();
initOperMapping();
initLimitMapping();
initNode();
scanner();
BraMappingError();
printNodeLink();
printErrorLink();
printIdentLink();
//語法分析部分
initGrammer();
First();
Follow();
Select();
MTable();
Analysis();
close();
return 0;
}
測試程序（被分析的C代碼）：
[plain]
int main()
{
int i = 7;
int j = 9;
int c[20] =
{2,10,10,19,3,4,5,5,34,6,54,52,34,55,68,10,90,78,56,20};
for (i=0;i<20;i++)
{
for(j=i+1;j<20;j--)
{
if(j == 19)
{
c[i] = j;
}
}
}
printf("Hello world");
return 0;
}
分析結果：
