语法分析器实验报告(可运行)
计算机科学与工程系
xx 大学
XX系
实验报告
XX 至 XX 学年 第 X 学期
计算机科学与工程系
源程序：
#include
#include
#include
#include
#include
#define Pro_MidSym_Max 2
#define Pro_RightSym_Max 10
#define UnTInfo_Fir_Max 10
#define UnTInfo_Fol_Max 10
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct ProNode {//产生式结构
char leftSym; //产生式左边的符号
char midSym[Pro_MidSym_Max]; //产生式推导符号
char rightSym[Pro_RightSym_Max]; //产生式右边的符号，不超过十个
int length; //产生式长度
}ProNode;
typedef struct UnTInfo {//每个非终结符的信息结构，包括first和follow集合
char first[UnTInfo_Fir_Max];
char follow[UnTInfo_Fol_Max];
}UnTInfo;
typedef struct { //构造顺序栈,存储符号
char *base;
char *top;
int stacksize;
}SqStack;
typedef struct QNode{ //构造单链队列，存储输入符号串
char data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
int proNum; //产生式个数
char UnTerminate[15]; //非终结符表
char Terminate[15]; //终结符表
char ProNull[20]; //记录能产生空字符的非终结符
ProNode sheet[15][15]; //分析表
char select[15][15]; //select集合，以便于构造分析表
LinkQueue Remain; //剩余符号串
void InitUnTInfo(UnTInfo unTInfo[],int unTInfoNum);
//初始化函数，对每个非终结符的信息结构进行初始化
void InitProNode(ProNode proNode[],int proNum);
//初始化函数，对每个非终结符的产生式结构进行初始化
void InitStack(SqStack &s); //初始化栈
void InitQueue(LinkQueue &q); //初始化队列
void EnQueue(LinkQueue &q,char c); //在队尾插入新的元素
void Exit(); //栈溢出处理函数
void Error();//出错处理
void Push(SqStack &s, char c); //入栈
char Pop(SqStack &s); //出栈
void InitSheet(ProNode** sheet,int m,int n) ; //初始化分析表函数
bool ReadPro(ProNode proNode[],char fileName[]);//从文件读取产生式函数
void PrintPro(ProNode proNode[],int proNum); //显示产生式
void SetUnTerminate(char UnTerminate[],ProNode proNode[],int proNum); //设置非终结符表
void SetTerminate(char UnTerminate[],ProNode proNode[],int proNum); //设置终结符表
int GetNumofUT(char UnTerminate[]); //获得非终结符个数
int GetNumofT(char Terminate[]); //获得终结符个数
int GetUTLoaction(char UnTerminate[],char c); //获得非终结符在非终结符表中的位置
int GetTLocaction(char UnTerminate[],char c); //获得终结符在终结符表中的位置
void First(ProNode proNode[],UnTInfo unTInfo[]); //计算各非终结符的First集
void Follow(ProNode proNode[],UnTInfo unTInfo[]); //计算各非终结符的Follow集
void AddChar(char chArray[],char c); //将非终结符的所有first值加入First集
void AddCharToChar(char chArray[],char otherArray[]); //将非终结符的所有first集加入First集
void AddFollow(char follow[],char c); //将非终结符的所有follow值加入Follow集
bool IsNull(char c); //非终结符能否产生空字符
bool IsTerminate(char c); //判断是否为终结符号
void SetSheet(ProNode proNode[],UnTInfo unTInfo[]); //设置分析表
void SetSelect(ProNode proNode[],UnTInfo unTInfo[]);//设置Select集合
void InputSym(); //输入字符串函数
void Scan(); //分析扫描的主控程序
char GetSym(LinkQueue &q) ; //获取下一字符
void PrintSym(SqStack &s); //显示符号栈符号
void PrintRemain(LinkQueue &q); //显示剩余符号串
void PrintSheet(int row,int col); //显示所使用产生式
void Success(); //分析成功
void main() {
char fileName[10];
cout
cout
cin>>fileName;
ProNode proNode[20];
InitProNode(proNode,20);
if(ReadPro(proNode,fileName)) {
/*输出文法产生式*/
cout
PrintPro(proNode,proNum);
/*设置非终结符表和终结符表*/
SetUnTerminate(UnTerminate,proNode,proNum);
SetTerminate(Terminate,proNode,proNum);
/* 输出First集*/
int NumofUT = GetNumofUT(UnTerminate);
int NumofT = GetNumofT(Terminate);
UnTInfo unTinfo[20];
InitUnTInfo(unTinfo,20); /* 输出First集*/
First(proNode,unTinfo);
/* 输出Follow集*/
Follow(proNode,unTinfo);
/*设置select*/
SetSelect(proNode,unTinfo);
/*输出sheet*/
cout
SetSheet(proNode,unTinfo);
cout
for(int jj = 0 ; jj
cout
cout
for(int mm = 0 ; mm
cout
for(int mn = 0 ; mn
PrintSheet(mm,mn);
cout
}
cout
}
InputSym(); //输入字符串
Scan(); //主控程序
}
else
Error();
}
void InitProNode(ProNode proNode[],int proNum) {
//初始化函数，对每个非终结符的产生式结构进行初始化
for(int i = 0 ; i
proNode[i].leftSym = '\0';
memset(proNode[i].midSym,0,Pro_MidSym_Max);
memset(proNode[i].rightSym,0,Pro_RightSym_Max);
proNode[i].length = 0;
}
}
void InitUnTInfo(UnTInfo unTInfo[],int unTInfoNum) {
//初始化函数，对每个非终结符的信息结构进行初始化
for(int i = 0 ; i
int firLength = strlen(unTInfo[i].first);
int folLength = strlen(unTInfo[i].follow);
memset(unTInfo[i].first,0,UnTInfo_Fir_Max);
//将非终结符号的Frist集合初始化为空串
memset(unTInfo[i].follow,0,UnTInfo_Fol_Max);
//将非终结符号的follow集合初始化为空串
}
}
void InitStack(SqStack &s) {//初始化栈
s.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!s.base) Exit();
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
}
void Push(SqStack &s, char c) { //入栈
if(s.top - s.base >= s.stacksize) { //栈满，追加存储空间
s.base = (char *)realloc(s.base,(s.stacksize + STACKINCREMENT) * sizeof(char));
if(!s.base) Exit(); //存储分配失败
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*(s.top) = c;
s.top = s.top + 1;
}
char Pop(SqStack &s) { //出栈
if(s.top == s.base ) return NULL;
s.top = s.top - 1;
char tmpChar = *(s.top);
return tmpChar;
}
void InitQueue(LinkQueue &q) { //初始化队列
q.front = q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!q.front) Exit(); //存储分配失败
q.front->next = NULL;
}
void EnQueue(LinkQueue &q,char c) { //在队尾插入新的元素
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if(!p) Exit(); //存储分配失败
p->data = c;
p->next = NULL;
q.rear->next = p;
q.rear = p;
}
void Exit() { //溢出处理
cout
}
void Error() { //出错处理
cout
}
void InitSheet(ProNode** sheet,int m,int n) {
//初始化分析表函数,以便将无定义的表格定义为error
for (int i = 0 ; i
for(int j = 0 ; j
sheet[i][j].leftSym = '\0'; //用0标记无定义的表格
}
}
bool ReadPro(ProNode proNode[],char fileName[]) {
FILE* pFile;
if((pFile = fopen(fileName,"r")) == NULL) {
cout
return false;
}
char tmpChar;
int tmpIndex = 0;
fscanf(pFile,"%c",&tmpChar);
while(tmpChar != '#') { //求出产生式的个数
if(tmpChar == ';')
tmpIndex++;
fscanf(pFile,"%c",&tmpChar);
}
proNum = tmpIndex;
rewind(pFile);
for(int i = 0;i
//同时可将非终结符置于非终结符号表
fscanf(pFile,"%c %c %c",&proNode[i].leftSym,&proNode[i].midSym[0],\
&proNode[i].midSym[1]);
proNode[i].midSym[2] = '\0';
fscanf(pFile,"%c",&tmpChar);
int j = 0;
while(tmpChar != ';') {
proNode[i].rightSym[j] = tmpChar;
fscanf(pFile,"%c",&tmpChar);
j++;
}
proNode[i].rightSym[j] = '\0';
proNode[i].length = j;
}
return true;
}
void PrintPro(ProNode proNode[],int proNum) { //显示产生式
for(int i = 0 ; i
cout
for(int j = 0; j
cout
cout
}
}
void SetUnTerminate(char UnTerminate[],ProNode proNode[],int proNum) {
//获得非终结符，存储于非终结符表
for(int i = 0; i
bool flag = true;
int tmpLength = strlen(UnTerminate);
for(int j = 0; j
if(UnTerminate[j] == proNode[i].leftSym) { //若已存在，则进入下个产生式
flag = false;
break;
}
}
if(flag) {
UnTerminate[tmpLength] = proNode[i].leftSym; 符加入到非终结符表
UnTerminate[tmpLength + 1] = '\0';
}
}
}
void SetTerminate(char Terminate[],ProNode proNode[],int proNum) {
//获得终结符，存储于终结符表
int tmpLength;
bool flag ;
for(int i = 0; i
for(int k = 0 ; k
flag = true;
//将非终结
tmpLength = strlen(Terminate);
if(isupper(proNode[i].rightSym[k])) //若为非终结符号，则进入下一个字符
flag = false;
else if ( proNode[i].rightSym[k] == '^') {
//记录能产生空字符的产生式
{ 结符加入到终结符表
proNode[i].rightSym[k];
int tmpLength = strlen(ProNull); flag = false; ProNull[tmpLength] = proNode[i].leftSym; ProNull[tmpLength + 1] = '\0'; } else if(flag) for(int j = 0; j
//将终 Terminate[tmpLength] = Terminate[tmpLength + 1] = '\0';
}
}
}
}
int GetNumofUT(char UnTerminate[]) { //获得非终结符个数
return strlen(UnTerminate);
}
int GetNumofT(char Terminate[]) { //获得终结符个数
return strlen(Terminate);
}
bool IsNull(char c) { //非终结符能否产生空字符
int len = strlen(ProNull);
for(int i = 0;i
if(ProNull[i] == c)
return true;
}
return false;
}
bool IsTerminate(char c) { //判断是否为终结符号
int num = GetNumofT(Terminate);
bool flag = false;
for(int i = 0 ; i
if(Terminate[i] == c) {
flag = true;
break;
}
}
return flag;
}
int GetUTLoaction(char UnTerminate[],char c) { //获得非终结符在非终结符表中的位置
for(int i = 0 ; i
if(UnTerminate[i] == c)
return i;
return -1;
}
int GetTLocaction(char Terminate[],char c) { //获得终结符在终结符表中的位置
for(int i = 0 ; i
if(Terminate[i] == c)
return i;
return -1;
}
void AddChar(char chArray[],char c) { //将非终结符的所有first值加入First集
bool flag = true;
int tmpLength = strlen(chArray);
for(int i = 0; i
if(chArray[i] == c) { //若已存在，则不加入
flag = false;
break;
}
}
if(flag) {
chArray[tmpLength] = c; //将first值加入First集
chArray[tmpLength + 1] = '\0';
}
}
void AddCharToChar(char chArray[],char otherArray[]) {
int otherLength = strlen(otherArray);
for(int j = 0 ; j
bool flag = true;
int tmpLength = strlen(chArray);
for(int i = 0; i
if(chArray[i] == otherArray[j]) { //若已存在，则不加入
flag = false;
break;
}
}
if(flag) {
chArray[tmpLength] = otherArray[j]; //将first值加入First集
chArray[tmpLength + 1] = '\0';
}
}
}
void First(ProNode proNode[],UnTInfo unTInfo[]) { //求出First集合
for(int i = proNum -1 ; i >= 0 ; i--) { //从最后一个产生式开始进行分析
char leftSym = proNode[i].leftSym;
char c = proNode[i].rightSym[0];
int leftSymLoc = GetUTLoaction(UnTerminate,leftSym);
if(IsNull(leftSym)) //如果产生式推出空字符，则把空字符加入First集合
AddChar(unTInfo[leftSymLoc].first,c);
else {
if(IsTerminate(c)) { //如果产生式右边第一个符号为终结符号
AddChar(unTInfo[leftSymLoc].first,c); //将符号加入First集合
}
else {
for(int k = 0; k
if(!IsNull(proNode[i].rightSym[k])) {
//判断能否产生空字符，直到找到不为空的停止
break;
}
}
if(k == proNode[i].length)
//若对于产生式右边的一切非终结符,均可推出ε，则将ε加进FIRST集
AddChar(unTInfo[leftSymLoc].first,'^');
else {
for(int l = 0 ; l
/*将产生式右边能推出空字符的非
终结符的Frist集中不含ε的终结符加入到该非终结符的Fisrt集*/
char rightChar = proNode[i].rightSym[l];
int rightSymLoc = GetUTLoaction(UnTerminate,rightChar);
int firstLen = strlen(unTInfo[rightSymLoc].first);
for (int m = 0 ; m
if(unTInfo[rightSymLoc].first[m] != '^')
AddChar(unTInfo[leftSymLoc].first,unTInfo[rightSymLoc].first[m]);
}
}
/*将产生式右边不能推出空字符的非终结符的Frist集加入到该非终结符的Fisrt集*/
int rightSymLoc = GetUTLoaction(UnTerminate,proNode[i].rightSym[k]);
AddCharToChar(unTInfo[leftSymLoc].first,unTInfo[rightSymLoc].first);
}
}
}
}
}
void Follow(ProNode proNode[],UnTInfo unTInfo[]) { //计算各非终结符的Follow集
AddChar(unTInfo[0].follow,'#'); //开始符号，则把“#”加入FOLLOW中；
int numOfUnT = GetNumofUT(UnTerminate);
for(int i = 0; i
for(int j = 0 ;j
bool flag = false ;
for(int k = 0 ; k
flag = false;
if(UnTerminate[i] == proNode[j].rightSym[k]) //判断非终结符是否在产生式右边
flag = true;
if(flag) {
if((k == proNode[j].length - 1) || IsNull(proNode[j].rightSym[k+1])) {
//若B→αA 或B→αAβ，且β=>ε,则把FOLLOW(B)加入FOLLOW(A) 中
if(proNode[j].leftSym != UnTerminate[i]) {
int leftSymLoc = GetUTLoaction(UnTerminate,proNode[j].leftSym);
AddCharToChar(unTInfo[i].follow,unTInfo[leftSymLoc].follow);
}
}
if(proNode[j].rightSym[k+1] != '\0'){
//若B→αAβ (β≠>ε)，则把FIRST(β)-{ε}加入FOLLOW(A)中
if(IsTerminate(proNode[j].rightSym[k+1]))
直接加入FOLLOW(A)中
AddChar(unTInfo[i].follow,proNode[j].rightSym[k+1]);
else { 则将FIRST(β)-{ε}加入FOLLOW(A)中
GetUTLoaction(UnTerminate,proNode[j].rightSym[k+1]);
strlen(unTInfo[rightSymLoc].first);
if(unTInfo[rightSymLoc].first[l] != '^')
AddChar(unTInfo[i].follow,unTInfo[rightSymLoc].first[l]);
}
}
}
}
//如果β为终结符，则将其 //如果β为非终结符，int rightSymLoc = int len = for(int l = 0 ; l
}
}
}
void SetSelect(ProNode proNode[],UnTInfo unTInfo[]) {//设置Select集合
bool isNull,isVT;
for(int i = 0 ;i
if(IsTerminate(proNode[i].rightSym[0])) {
//如果产生式的右边第一字符为终结符，则将其加入select集
AddChar(select[i],proNode[i].rightSym[0]);
}
else if(proNode[i].rightSym[0] == '^')
//如果产生式的右边字符为ε,则应将左边字符的follow集加入select集
AddCharToChar(select[i],unTInfo[GetUTLoaction(UnTerminate,proNode[i].leftSym)].follow);
else {
isVT = false;
isNull = true;
for(int j = 0; j
//产生式右边的第一个字符为非终结符，则逐个分析
if(!IsTerminate(proNode[i].rightSym[j])) {
//若α=X1X2 „ Xnα′，其中Xi∈VN , 1≤i≤n；
//若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α),
//FIRST(α)则应加入select集；以此类推
int rightSymLoc = GetUTLoaction(UnTerminate,proNode[i].rightSym[j]);
int firLen = strlen(unTInfo[rightSymLoc ].first);
for(int k = 0 ; k
if(unTInfo[rightSymLoc ].first[k] != '^')
AddChar(select[i],unTInfo[rightSymLoc].first[k]);
if(!IsNull(proNode[i].rightSym[j])) {
//如果该非终结符不能推出空字符则应停止循环
isNull = false;
break;
}
}
else { //遇到了终结符号，此时也应终止循环
isVT = true;
break;
}
}
if(isVT&&isNull) //处理像E->ABaβ的产生式的情况
AddChar(select[i],proNode[i].rightSym[j]);
if(j == proNode[i].length) {
//若α=X1X2 „ Xnα′，其中Xi∈VN , 1≤i≤n；
//若对于一切1≤i≤n,ε∈FIRST(Xi)，则将follow(α)加入select集合
int leftSymLoc = GetUTLoaction(UnTerminate,proNode[i].leftSym);
AddCharToChar(select[i],unTInfo[leftSymLoc].follow);
}
}
}
}
void SetSheet(ProNode proNode[],UnTInfo unTInfo[]) { //构造分析表
int selLen ;
int rowLoc,colLoc;
for(int i = 0; i
selLen = strlen(select[i]);
for(int j = 0 ; j
rowLoc = GetUTLoaction(UnTerminate,proNode[i].leftSym);
colLoc = GetTLocaction(Terminate,select[i][j]);
sheet[rowLoc][colLoc] = proNode[i];
}
}
}
void InputSym() { //输入字符串函数
InitQueue(Remain);
cout
char tmpChar;
int i = 0 ;
cin>>tmpChar;
while(tmpChar != '#') {
EnQueue(Remain,tmpChar);
cin>>tmpChar;
}
EnQueue(Remain,tmpChar);
}
void Scan() { //分析扫描的主控程序
int i = 0 ;
int step = 1;
int rightLoc;
int leftLoc;
char a;
char x;
bool flag = true;
//SymStack[i] = '#';
//SymStack[++i] = UnTerminate[0]; //'#' 、开始符号入栈
//SqStack s;
SqStack SymStack; //符号栈
InitStack(SymStack);
cout
cout
Push(SymStack,'#');
Push(SymStack,UnTerminate[0]); //'#' 、开始符号入栈
PrintSym(SymStack);
a = GetSym(Remain); //读入第一个符号
cout
while(flag) {
PrintRemain(Remain);
x = Pop(SymStack); //从栈中弹出符号
leftLoc = GetUTLoaction(UnTerminate,x);
rightLoc = GetTLocaction(Terminate,a);
PrintSheet(leftLoc,rightLoc);
cout
if(IsTerminate(x)){
if(x == a) {
a = GetSym(Remain);
cout
PrintSym(SymStack);
cout
}
else {
flag = false;
Error();
}
}
else if(x == '#') {
if(x == a) { //分析成功
Success();
flag = 0 ;
}
else {
flag = 0 ;
Error();
}
}
else
if(sheet[GetUTLoaction(UnTerminate,x)][GetTLocaction(Terminate,a)].leftSym \
!= '\0' ) { // X ∈Vn查分析表
//Pop(SymStack);
leftLoc = GetUTLoaction(UnTerminate,x);
rightLoc = GetTLocaction(Terminate,a);
if(sheet[leftLoc][rightLoc].rightSym[0] != '^') {
//若X1X2„Xn != ε，则反顺序进栈
int rightLen
strlen(sheet[leftLoc][rightLoc].rightSym);
for(int i = rightLen - 1; i >=0 ; i--) {
Push(SymStack,sheet[leftLoc][rightLoc].rightSym[i]);
}
cout
=
PrintSym(SymStack);
cout
}
else {
cout
PrintSym(SymStack);
cout
}
}
else {
flag = 0;
Error();
}
}
}
char GetSym(LinkQueue &q) {
if(q.front == q.rear) return NULL;
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
p = q.front->next;
char tmp = p->data;
q.front->next = p->next;
if(q.rear == p) q.rear = q.front;
free(p);
return tmp;
}
void PrintSym(SqStack &s) { //显示符号栈 符号
char* i ;
for( i = s.base ; i
cout
cout
}
void PrintRemain(LinkQueue &q) { //显示剩余符号串
QueuePtr d ;
char tmp;
if(q.front->next != NULL) {
d =q.front->next;
do {
tmp = d->data;
cout
d = d->next;
}while(tmp != '#');
cout
}
else return ;
}
void PrintSheet(int row,int col) { //显示所使用产生式
if(row != -1 && col != -1) {
cout
for(int j = 0; j
cout
}
else
cout
}
void Success() {//分析成功
cout
}
实验结果：