算术表达式文法
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
给定一符合该文法的句子，如id+id*id#，运行预测分析程序，给出分析过程和每一步的分析结果
前言
- 代码遵从C++14标准，忙着别的事潦草的完成，还有许多需要优化的地方。
- 预测表里面的数：-1代表这有报错，其他数字拆开十位代表行，个位代表列；
- 行：给出文法的行，从0开始，如：E→TE’是第0行；因为只需要到了右半部分所以只保留了右半部分
- 列：为什么会出现列呢？因为很多文法右半部分是或的关系，如：T’ →*FT’ |/ FT’ |%FT’|ε 依次的行列是（3,0），（3,1），（3,2），（3,3）所以预测表里存储的是30,31,32,33
- 其他部分看代码的注释即可，有问题可以留言或加我QQ讨论
话不多说上代码
main.cpp
//
// Created by NorthS on 2022/5/5.
// QQ：1826496887
// url：www.vieuu.cn
//
#include "compilerwork.h"
//E`=X
//T`=Y
stack<char> reverAndPush(stack<char> s,string str);
int main(){
string s[5][10];
s[0][0]="TX";
s[1][0]="+TX";s[1][1]="-TX";s[1][2]="$";
s[2][0]="FY";
s[3][0]="*FY";s[3][1]="/FY";s[3][2]="%FY";s[3][3]="$";
s[4][0]="(E)";s[4][1]="i";s[4][2]="n";
int patable[5][10]={0,0,-1,-1,-1,-1,-1,0,-1,-1,
-1,-1,10,11,-1,-1,-1,-1,12,12,
20,20,-1,-1,-1,-1,-1,20,-1,-1,
-1,-1,33,33,30,31,32,-1,33,33,
41,42,-1,-1,-1,-1,-1,40,-1,-1
};
int follow[5][10]={0,0,0,0,0,0,0,0,1,1,
0,0,0,0,0,0,0,0,1,1,
0,0,1,1,0,0,0,0,1,1,
0,0,1,1,0,0,0,0,1,1,
0,0,1,1,1,1,1,0,1,1
};
string str="ii#";
int flag=0;
stack<char> gra;
gra.push('#');
gra.push('E');
while(1){
if(flag-1==str.size())break;
if(isNonterminator(gra.top())){//非终结符
int i= inNonterminatorindex(gra.top());
int j= inTerminatorindex(str[flag]);
if(patable[i][j]!=-1){//在预测表中有交点
int index=patable[i][j];
int m=index/10;
int n=index%10;
cout<<gra.top()<<"\t\t\t"<<str[flag]<<"\t\t\t"<<"展开非终结符"<<gra.top()<<"->"<<s[m][n]<<endl;
//在栈中弹出该非终结符
gra.pop();
//其右式逆序入栈
gra= reverAndPush(gra,s[m][n]);
}else{//在预测表中没交点
if(follow[i][j]==1){//当前单词属于该follow集
cout<<gra.top()<<"\t\t\t"<<str[flag]<<"\t\t\t"<<"\033[31;1m"<<"从栈中弹出该非终结符"<<gra.top()<<"\033[0m"<<endl;
//从栈中弹出该非终结符继续分析
gra.pop();
}else{//当前单词不属于该follow集
cout<<gra.top()<<"\t\t\t"<<str[flag]<<"\t\t\t"<<"\033[31;1m"<<"串指针下移（抛弃该单词不分析）"<<"\033[0m"<<endl;
//串指针下移（抛弃该单词不分析）
flag++;
if(flag==str.size()){//如果跳过的单词是最后一个单词报错并直接结束
break;
}
}
}
}
if(isTerminator(gra.top())){//终结符
if(gra.top()==str[flag]){//匹配成功
cout<<gra.top()<<"\t\t\t"<<str[flag]<<"\t\t\t"<<"匹配终结符"<<str[flag]<<endl;
gra.pop();//栈顶元素出栈
flag++;//串指针下移
}else{//匹配不成功
//第一种：从栈中弹出此终结符x（认为输入串中缺少单词a）√
// 第二种：将串指针下移一个位置（认为串中当前单词a多余）
cout<<gra.top()<<"\t\t\t"<<str[flag]<<"\t\t\t"<<"\033[31;1m"<<"从栈中弹出该终结符"<<"\033[0m"<<gra.top()<<endl;
gra.pop();
}
}
}
return 0;
}
handle.cpp
//
// Created by NorthS on 2022/5/5.
// QQ：1826496887
// url：www.vieuu.cn
//
#include "compilerwork.h"
char Nonterminator[10]={'E','X','T','Y','F'};
char Terminator[10]={'i','n','+','-','*','/','%','(',')','#'};
bool isNonterminator(char ch){
for(int i=0;i<strlen(Nonterminator);i++){
if(Nonterminator[i]==ch)return true;
}
return false;
}
bool isTerminator(char ch){
for(int i=0;i<strlen(Terminator);i++){
if(Terminator[i]==ch)return true;
}
return false;
}
int inNonterminatorindex(char ch){
for(int i=0;i<strlen(Nonterminator);i++){
if(Nonterminator[i]==ch)return i;
}
return -4;
}
int inTerminatorindex(char ch){
for(int i=0;i<strlen(Terminator);i++){
if(Terminator[i]==ch)return i;
}
return -4;
}
stack<char> reverAndPush(stack<char> s,string str){
if(str.size()==1&&str[0]=='$')return s;
for(int i=str.size()-1;i>=0;i--){
s.push(str[i]);
}
return s;
}
compilerwork.h
//
// Created by NorthS on 2022/5/5.
// QQ：1826496887
// url：www.vieuu.cn
//
#ifndef COMPILERW4_COMPILERWORK_H
#define COMPILERW4_COMPILERWORK_H
#include<bits/stdc++.h>
using namespace std;
/**
* 是否是非终结符
* @param ch
* @return
*/
bool isNonterminator(char ch);
/**
* 是否是终结符
* @param ch
* @return
*/
bool isTerminator(char ch);
/**
* 该非终结符在非终结符表中的位置
* @param ch
* @return
*/
int inNonterminatorindex(char ch);
/**
* 该终结符在终结符表中的位置
* @param ch
* @return
*/
int inTerminatorindex(char ch);
#endif //COMPILERW4_COMPILERWORK_H
