实验内容针对SysY语言中简单算术表达式文法G[E]:E→TE’E’→ATE’|εT→FT’T’→MFT’
εF→(E)
iA → +
-M → *
/求解相应的FIRST、FOLLOW集，构造预测分析表，并编写LL(1)语法分析程序，并给出测试句子的分析过程。输入：是词法分析输出的二元组序列，即任意简单算术表达式经过专题1程序输出后得到的结果。【上述文法中i即对应词法分析的标识符， ±*/分别对应词法分析得到的运算符】
处理：基于分析表进行 LL(1)语法分析，判断其是否符合文法。
输出：串是否合法。注：有关FIRST/FOLLOW集的有关定义请看编译原理 LL(1)文法判别方法
设计方法给出语法分析表1.使用两个map储存该表，第一个表为Map<Character,Map>，储存左侧非终结符号和右侧输入符号对应的map,第二个map为Map<Character,String>，储存输入符号和应该转换为的字符串。2.利用栈Deque来储存需要转换的符号，从E开始。每次开始遍历时先弹出栈顶符号，通过map的搜索找到对应的字符串，将字符串压入栈，如果不存在则跳过。并设置错误标记，如果有跳过则最后输出“不符合文法”。如果栈顶的符号和当前字符串符号相同，则输出匹配，遇到空值ε时，字符串往后一位，不把ε压入栈。3.若栈或者字符串序列有一者率先到达底端，则直接报错。函数定义public static void Init()//初始化分析表public static String txt2String(File file)//读入txtpublic static void analyze(String s)//分析程序程序
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
public class LL1_2 {
//LL(1)语法分析器的设计与实现
static Deque<Character> deque = new LinkedList<>();
static Map<Character,Map<Character,String>> mapcol =
new HashMap<>();//找列
static String str="";
public static void Init(){
//载入表格，X代表E',Y代表T',这里可以用语法糖简化书写
Map<Character,String> maprow1 =
new HashMap<>();
maprow1.put('i',"TX");
maprow1.put('(',"TX");
mapcol.put('E',maprow1);
Map<Character,String> maprow2 =
new HashMap<>();
maprow2.put('i',"FY");
maprow2.put('(',"FY");
mapcol.put('T',maprow2);
Map<Character,String> maprow3 =
new HashMap<>();
maprow3.put(')',"ε");
maprow3.put('+',"ATX");
maprow3.put('-',"ATX");
分类专栏
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
}

本来是打算再写一个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}