求一个语法分析器
发布网友
发布时间：2022-05-02 20:41
共3个回答
热心网友
时间：2022-06-27 00:27
#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<<"请输入放有产生式的文件（如：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);
int NumofUT = GetNumofUT(UnTerminate);
int NumofT = GetNumofT(Terminate);
UnTInfo unTinfo[20];
InitUnTInfo(unTinfo,20);
First(proNode,unTinfo);
Follow(proNode,unTinfo);
SetSelect(proNode,unTinfo);
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);
memset(unTInfo[i].follow,0,UnTInfo_Fol_Max);
}
}
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) {
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);
while(tmpChar != '#') { //求出产生式的个数
if(tmpChar == ';')
tmpIndex++;
fscanf(pFile,"%c",&tmpChar);
}
proNum = tmpIndex;
rewind(pFile);
for(int i = 0;i < proNum;i++) { //读出各产生式并置于已定义的数据结构ProNode中,
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 < proNum ; i++) {
cout<<proNode[i].leftSym<<proNode[i].midSym[0]<<proNode[i].midSym[1];
for(int j = 0; j < proNode[i].length;j++)
cout<<proNode[i].rightSym[j];
cout<<endl;
}
}
void SetUnTerminate(char UnTerminate[],ProNode proNode[],int proNum) {
for(int i = 0; i < proNum; i++) { //从第一个产生式开始
bool flag = true;
int tmpLength = strlen(UnTerminate);
for(int j = 0; j <= tmpLength; 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 < proNum; i++) { //从第一个产生式开始
for(int k = 0 ; k < proNode[i].length; k++) {
flag = true;
tmpLength = strlen(Terminate);
if(isupper(proNode[i].rightSym[k])) //若为非终结符号，则进入下一个字符
flag = false;
else if ( 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 <= tmpLength; j++) {
if(Terminate[j] == proNode[i].rightSym[k]) {
flag = false;
break;
}
}
if(flag) { //将终结符加入到终结符表
Terminate[tmpLength] = proNode[i].rightSym[k];
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 < len;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 < num; i++ ) {
if(Terminate[i] == c) {
flag = true;
break;
}
}
return flag;
}
int GetUTLoaction(char UnTerminate[],char c) { //获得非终结符在非终结符表中的位置
for(int i = 0 ; i < GetNumofUT(UnTerminate);i++)
if(UnTerminate[i] == c)
return i;
return -1;
}
int GetTLocaction(char Terminate[],char c) { //获得终结符在终结符表中的位置
for(int i = 0 ; i < GetNumofT(Terminate);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 <= tmpLength; 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 < otherLength; j++) {
bool flag = true;
int tmpLength = strlen(chArray);
for(int i = 0; i <= tmpLength; 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 < proNode[i].length; k++) {
if(!IsNull(proNode[i].rightSym[k])) {
break;
}
}
if(k == proNode[i].length)
AddChar(unTInfo[leftSymLoc].first,'^');
else {
for(int l = 0 ; l <k;l++) {
char rightChar = proNode[i].rightSym[l];
int rightSymLoc = GetUTLoaction(UnTerminate,rightChar);
int firstLen = strlen(unTInfo[rightSymLoc].first);
for (int m = 0 ; m < firstLen; m++) {
if(unTInfo[rightSymLoc].first[m] != '^')
AddChar(unTInfo[leftSymLoc].first,unTInfo[rightSymLoc].first[m]);
}
}
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 < numOfUnT ; i++) {
for(int j = 0 ;j < proNum; j++) { //从第一个产生式开始进行分析，逐个进行扫描
bool flag = false ;
for(int k = 0 ; k < proNode[j].length; 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])) {
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'){
if(IsTerminate(proNode[j].rightSym[k+1]))
AddChar(unTInfo[i].follow,proNode[j].rightSym[k+1]);
else { //如果β为非终结符，则将FIRST(β)-{ε}加入FOLLOW(A)中
int rightSymLoc = GetUTLoaction(UnTerminate,proNode[j].rightSym[k+1]);
int len = strlen(unTInfo[rightSymLoc].first);
for(int l = 0 ; l < len ; l++) {
if(unTInfo[rightSymLoc].first[l] != '^')
AddChar(unTInfo[i].follow,unTInfo[rightSymLoc].first[l]);
}
}
}
}
}
}
}
}
void SetSelect(ProNode proNode[],UnTInfo unTInfo[]) {//设置Select集合
bool isNull,isVT;
for(int i = 0 ;i < proNum; i++) { //扫描每一个产生式，求出Select集合
if(IsTerminate(proNode[i].rightSym[0])) {
AddChar(select[i],proNode[i].rightSym[0]);
}
else if(proNode[i].rightSym[0] == '^')
AddCharToChar(select[i],unTInfo[GetUTLoaction(UnTerminate,proNode[i].leftSym)].follow);
else {
isVT = false;
isNull = true;
for(int j = 0; j < proNode[i].length; j++) {
if(!IsTerminate(proNode[i].rightSym[j])) {
int rightSymLoc = GetUTLoaction(UnTerminate,proNode[i].rightSym[j]);
int firLen = strlen(unTInfo[rightSymLoc ].first);
for(int k = 0 ; k < firLen ; 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) {
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 < proNum ; i++) {
selLen = strlen(select[i]);
for(int j = 0 ; j < selLen ; j++) {
rowLoc = GetUTLoaction(UnTerminate,proNode[i].leftSym);
colLoc = GetTLocaction(Terminate,select[i][j]);
sheet[rowLoc][colLoc] = proNode[i];
}
}
}
void InputSym() { //输入字符串函数
InitQueue(Remain);
cout<<"请输入要分析的字符串(以'#'结束):"<<endl;
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;
SqStack SymStack; //符号栈
InitStack(SymStack);
cout<<"步骤"<<"\t"<<"符号栈"<<"\t\t"<<"读入符号"<<"\t"<<"剩余符号串"<<"\t"<<"使用产生式"<<endl;
cout<<step++<<"\t";
Push(SymStack,'#');
Push(SymStack,UnTerminate[0]); //'#' 、开始符号入栈
PrintSym(SymStack);
a = GetSym(Remain); //读入第一个符号
cout<<a<<"\t\t";
while(flag) {
PrintRemain(Remain);
x = Pop(SymStack); //从栈中弹出符号
leftLoc = GetUTLoaction(UnTerminate,x);
rightLoc = GetTLocaction(Terminate,a);
PrintSheet(leftLoc,rightLoc);
cout<<"\n";
if(IsTerminate(x)){
if(x == a) {
a = GetSym(Remain);
cout<<step++<<"\t";
PrintSym(SymStack);
cout<<a<<"\t\t";
}
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查分析表
leftLoc = GetUTLoaction(UnTerminate,x);
rightLoc = GetTLocaction(Terminate,a);
if(sheet[leftLoc][rightLoc].rightSym[0] != '^') {
int rightLen = strlen(sheet[leftLoc][rightLoc].rightSym);
for(int i = rightLen - 1; i >=0 ; i--) {
Push(SymStack,sheet[leftLoc][rightLoc].rightSym[i]);
}
cout<<step++<<"\t";
PrintSym(SymStack);
cout<<a<<"\t\t";
}
else {
cout<<step++<<"\t";
PrintSym(SymStack);
cout<<a<<"\t\t";
}
}
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 < s.top;i++)
cout<<*i;
cout<<"\t\t";
}
void PrintRemain(LinkQueue &q) { //显示剩余符号串
QueuePtr d ;
char tmp;
if(q.front->next != NULL) {
d =q.front->next;
do {
tmp = d->data;
cout<<tmp;
d = d->next;
}while(tmp != '#');
cout<<"\t\t";
}
else return ;
}
void PrintSheet(int row,int col) { //显示所使用产生式
if(row != -1 && col != -1) {
cout<<sheet[row][col].leftSym<<sheet[row][col].midSym[0]<<sheet[row][col].midSym[1];
for(int j = 0; j < sheet[row][col].length;j++)
cout<<sheet[row][col].rightSym[j];
}
else
cout<<" ";
}
void Success() {//分析成功
cout<<"Successful!"<<endl;
}
热心网友
时间：2022-06-27 00:28
热心网友
时间：2022-06-27 00:28
