预测分析法
一、功能描述:
构造文法的语法分析程序,要求采用预测分析法对输入的字符串进行语法分析。
二、程序结构描述:
全局变量:
map<char,int> key; —— 终结符、非终结符所代表的值
string sheet[10][10]; —— 预测分析表
string s; —— 输入的字符串
int i; —— 当前读到的位置
程序分成如下几个函数:
void init() —— 初始化函数:构造预测分析表。
void printSuccess(); —— 打印正确信息
void printFail() ; —— 打印失败信息
bool getNext(); —— 获得串中的下一个字符,如果已结束则返回false
bool check() —— 分析过程,不匹配则返回false
main —— 主函数
处理输入串的部分,若输入为“.”则退出循环,否则对指定文件进行语法分析。
程序总体执行流程详见代码。
三、实验总结:
完成总使用四课时:
其中纸上时间一课时,编程两课时,调试一课时。
收获:
了解到一些语法分析的知识。
四、程式源码:
-
#include<iostream>
-
#include<string>
-
#include<stack>
-
#include<map>
-
using namespace std;
-
-
map<char,int> key;
-
string sheet[10][10];
-
string s;
-
int i;
-
-
void init(){
-
// 设定终结符Key值
-
key['i'] = 0;
-
key['+'] = 1;
-
key['*'] = 2;
-
key['('] = 3;
-
key[')'] = 4;
-
key['#'] = 5;
-
-
// 设定非终结符Key值
-
key['E'] = 10;
-
key['S'] = 11;
-
key['T'] = 12;
-
key['N'] = 13;
-
key['F'] = 14;
-
-
// 初始化预测分析表
-
for(int i=0; i<5; i++){
-
for(int j=0; j<6; j++){
-
sheet[i][j] = "";
-
}
-
}
-
-
// 构造预测分析表
-
sheet[0][0] = "TS"; // E->TS
-
sheet[0][3] = "TS"; // E->TS
-
sheet[1][1] = "+TS"; // S->+TS
-
sheet[1][4] = "0"; // S->ε
-
sheet[1][5] = "0"; // S->ε
-
sheet[2][0] = "FN"; // T->FN
-
sheet[2][3] = "FN"; // T->FN
-
sheet[3][1] = "0"; // N->ε
-
sheet[3][2] = "*FN"; // N->*FN
-
sheet[3][4] = "0"; // N->ε
-
sheet[3][5] = "0"; // N->ε
-
sheet[4][0] = "i"; // F->i
-
sheet[4][3] = "(E)"; // F->(E)
-
}
-
-
void printSuccess(){
-
cout<<"Success!"<<endl;
-
}
-
-
void printFail(){
-
cout<<"Fail!"<<endl;
-
}
-
-
bool getNext(){
-
if(i==s.size()-1)return false;
-
i++;
-
return true;
-
}
-
-
bool check(){
-
stack<char> st;
-
st.push('#'); // 初始时压入'#'
-
st.push('E'); // 起始符压栈
-
while(getNext()){
-
char in = s[i];
-
while(true){
-
char top = st.top();
-
string v;
-
if(in==top){ // 栈顶与输入字符相等则弹出
-
bool flag = getNext();
-
in = s[i];
-
st.pop();
-
if(flag)continue; // 如果未读完 则继续分析
-
else break; // 否则退出
-
}
-
if((v = sheet[key[top]-10][key[in]])!=""){ // 预测分析表中有值
-
st.pop();
-
if(v=="0")continue;
-
for(int j=v.size()-1; j>=0; j--){ // 压栈
-
st.push(v[j]);
-
}
-
}else{
-
st.push(in);
-
break;
-
}
-
}
-
}
-
return st.empty(); // 如果栈不为空 说明表达式不符合文法
-
}
-
-
int main(){
-
init();
-
-
cout<<"input string(end of '#', if u want to exit, just press '.'):"<<endl;
-
-
while(cin>>s){
-
if(s==".")break;
-
i = -1;
-
-
if(check()){
-
printSuccess();
-
}else{
-
printFail();
-
}
-
-
cout<<endl;
-
-
}
-
return 0;
-
}