实验2.cpp

1 掌握手工生成词法分析器的方法

#include <iostream.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

 

#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<<"编制人：涂君兰，20042003，三班"<<endl;

       cout<<"请输入放有产生式的文件（如：pro.txt）:"<<endl;

       cin>>fileName;

       ProNode proNode[20];

       InitProNode(proNode,20);

       if(ReadPro(proNode,fileName)) {

              /*输出文法产生式*/

              cout<<"该文法产生式为："<<endl;

              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<<endl<<"分析表:"<<endl;

              SetSheet(proNode,unTinfo);

              cout<<"\t";

              for(int jj = 0 ; jj < NumofT ; jj++) 

                     cout<<Terminate[jj]<<"\t";

              cout<<endl;

              for(int mm = 0 ; mm < NumofUT ; mm++) {

                     cout<<UnTerminate[mm]<<"\t";

                     for(int mn = 0 ; mn < NumofT; mn++) {

                            PrintSheet(mm,mn);

                            cout<<"\t";

                     }

                     cout<<endl;

              }

              InputSym(); //输入字符串

              Scan();    //主控程序

              }

              else 

                     Error();

       }

       

       void InitProNode(ProNode proNode[],int proNum) {  

              //初始化函数，对每个非终结符的产生式结构进行初始化

              for(int i = 0 ; i < proNum ; 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 < unTInfoNum;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<<"溢出！"<<endl;

       }

       

       void Error() { //出错处理

              cout<<"分析出错！"<<endl;

       }

       

       void InitSheet(ProNode** sheet,int m,int n) {

              //初始化分析表函数,以便将无定义的表格定义为error

              

              for (int i = 0 ; i < m;i++)

                     for(int j = 0 ; j < n ; j++) {

                            sheet[i][j].leftSym = '\0';       //用0标记无定义的表格

                     }

                     

       }

       

       bool ReadPro(ProNode proNode[],char fileName[]) {

              FILE* pFile;

              if((pFile = fopen(fileName,"r")) == NULL) {

                     cout<<"打开文件出错！"<<endl;

                     return false;

              }

              char tmpChar;

              int tmpIndex = 0;

              fscanf(pFile,"%c",&tmpChar);