本文主要是介绍编译原理实验4——LL（1）文法分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本来是打算再写一个select集生成器的，但是时间有限再加上懒后来还是放弃了= =。
这个代码也是需要先新建一个文本文件sy4.in
文本文件中第一行有一个整数x，代表有x个产生式
接下来x行每行有三个字符串，分别代表产生式左边，右边还有对应的select集
最后一行还有一个字母s，代表起始字符
在读入了数据之后，若文法是LL（1)文法，则会输出"The Data is ok!"
否则就是输出“Wrong Data”，并且终止程序。
若文法OK，则直接输入待分析的句子即可
若分析句子符合文法，则会输出accepted，并且询问是否输出对应的最左推导。
否则输出Wrong！
输入y以'^'开头的字符串则程序终止。
代码如下：
#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
const int M = 55;
FILE *f1;
struct CharHash{/*{{{*/map<char,int> mp;char ch[N];bool End[N];int cnt;void init(){memset(End,1,sizeof(End));mp.clear();cnt = 0;ch[cnt] = '#';mp['#'] = cnt ++;}int Insert(char c){if(mp.find(c) == mp.end()){ch[cnt] = c;mp[c] = cnt ++;}return mp[c];}char Find(int c){return ch[c];}void SetnEnd(int c){End[c] = 0;}
};/*}}}*/
CharHash ChHash;
struct Unknowname{/*{{{*/struct Derivation{/*{{{*/int s,t[10],tcnt;int select[M];void add(){memset(select,0,sizeof(select));char tmp[10];fscanf(f1,"%s",tmp);s = ChHash.Insert(tmp[0]);fscanf(f1,"%s",tmp);tcnt = strlen(tmp);for(int i = 0 ; tmp[i] != '\0' ; i ++)t[i] = ChHash.Insert(tmp[i]);fscanf(f1,"%s",tmp);for(int i = 0 ; tmp[i] != '\0' ; i ++)select[ ChHash.Insert(tmp[i]) ] = 1;ChHash.SetnEnd(s);}bool operator < (const Derivation &a)const{return s < a.s;}};/*}}}*/Derivation Der[N];int n;int table[M][M];int queue[N],qcnt;char Schar;void init(){memset(table,-1,sizeof(table));};void read(){fscanf(f1,"%d",&n);for(int i = 0 ; i < n ; i ++)Der[i].add();sort(Der,Der + n);fscanf(f1," %c",&Schar);}bool check(){bool in[M];bool ok = 1;memset(in,0,sizeof(in));for(int i = 0 ; i < n && ok ; i ++){if(i && Der[i].s != Der[i - 1].s)memset(in,0,sizeof(in));for(int j = 0 ; j < ChHash.cnt ; j ++){if(in[j] && Der[i].select[j]) ok = 0;in[j] |= Der[i].select[j];}}puts(ok ? "The Data is ok!" : "Wrong Data!");return ok;}void GetTable(){int cc = ChHash.cnt;for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < cc ; j ++){if(Der[i].select[j] == 0) continue;int u = Der[i].s;int v = j;table[u][v] = i;}}}bool Analysis(char s[]){char stack[N],top = 0;stack[top ++] = ChHash.Insert('$');stack[top ++] = ChHash.Insert(Schar);int tail = 0,len = strlen(s);qcnt = 0;for(int i = 0 ; s[i] != '\0' ; i ++)s[i] = ChHash.Insert(s[i]);while(top){int u = stack[top - 1];int v = s[tail];if(u == 0){top --;continue;}if(ChHash.End[u]){if(v != u){printf("Wrong!1\n");return 0;}else{top --;tail ++;}}else{int id = table[u][v];if(id == -1){printf("Wrong!2\n");return 0;}top --;for(int i = Der[id].tcnt - 1 ; i >= 0 ; i --)stack[top ++] = Der[id].t[i];queue[qcnt ++] = id;}}if(top == 0 && tail == len){printf("Accepted!\n");return 1;}else{printf("Wrong3!\n");return 0;}}void output(){for(int i = 0 ; i < qcnt ; i ++){int id = queue[i];printf("%c->",ChHash.Find(Der[id].s));for(int j = 0 ; j < Der[id].tcnt ; j ++)printf("%c",ChHash.Find(Der[id].t[j]));printf("\n");}}
};/*}}}*/
Unknowname Table;
int main(){//freopen("out","w",stdout);f1 = fopen("sy4.in","r");ChHash.init();Table.init();Table.read();if(Table.check() == 0) return 0;Table.GetTable();char tmp[100];printf("please input the string: ");while(~scanf("%s",tmp)){if(tmp[0] == '^') break;int len = strlen(tmp);tmp[len] = '$';tmp[len + 1] = '\0';bool ok = Table.Analysis(tmp);if(ok){int t;printf("do you want to know the derivation?\n(0 is no 1 is yes)\n");scanf("%d",&t);if(t) Table.output();}printf("please input the string: (^ is over)");}fclose(f1);return 0;
}
/*
i+(i*i+i)
i(i)
((i))
i+i+
*/样例sy4.in如下：
8
E TA (i
A +TA +
A # )$
T FB (i
B *FB *
B # )+$
F (E) (
F i i
E
这篇关于编译原理实验4——LL（1）文法分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
