编译原理OJ平台练习题题解

A.小C语言–词法分析程序

小C语言--词法分析程序
Description
小C语言文法 
1. <程序>→<main关键字>(){<声明序列><语句序列>}
2. <声明序列>→<声明序列><声明语句>|<声明语句>|<空>
3. <声明语句>→<标识符表>;
4. <标识符表>→<标识符>,<标识符表>|<标识符>
5. <语句序列>→<语句序列><语句>|<语句>
6. <语句>→< if语句>|< while语句>|< for语句>|<复合语句>|<赋值语句>
7. < if语句>→< if关键字>(<表达式>)<复合语句>|(<表达式>)<复合语句>< else关键字><复合语句>
8. < while语句>→< while关键字>(<表达式>)<复合语句>
9. < for语句>→< for关键字>(<表达式>;<表达式>;<表达式>)<复合语句>
10. <复合语句>→{<语句序列>}
11. <赋值语句>→<表达式>;
12. <表达式>→<标识符>=<算数表达式>|<布尔表达式>
13. <布尔表达式>→<算数表达式> |<算数表达式><关系运算符><算数表达式>
14. <关系运算符>→>|<|>=|<=|==|!=
15. <算数表达式>→<算数表达式>+<项>|<算数表达式>-<项>|<项>
16. <项>→<项>*<因子>|<项>/<因子>|<因子>
17. <因子>→<标识符>|<无符号整数>|(<算数表达式>)
18. <标识符>→<字母>|<标识符><字母>|<标识符><数字>
19. <无符号整数>→<数字>|<无符号整数><数字>
20. <字母>→a|b|…|z|A|B|…|Z
21. <数字>→0|1|2|3|4|5|6|7|8|922. < main关键字>→main
23. < if关键字>→if
24. < else关键字>→else
25. < for关键字>→for
26. < while关键字>→while
27. < int关键字>→int每行单词数不超过10个
小C语言文法如上，现在我们对小C语言写的一个源程序进行词法分析，分析出关键字、自定义标识符、整数、界符
和运算符。
关键字：main if else for while int
自定义标识符：除关键字外的标识符
整数：无符号整数
界符：{ } ( ) , ;
运算符：= + - * / < <= > >= == !=Input
输入一个小C语言源程序，源程序长度不超过2000个字符，保证输入合法。Output
按照源程序中单词出现顺序输出，输出二元组形式的单词串。(单词种类,单词值)单词一共5个种类：关键字：用keyword表示
自定义标识符：用identifier表示
整数：用integer表示
界符：用boundary表示
运算符：用operator表示每种单词值用该单词的符号串表示。Samples
Sample #1
Input 
Output 
main() 
{int a, b;if(a == 10){a = b;}
}
(keyword,main)
(boundary,()
(boundary,))
(boundary,{)
(keyword,int)
(identifier,a)
(boundary,,)
(identifier,b)
(boundary,;)
(keyword,if)
(boundary,()
(identifier,a)
(operator,==)
(integer,10)
(boundary,))
(boundary,{)
(identifier,a)
(operator,=)
(identifier,b)
(boundary,;)
(boundary,})
(boundary,})

#include <bits/stdc++.h>
using namespace std;
string kw[6] = {"main","if","else","int","for","while"};
string x,y;void jud(){if(!y.empty()){cout<<"(integer,"<<y<<')'<<endl;y="";}if(!x.empty()){for(int i=0;i<6;i++){if(x==kw[i]){cout<<"(keyword,"<<x<<')'<<endl;x="";}}}if(!x.empty()){cout<<"(identifier,"<<x<<')'<<endl;x="";}
}
int main(){string a;while(getline(cin,a)){for(int i=0;i<a.size();i++){if(a[i]==' '){jud();continue;}else if(a[i]=='{'||a[i]=='}'||a[i]=='('||a[i]==')'||a[i]==','||a[i]==';'){jud();cout<<"(boundary,"<<a[i]<<')'<<endl;}else if(a[i]=='='||a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='!'||a[i]=='>'||a[i]=='<'){jud();cout<<"(operator,"<<a[i];if(i+1<a.size()&&a[i+1]=='='){cout<<a[i+1];i++;}cout<<')'<<endl;}else {if(x.empty()&&isdigit(a[i])){y+=a[i];}else x+=a[i];}}}return 0;
}

B - 识别浮点常量问题

Description
编译器在对程序进行编译之前，首先要进行语法分析。通常，程序被分解成若干个小单元，然后和语言的语法模式进行匹配。在分析表达式的时候，变量的类型在变量声明的时候就决定了；而常量的类型需要从常量的形式来判断。假设你是自动编译器（ACM）开发小组的一员，负责Pascal语言编译器的开发。你的任务是分析程序分解模块送来的文件，判断其中包含的字符串是否合乎语法的Pascal浮点常量。Pascal语言对浮点常量的语法要求是：一个浮点常量除了十进制数码之外，必须带有一个小数点或一个指数（紧接在字母e或E之后，在正式文档中也被称为比例因子）。如果该浮点常量含有小数点，则在小数点两侧都至少要有一个十进制数码。当然，在整个浮点常量或指数之前，也许会出现符号+或-。指数不能包含小数。空格也许会出现在浮点常量的前后，但不会出现在浮点常量中间。请注意Pascal语言的语法规则没有对浮点数常量的取值范围作出任何假定。
Input
输入只有一行，就是有待识别的字符串。字符串的长度不超过255。
Output
请将分析的结果按以下样例的格式输出。如果输入文件中的字符串是Pascal浮点常量，请输出字符串“YES”，否则输出字符串“NO”。
Samples
Sample #1
Input 
Output 
1.2
YES
Hint
输入：1                                             输出：NO
输入：1.0e-55                                 输出：YES
输入：e-12                                       输出：NO
输入：1e-12                                    输出：YES
输入：6.5E                                       输出：NO
输入：+4.1234567890E-9999     输出: YES

#include <bits/stdc++.h>
using namespace std;int judge_function(char s[]) { int i, j, k;int a, b;int len = strlen(s);// 确定有效字符的开始位置afor(i = 0; i < len; i++) {if(s[i] != ' ') {break;}}a = i;// 确定有效字符的结束位置bfor(i = len - 1; i >= 0; i--) {if(s[i] != ' ') {break;}}b = i;// 从a到b遍历有效字符for(i = a; i <= b; i++) {if(s[i] == '+' || s[i] == '-') { if(i != 0) {j = i - 1; k = i + 1;if(i >= len - 1) { return 0;}if(!((s[j] == 'e' || s[j] == 'E') && (s[k] >= '0' && s[k] <= '9'))) {break;}}} else if(s[i] == 'e' || s[i] == 'E') {j = i - 1;k = i + 1;if(i >= len - 1) {return 0;}if(!((s[j] >= '0' && s[j] <= '9') && (s[k] == '+' || s[k] == '-' || (s[k] >= '0' && s[k] <= '9')))) {break;}for(j = i; j <= b; j++) {if(s[j] == '.') {break;}}if(j <= b) {break;}} else if(s[i] == '.') {j = i - 1;k = i + 1;if(i >= len - 1) {return 0;}if(!((s[j] >= '0' && s[j] <= '9') && (s[k] >= '0' && s[k] <= '9'))) {break;}} else if(s[i] >= '0' && s[i] <= '9') {continue;} else {break;}}if(i < b) {return 0;} else {return 1;}
}int main() {char s[256];int i;int flag1, flag2;while(fgets(s, sizeof(s), stdin)) { // 使用fgets替代getsflag1 = 0;flag2 = 0;int len = strlen(s);for(i = 0; i < len; i++) {if(s[i] == 'e' || s[i] == 'E') {flag1++;}if(s[i] == '.') {flag2++;}}if((flag1 == 1 && flag2 == 1) || (flag1 + flag2 == 1)) {if(judge_function(s)) {cout << "YES" << endl;} else {cout << "NO" << endl;}} else {cout << "NO" << endl;}}return 0;
}

C - 小型Basic编译器问题

Description
编写一个TinyBasic语言的解释程序，对于任何一个给出的正确的TinyBasic语言的程序，你的程序能运行它并得到正确的结果。那么，怎样的TinyBasic的程序叫做正确的呢？（1）符合TinyBasic语言的语法规则；
（2）程序执行时会产生一个或多个输出，可以中断（即程序不会进入无限循环状态）。TinyBasic语言的语法规则：（1）每一行的TinyBasic程序都是下面这样的形式（所有出现的字母均为大写）
[<空格>]<行号><空格><语句>
其中，[<空格>]中可以有任意个空格，当然也可以没有；
<行号>中一定要有行号，从1开始，依次递增1；
<空格>中至少有一个空格；
<语句>应为下面的语句之一：
LET<空格><变量>=<表达式>
PRINT<空格><变量>
GOTO<空格><表达式>
IF<空格><表达式>
STOP
（2）定义变量和表达式的规则为
<变量>必须是单个的大写英文字母，存储一个整数值；
<表达式>为   
<常量> 范围在[-10000…10000]内的整数常量，比如0，-5，34  <变量>+<变量> 两个变量所代表的是有符号整数   
<变量>><变量> 大于号，真为1，假为0
（3）表达式中和LET语句的=（等号）两边没有空格；
（4）TinyBasic的程序最多只有100行。执行TinyBasic语言程序的规则：（1）从程序中的第1行开始执行；
（2）程序中用到的所有变量的初始值均为0；
（3）语句连续执行除非碰到IF或GOTO语句；
（4）5种语句的定义
LET 给变量赋值。若两个变量相加，相加的结果在[-10000…10000]之内。  
PRINT <变量名>=<值>的格式打印变量的值。左对齐，并单独占用一行；行中无任何多余空格。
GOTO 跳到行号为<表达式>的值的一行。<表达式>不需要是一个常量；<表达式>的值是程序中的有效行号。  
IF 如果表达式的值非0继续执行下一行；如果表达式的值为0跳过下一行，执行下一行的下一行。在IF语句以下至少还应该有两条语句。
STOP 终止执行。TinyBasic程序一定会执行到STOP语句（如果你的解释程序是正确的话）；TinyBasic程序可能包含一个以上的STOP语句；程序的最后一句不一定是STOP语句。
Input
输入数据只有一组，包含一个程序，没有多余的空行，每一行为一条语句，具体要求按上面的解释。你编写的程序要正确地运行该TinyBasic程序。
Output
输出程序的运行结果，文件头尾都不需要多余空行。
Samples
Sample #1
Input 
Output 
1 LET A=10
2 LET I=0
3 LET X=I+I
4 LET T=1
5 LET X=X+T
6 PRINT X
7 LET T=1
8 LET I=I+T
9 IF A>I
10 GOTO 3
11 STOP
X=1
X=3
X=5
X=7
X=9
X=11
X=13
X=15
X=17
X=19

#include <bits/stdc++.h>
using namespace std;
struct st
{char sign[25];//体数组存指令类型char opera[25];//结构体数组执行语句
} p[129];
int value[128];//存储所有变量，ASCLL码作为下标
int run(int y,st a)
{if(!strcmp(a.sign,"STOP"))//结束程序return 0;if(!strcmp(a.sign,"IF"))//条件为真，执行下一句，否则跳过下一句{if(value[(int)a.opera[0]]>value[(int)a.opera[2]])return y+1;return y+2;}if(!strcmp(a.sign,"GOTO"))//跳转到指定行{int k,ans=0;for(k=0; a.opera[k]; k++)ans=ans*10+a.opera[k]-'0';return ans;}if(!strcmp(a.sign,"LET"))//赋值{if(isalpha(a.opera[2]))//类似X=A+B的情况value[(int)a.opera[0]]=value[(int)a.opera[2]]+value[(int)a.opera[4]];else//类似X=0的情况{value[(int)a.opera[0]]=0;for(int k=2; a.opera[k]; k++)value[(int)a.opera[0]]=value[(int)a.opera[0]]*10+a.opera[k]-'0';}}else//输出printf("%c=%d\n",a.opera[0],value[(int)a.opera[0]]);return y+1;
}
int main()
{memset(value,0,sizeof(value));int x,y=1;while(~scanf("%d",&x)){scanf("%s",p[x].sign);if(strcmp(p[x].sign,"STOP"))//不为STOP是就输入scanf("%s",p[x].opera);}while(y){y=run(y,p[y]);//j为下一次执行的行数，为0则终结}return 0;
}

D - 表达式语法分析——递归子程序法

Description
递归子程序法是一种确定的自顶向下语法分析方法，要求文法是LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按LL(1)形式唯一地确定选择某个候选式进行推导。请根据下面的表达式LL(1)文法，构造递归子程序，完成对表达式的语法分析。表达式文法如下：E→TGG→+TG | εT→FSS→*FS | εF→(E) | i对于给定的输入串（长度不超过50个符号），请输出分析过程中用到的所有产生式，并指明该输入串是否为该文法能生成的表达式,输出共11行，前10行每行两个数据用空格隔开，表示推导时所用产生式顺序号（从0开始），最后一行是accept，表示i+i*i是文法能生成的合法表达式。注：其中&符号代表文法中的ε符号。
例如：i+i*i是文法能生成的一个表达式,输出格式如下：0 E-->TG1 T-->FS2 F-->i3 S-->&4 G-->+TG5 T-->FS6 F-->i7 S-->*FS8 F-->i9 S-->&10 G-->&accepti@i不是文法能生成的表达式，输出共5行，前5行每行两个数据用空格隔开，表示推导时所用产生式序号（从0开始），最后一行是error，表示i@i不是文法能生成的表达式。@不是合法的文法符号，输出格式举例：0 E-->TG1 T-->FS2 F-->i3 S-->&4 G-->&error(i+i*i不是文法能生成的表达式，存在括号不匹配的语法错误，输出格式举例：0 E-->TG1 T-->FS2 F-->(E)3 E-->TG4 T-->FS5 F-->i6 S-->&7 G-->+TG8 T-->FS9 F-->i10 S-->*FS11 F-->i12 S-->&13 G-->&errorInput
输入数据只有一行，代表待分析的符号串，以#号结束Output
输出推导过程中所有的产生式，按照使用顺序给出。输出详细说明见题目描述中的例子。Samples
Sample #1
Input 
Output 
i+i*i#
0 E-->TG
1 T-->FS
2 F-->i
3 S-->&
4 G-->+TG
5 T-->FS
6 F-->i
7 S-->*FS
8 F-->i
9 S-->&
10 G-->&
accept

#include <stdio.h>  
#include <stdlib.h>  void G();  
void E();  
void F();  
void S();  
void T();  char st[50];  
int num = 0;  
int c = 0;  int main() {  scanf("%s", st);  E();  if (st[c] == '#')  printf("accept\n");  else  printf("error\n");  return 0;  
}  void E() {  if (st[c] == 'i' || st[c] == '(') {  printf("%d E-->TG\n", num++);  T();  G();  } else {  printf("error\n");  exit(0);  }  
}  void T() {  if (st[c] == 'i' || st[c] == '(') {  printf("%d T-->FS\n", num++);  F();  S();  } else {  printf("error\n");  exit(0);  }  
}  void G() {  if (st[c] == '+') {  printf("%d G-->+TG\n", num++);  c++;  T();  G();  } else {  printf("%d G-->&\n", num++); // 用ε表示空  }  
}  void S() {  if (st[c] == '*') {  printf("%d S-->*FS\n", num++);  c++;  F();  S();  } else {  printf("%d S-->&\n", num++); // 用ε表示空  }  
}  void F() {  if (st[c] == 'i') {  printf("%d F-->i\n", num++);  c++;  } else if (st[c] == '(') {  printf("%d F-->(E)\n", num++);  c++;  E();  if (st[c] == ')') {  c++;  } else {  printf("error\n");  exit(0);  }  } else {  printf("error\n");  exit(0);  }  
}

E - 表达式语法分析——预测分析法

Description
预测分析法是自顶向下分析的一种方法，一个预测分析程序是由三个部分组成：
(1) 预测分析程序(2) 先进后出栈(3) 预测分析表现给出表达式文法：E→TGG→+TG | εT→FSS→*FS | εF→(E) | i该表达式文法是LL(1)文法，其预测分析表为：请根据该预测分析表构造预测分析程序，完成对表达式的语法分析，对给定的输入串，判断其是否为合法表达式，给出所使用的产生式序列。Input
给定输入串（长度不超过50个符号，以#号结束，符号保证是终结符或#）。例如：i+i*i# 是合法表达式i+i*(i+i)# 是合法表达式ii+i*i# 不是合法表达式i*(i+i# 不是一个合法的表达式。Output
要求输出分析过程中使用的所有产生式，产生式按使用顺序各占一行，每行有两个数据，使用顺序号（从1开始编号）及产生式本身，中间用一个空格分开，最后一行表示语法分析是否成功结束，如果成功分析结束输出acc!，表示该输入串是合法表达式，否者输出error!，表示该输入串不是合法表达式。
注：其中^符号代表文法中的ε符号。
针对输入串i+i*i#，因为分析过程使用了11次产生式，且该输入串是合法表达式，输出如下：
1 E->TG2 T->FS3 F->i4 S->^5 G->+TG6 T->FS7 F->i8 S->*FS9 F->i10 S->^11 G->^acc!针对输入串i*(i+i#，因为分析过程使用了14次产生式后，发现语法错误，该输入串不是合法表达式，输出如下：1 E->TG2 T->FS3 F->i4 S->*FS5 F->(E)6 E->TG7 T->FS8 F->i9 S->^10 G->+TG11 T->FS12 F->i13 S->^14 G->^error!Samples
Sample #1
Input 
Output 
i+i*i#
1 E->TG
2 T->FS
3 F->i
4 S->^
5 G->+TG
6 T->FS
7 F->i
8 S->*FS
9 F->i
10 S->^
11 G->^
acc!

#include <iostream>
#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
stack<char> A,B;
int cn=1;
//A是分析栈 刚开始#E入栈
//B是剩余输入串 刚开始输入串入栈 (倒)//整个为LL(1)分析过程
int fun(char a,char b)
{if(a==b){A.pop();B.pop();return 1;}else if(a=='E'&&(b=='i'||b=='(')){printf("%d E->TG\n",cn++);A.pop();A.push('G');A.push('T');//倒着如栈return 1;}else if(a=='G'&&b=='+'){printf("%d G->+TG\n",cn++);A.pop();A.push('G');A.push('T');A.push('+');return 1;}else if(a=='G'&&(b==')'||b=='#')){printf("%d G->^\n",cn++);A.pop();return 1;}else if(a=='T'&&(b=='('||b=='i')){printf("%d T->FS\n",cn++);A.pop();A.push('S');A.push('F');return 1;}else if(a=='S'&&(b=='+'||b==')'||b=='#')){printf("%d S->^\n",cn++);A.pop();return 1;}else if(a=='S'&&b=='*'){printf("%d S->*FS\n",cn++);A.pop();A.push('S');A.push('F');A.push('*');return 1;}else if(a=='F'&&b=='i'){printf("%d F->i\n",cn++);A.pop();A.push('i');return 1;}else if(a=='F'&&b=='('){printf("%d F->(E)\n",cn++);A.pop();A.push(')');A.push('E');A.push('(');return 1;}return 0;}
int main()
{char str[55];scanf("%s",str);int len=strlen(str);for(int i=len-1;i>=0;i--){B.push(str[i]);}A.push('#');A.push('E');while(1){if(A.top()=='#'&&B.top()=='#'){printf("acc!\n");break;}else{int z=fun(A.top(),B.top());if(z==0){printf("error!\n");break;}}}return 0;
}

F - 算符优先分析

DescriptionE→E+T |TT→T*F |FF→(E) | i该表达式文法是算符优先文法，其算符优先分析表为： 注意：构造算符优先分析表前，请先拓广文法，例如引入非终结符Q，令Q→#E#。Input
输入数据有多行。
第一行为一个整数n(n<=50)，代表文法中产生式的个数，其中不包括拓广文法增加的产生式。
接下来的n行，每行给出一个产生式。
最后一行给出待分析的输入串，长度不超过50个符号。
Output
要求输出该文法的算符优先分析表，输出格式请参考上面的表格。
算符优先分析表中算符的排列顺序为输入文法时终结符出现的顺序，#出现在最后。
算符之间的优先关系，分别用=、<和>表示，代表相同、低于和高于的优先关系。
第一行先输出一个空格，然后按顺序输出所有算符。
第二行开始第一列为对应的算符，接着输出对应算法之间的优先关系。
输出的最后一行表示对输入串的分析是否成功结束，如果成功分析结束输出Success，表示该输入串是文法的一个句子，否者输出Fail，表示该输入串不是文法的一个句子。
Samples
Sample #1
Input 
Output 
6
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i
i+i*i
+*()i#
+><<><>
*>><><>
(<<<=< 
)>> > >
i>> > >
#<<< <=
Success

#include <iostream>
#include <string.h>
using namespace std;
string str[30][100];
char st[30][100],st1[30][100],order[60],st2[100][2],st3[100],st4[100][2];
int num[30],num1[30],bj1[30],bj2[150],sum[100][100],st3l,st4l;
char Stack[100],sta[100];
int top,top1,end1,number,bj0[150];
void print(char a)
{int b=a-'A';for(int i=0;i<num[b];i++){if(st[b][i]>='A'&&st[b][i]<='Z')print(st[b][i]);else st3[st3l++]=st[b][i];}
}
void print1(char a)
{int b=a-'A';for(int i=0;i<num1[b];i++){if(st1[b][i]>='A'&&st1[b][i]<='Z')print1(st1[b][i]);else st3[st3l++]=st1[b][i];}
}
void print_stack()
{for(int i=0;i<=top;i++)cout<<Stack[i];
}
void print_sta()
{if(top1+1==end1) cout<<"#";for(int i=top1+1;i<end1;i++)cout<<sta[i];
}
int main()
{int i,j,k,kk,m,n,nn,mm,bj,l,ll,bj3;char s;while(cin>>m){memset(bj0,0,sizeof(bj0));    //test9l=ll=bj3=st4l=0;for(i=0;i<150;i++)bj2[i]=0;for(i=0;i<30;i++){num[i]=0; num1[i]=0; bj1[i]=0;}string str1,str2;for(i=0;i<m;i++){cin>>str1;if(i==0) s=str1[0];mm=str1[0]-'A';n=str1.size();str2=str1.substr(3,n);char *p=&str2[0];//const char *d="|";//p=strtok(str3,d);//while(p!=NULL)//{bj=0;nn=strlen(p);if(nn==1){st[mm][num[mm]]=p[0];num[mm]++;st1[mm][num1[mm]]=p[0];num1[mm]++;if(p[0]<'A'||p[0]>'Z'){bj0[p[0]]=1;     //test9if(p[0]!='#'){order[l++]=p[0]; bj2[p[0]]=1;}else bj3=1;}}else{int aa=0;char bb;for(j=0;j<nn;j++){if(p[j]<'A'||p[j]>'Z'){bj0[p[j]]=nn;       //test9if(aa==0){bb=p[j];aa=1;}else{st4[st4l][0]=bb;st4[st4l++][1]=p[j];}if(bj2[p[j]]==0){if(p[j]!='#'){order[l++]=p[j];bj2[p[j]]=1;}else bj3=1;}if(bj!=1){bj=1;st[mm][num[mm]]=p[j];num[mm]++;}}if(j>0){if((p[j]<'A'||p[j]>'Z')&&p[j-1]>='A'&&p[j-1]<='Z'){st2[ll][0]=p[j-1];st2[ll++][1]=p[j];continue;}if((p[j-1]<'A'||p[j-1]>'Z')&&p[j]>='A'&&p[j]<='Z'){st2[ll][0]=p[j-1];st2[ll++][1]=p[j];}}}if(bj==0){st[mm][num[mm]]=p[0];num[mm]++;}bj=0;for(j=nn-1;j>=0;j--){if(p[j]<'A'||p[j]>'Z'){bj=1;st1[mm][num1[mm]]=p[j];num1[mm]++;break;}}if(bj==0){st1[mm][num[mm]]=p[0];num1[mm]++;}}//p=strtok(NULL,d);//}}order[l++]='#';bj2['#']=1;st2[ll][0]='#';st2[ll++][1]=s;st2[ll][0]=s;st2[ll++][1]='#';memset(sum,0,sizeof(sum));for(i=0;i<ll;i++){st3l=0;if(st2[i][0]>='A'&&st2[i][0]<='Z'){print1(st2[i][0]);for(j=0;j<l;j++){if(st2[i][1]==order[j]){for(k=0;k<st3l;k++){for(kk=0;kk<l;kk++){if(st3[k]==order[kk]){sum[kk][j]=3;break;}}}break;}}}else{print(st2[i][1]);for(j=0;j<l;j++){if(st2[i][0]==order[j]){for(k=0;k<st3l;k++){for(kk=0;kk<l;kk++){if(st3[k]==order[kk]){sum[j][kk]=1;break;}}}break;}}}}for(i=0;i<st4l;i++){for(j=0;j<l;j++){if(st4[i][0]==order[j]){for(k=0;k<l;k++){if(st4[i][1]==order[k]){sum[j][k]=2;break;}}break;}}}sum[l-1][l-1]=2;//test9cin>>sta;cout<<" ";for(i=0;i<l;i++)cout<<order[i];cout<<endl;for(i=0;i<l;i++){cout<<order[i];for(j=0;j<l;j++){if(sum[i][j]==1)cout<<"<";else if(sum[i][j]==2)cout<<"=";else if(sum[i][j]==3)cout<<">";else cout<<" ";}cout<<endl;}int flag=0;end1=strlen(sta);sta[end1]='#';end1++;top=number=top1=0;Stack[0]='#';bj0['#']=1;/*for(i=0;i<150;i++)cout<<bj0[i]<<" ";cout<<endl;*/for(i=0;i<end1;i++){if(bj0[sta[i]]==0){flag=1;break;}}while(top>=0){if(flag==1) break;//number++;//cout<<number<<"\t";//print_stack();mm=-1;for(i=top;i>=0;i--){if(Stack[i]<'A'||Stack[i]>'Z'){mm=i;break;}}if(mm==-1) {flag=1;break;}k=kk=-1;for(i=0;i<l;i++){if(order[i]==Stack[mm]){k=i;}if(order[i]==sta[top1]){kk=i;}}if(k==-1||kk==-1){flag=1;break;}//cout<<"\t";if(sum[k][kk]==1){//cout<<"<\t";}else if(sum[k][kk]==2){//cout<<"=\t";}else if(sum[k][kk]==3){//cout<<">\t";}else{flag=1;break;}//if(sta[top1]!='#') cout<<sta[top1]<<"\t";//else cout<<" \t";//print_sta();//cout<<"\t";if(sum[k][kk]==1){//cout<<"移进"<<endl;top1++;Stack[++top]=sta[top1-1];}else if(sum[k][kk]==2){if(sta[top1]!='#'){//cout<<"移进"<<endl;top1++;Stack[++top]=sta[top1-1];}else if(Stack[mm]=='#'){//cout<<"接受"<<endl;break;}}else if(sum[k][kk]==3){//cout<<"归约"<<endl;top-=(bj0[Stack[mm]]-1);Stack[top]='N';}}if(flag==0) cout<<"Success"<<endl;else cout<<"Fail"<<endl;}return 0;
}

G - 算符优先系列之(一)Firstvt和Lastvt集

Description
学过编译原理的菊苣们都知道算符优先文法，作为一个有点深度的分析方法，我们怎么能只止步于理论呢，实践才是王道哦。已知文法G[S]的表达式，计算G[S]的Firstvt和Lastvt。因为某些特殊的原因，我们在这规定一下输入输出格式。例如：已知文法G[S]为：S->a|@|(T)T->T,S|S首先先把各条件语句按照从左到右从上到下的方式分解和输出S->aS->@S->(T)T->T,ST->S对于输出首先输出FIRSTVT集然后输出LASTVT集，对于各自的集合的的输出按照非终结符从上向下的方式Firstvt[S]:非终结符+空格的形式Firstvt[T]:Lastvt[S]:Lastvt[T]:Input
多组输入。第一行输入一个n，表示表达式的个数，接下来n行，每行一个表达式Output
根据上述的格式，输出文法的Firstvt和Lastvt集合Samples
Sample #1
Input 
Output 
2
S->a|@|(T)
T->T,S|S
Firstvt[S]:a @ ( 
Firstvt[T]:, a @ ( 
Lastvt[S]:a @ ) 
Lastvt[T]:, a @ )

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
typedef long long LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
using namespace std;const int Maxn=110;
const int maxn=20;
char str[maxn][Maxn];//输入文法
char st[maxn];//输入串
char stac[maxn];//模拟栈的数组
char nstr[maxn][maxn];//储存转化文法
char mstr[maxn][maxn];
char fin[maxn];//存储终结符
char firstvt[maxn][maxn],lastvt[maxn][maxn];
char cmp[maxn][maxn];//存储表中的比较符
int firstflag[maxn],lastflag[maxn];//非终结符的firstvt,lastvt是否求出
int fcnt[maxn],lcnt[maxn];//非终结符firsvt和lastvt的个数
int is_fin(char c) { //判断终结符for(int i=0; fin[i]!='\0'; i++) {if(fin[i]==c)return 1;}return 0;
}
int site(char c) { //求在表中的下标for(int i=0; fin[i]!='\0'; i++) {if(fin[i]==c)return i;}
}
void get_firstvt(char s,int t) { //求s非终结符的firstvt值int i,j,ii,jj,tt;for(i=0; i<t; i++) {if(str[i][0]==s)break;}if(!firstflag[i]) {int k=fcnt[i];for(j=0; str[i][j]!='\0'; j++) {if(j==2||str[i][j]=='|') {if(is_fin(str[i][j+1])) {firstvt[i][k++]=str[i][j+1];} else {if(is_fin(str[i][j+2])) {firstvt[i][k++]=str[i][j+2];}if(str[i][j+1]!=s) {get_firstvt(str[i][j+1],t);for(ii=0; ii<t; ii++) {if(str[ii][0]==str[i][j+1])break;}for(jj=0; jj<fcnt[ii]; jj++) {for(tt=0; tt<k; tt++) {if(firstvt[i][tt]==firstvt[ii][jj])break;}if(tt==k) {firstvt[i][k++]=firstvt[ii][jj];}}}}}}firstvt[i][k]='\0';fcnt[i]=k;firstflag[i]=1;}
}void output_firstvt(int T) { //输出firstvt集for(int i=0; i<T; i++) {get_firstvt(str[i][0],T);}for(int i=0; i<T; i++) {printf("Firstvt[%c]:",str[i][0]);for(int j=0; j<fcnt[i]; j++) {printf("%c ",firstvt[i][j]);}puts("");}
}void get_lastvt(char s,int t) { //求s非终结符的lastvt值int i,j,ii,jj,tt;for(i=0; i<t; i++) {if(str[i][0]==s)break;}if(!lastflag[i]) {int k=lcnt[i];for(j=0; str[i][j]!='\0'; j++) {if(str[i][j+1]=='|'||str[i][j+1]=='\0') {if(is_fin(str[i][j])) {lastvt[i][k++]=str[i][j];} else {if(is_fin(str[i][j-1])) {lastvt[i][k++]=str[i][j-1];}if(str[i][j]!=s) {get_lastvt(str[i][j],t);for(ii=0; ii<t; ii++) {if(str[ii][0]==str[i][j])break;}for(jj=0; jj<lcnt[ii]; jj++) {for(tt=0; tt<k; tt++) {if(lastvt[i][tt]==lastvt[ii][jj])break;}if(tt==k) {lastvt[i][k++]=lastvt[ii][jj];}}}}}}lastvt[i][k]='\0';lcnt[i]=k;lastflag[i]=1;}
}void output_lastvt(int T) { //输出lastvt集for(int i=0; i<T; i++) {get_lastvt(str[i][0],T);}for(int i=0; i<T; i++) {printf("Lastvt[%c]:",str[i][0]);for(int j=0; j<lcnt[i]; j++) {printf("%c ",lastvt[i][j]);}puts("");}
}
void output(int i,int j,char *str) {printf("\t");for(int ii=i; ii<=j; ii++)printf("%c",str[ii]);
}
int main() {int T;while(scanf("%d",&T)!=EOF){int cnt=0;//终结符的个数memset(firstflag,0,sizeof(firstflag));memset(lastflag,0,sizeof(lastflag));memset(cmp,0,sizeof(cmp));for(int i=0; i<T; i++) {scanf("%s",str[i]);fcnt[i]=lcnt[i]=0;}for(int i=0; i<T; i++) {for(int j=0; str[i][j]!='\0'; j++) {if((str[i][j]<'A'||str[i][j]>'Z')&&(str[i][j]!='-'&&str[i][j]!='>')&&str[i][j]!='|')fin[cnt++]=str[i][j];}}fin[cnt++]='#';fin[cnt]='\0';output_firstvt(T);output_lastvt(T);}return 0;
}

H - 算符优先系列之(二)算符优先关系表

Description
学过编译原理的菊苣们都知道算符优先文法，作为一个有点深度的分析方法，我们怎么能只止步于理论呢，实践才是王道哦。已知文法G[S]的表达式，求算符优先关系表。因为某些特殊的原因，我们在这规定一下输入输出格式。已知文法G[S]为：S`->#S#(拓展文法,不是题目给出的文法)S->a|@|(T)T->T,S|S表达式算符优先关系表中从左到右(从上到下)的顺序为从表达式文法中从左到右从上到下的顺序即为a @ ( ) , #  （我们默认把#放在最右边或者最下边）Input
多组输入。第一行输入一个n，表示表达式的个数，接下来n行每行一个表达式(记得还有一个要在自己程序中添加的拓展文法哦)Output
根据上述的格式，输出算符优先关系表(输出的格式用水平制表符\t)Samples
Sample #1
Input 
Output 
2
S->a|@|(T)
T->T,S|Sa	@	(	)	,	#
a	 	 	 	>	>	>	
@	 	 	 	>	>	>	
(	<	<	<	=	<	 	
)	 	 	 	>	>	>	
,	<	<	<	>	>	 	
#	<	<	<	 	 	=	

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
using namespace std;const int Maxn=110;
const int maxn=20;
char str[maxn][Maxn];//输入文法
char st[maxn];//输入串
char stac[maxn];//模拟栈的数组
char nstr[maxn][maxn];//储存转化文法
char mstr[maxn][maxn];
char fin[maxn];//存储终结符
char firstvt[maxn][maxn],lastvt[maxn][maxn];
char cmp[maxn][maxn];//存储表中的比较符
int firstflag[maxn],lastflag[maxn];//非终结符的firstvt,lastvt是否求出
int fcnt[maxn],lcnt[maxn];//非终结符firsvt和lastvt的个数
int is_fin(char c) { //判断终结符for(int i=0; fin[i]!='\0'; i++) {if(fin[i]==c)return 1;}return 0;
}
int site(char c) { //求在表中的下标for(int i=0; fin[i]!='\0'; i++) {if(fin[i]==c)return i;}
}void get_firstvt(char s,int t) { //求s非终结符的firstvt值int i,j,ii,jj,tt;for(i=0; i<t; i++) {if(str[i][0]==s)break;}if(!firstflag[i]) {int k=fcnt[i];for(j=0; str[i][j]!='\0'; j++) {if(j==2||str[i][j]=='|') {if(is_fin(str[i][j+1])) {firstvt[i][k++]=str[i][j+1];} else {if(is_fin(str[i][j+2])) {firstvt[i][k++]=str[i][j+2];}if(str[i][j+1]!=s) {get_firstvt(str[i][j+1],t);for(ii=0; ii<t; ii++) {if(str[ii][0]==str[i][j+1])break;}for(jj=0; jj<fcnt[ii]; jj++) {for(tt=0; tt<k; tt++) {if(firstvt[i][tt]==firstvt[ii][jj])break;}if(tt==k) {firstvt[i][k++]=firstvt[ii][jj];}}}}}}firstvt[i][k]='\0';fcnt[i]=k;firstflag[i]=1;}
}void output_firstvt(int T) { //输出firstvt集for(int i=0; i<T; i++) {get_firstvt(str[i][0],T);}}void get_lastvt(char s,int t) { //求s非终结符的lastvt值int i,j,ii,jj,tt;for(i=0; i<t; i++) {if(str[i][0]==s)break;}if(!lastflag[i]) {int k=lcnt[i];for(j=0; str[i][j]!='\0'; j++) {if(str[i][j+1]=='|'||str[i][j+1]=='\0') {if(is_fin(str[i][j])) {lastvt[i][k++]=str[i][j];} else {if(is_fin(str[i][j-1])) {lastvt[i][k++]=str[i][j-1];}if(str[i][j]!=s) {get_lastvt(str[i][j],t);for(ii=0; ii<t; ii++) {if(str[ii][0]==str[i][j])break;}for(jj=0; jj<lcnt[ii]; jj++) {for(tt=0; tt<k; tt++) {if(lastvt[i][tt]==lastvt[ii][jj])break;}if(tt==k) {lastvt[i][k++]=lastvt[ii][jj];}}}}}}lastvt[i][k]='\0';lcnt[i]=k;lastflag[i]=1;}
}void output_lastvt(int T) { //输出lastvt集for(int i=0; i<T; i++) {get_lastvt(str[i][0],T);}}void get_table(int T,int cnt) { //得到表int x=0,y=0;int i,j,ii,jj;for(i=0; i<T; i++) {for(j=0; str[i][j]!='\0'; j++) {if(str[i][j]!='|')nstr[x][y++]=str[i][j];else if(str[i][j]=='|') {nstr[x][y]='\0';x++;y=0;nstr[x][y++]=str[i][0];nstr[x][y++]='-';nstr[x][y++]='>';}}nstr[x][y]='\0';x++;y=0;}//对于S1->#S#;char a='#';cmp[site(a)][site(a)]='=';for(i=0; i<fcnt[0]; i++) {cmp[site(a)][site(firstvt[0][i])]='<';}for(i=0; i<lcnt[0]; i++) {cmp[site(lastvt[0][i])][site(a)]='>';}//对于初始的文法for(i=0; i<x; i++) {for(j=3; nstr[i][j+1]!='\0'; j++) {if(is_fin(nstr[i][j])&&is_fin(nstr[i][j+1]))cmp[site(nstr[i][j])][site(nstr[i][j+1])]='=';if(is_fin(nstr[i][j])&&!is_fin(nstr[i][j+1])&&is_fin(nstr[i][j+2])&&nstr[i][j+2]!='\0')cmp[site(nstr[i][j])][site(nstr[i][j+2])]='=';if(!is_fin(nstr[i][j])&&is_fin(nstr[i][j+1])) { //对于非终结符在终结符之前for(ii=0; ii<T; ii++) {if(str[ii][0]==nstr[i][j])break;}for(jj=0; jj<lcnt[ii]; jj++)cmp[site(lastvt[ii][jj])][site(nstr[i][j+1])]='>';}if(is_fin(nstr[i][j])&&!is_fin(nstr[i][j+1])) { //对于终结符在非终结符之前for(ii=0; ii<T; ii++) {if(str[ii][0]==nstr[i][j+1])break;}for(jj=0; jj<fcnt[ii]; jj++)cmp[site(nstr[i][j])][site(firstvt[ii][jj])]='<';}}}for(i=0; fin[i]!='\0'; i++)printf("\t%c",fin[i]);puts("");for(i=0; i<cnt; i++) {printf("%c\t",fin[i]);for(j=0; j<cnt; j++) {if(cmp[i][j]!=0)printf("%c\t",cmp[i][j]);elseprintf(" \t");}puts("");}}
void output(int i,int j,char *str) {printf("\t");for(int ii=i; ii<=j; ii++)printf("%c",str[ii]);
}int isDX(char c)
{if(c>='A'&&c<='Z')return 1;return 0;
}
void exchange()
{int ecnt=0;for(int i=0;i<10;i++){int mcnt=0;for(int j=3;nstr[i][j]!='\0';j++){if(isDX(nstr[i][j])&&strlen(nstr[i])!=4)mstr[ecnt][mcnt++]='N';else if(!isDX(nstr[i][j]))mstr[ecnt][mcnt++]=nstr[i][j];else{break;}}mstr[ecnt][mcnt]='\0';if(strlen(mstr[ecnt])!=0)ecnt++;}
}int main() {int T;while(~scanf("%d",&T)){int cnt=0;//终结符的个数memset(firstflag,0,sizeof(firstflag));memset(lastflag,0,sizeof(lastflag));memset(cmp,0,sizeof(cmp));for(int i=0; i<T; i++) {scanf("%s",str[i]);fcnt[i]=lcnt[i]=0;}for(int i=0; i<T; i++) {for(int j=0; str[i][j]!='\0'; j++) {if((str[i][j]<'A'||str[i][j]>'Z')&&(str[i][j]!='-'&&str[i][j]!='>')&&str[i][j]!='|')fin[cnt++]=str[i][j];}}fin[cnt++]='#';fin[cnt]='\0';output_firstvt(T);output_lastvt(T);get_table(T,cnt);}return 0;
}

I - 算符优先系列之(三)输入串分析

Description
学过编译原理的菊苣们都知道算符优先文法，作为一个有点深度的分析方法，我们怎么能只止步于理论呢，实践才是王道哦。已知文法G[S]的表达式和输入串，求输入串的分析过程表。因为某些特殊的原因，我们在这规定一下输入输出格式。已知文法G[S]为：S`->#S#(拓展文法,不是题目给出的文法)S->a|@|(T)T->T,S|S输出的分析过程表从左到右分为6组，依次是步骤，栈，优先关系，当前符号，剩余输入串，移进或规约步骤的标号从“1”(无引号)开始，规约时规定将可归约的项规约成非终结符“N”(无引号)，当分析串分析成功时在移进或规约组显示“jieshou”(无引号)Input
多组输入。第一行输入一个n，表示表达式的个数，接下来n行每行一个表达式(记得还有一个要在自己程序中添加的拓展文法哦)，接下来第n+2行为输入串。Output
根据上述的格式，输出输入串分析表(输出的格式用水平制表符\t)Samples
Sample #1
Input 
Output 
2
S->a|@|(T)
T->T,S|S
(a,a)#
1	#	  <	  (	  a,a)#	  yijin
2	#(	  <	  a	  ,a)#	  yijin
3	#(a	  >	  ,	  a)#	  guiyue
4	#(N	  <	  ,	  a)#	  yijin
5	#(N,	  <	  a	  )#	  yijin
6	#(N,a     >	  )	  #	  guiyue
7	#(N,N     >       )	  #	  guiyue
8	#(N	  =	  )	  #	  yijin
9	#(N)	  >	          #       guiyue
10	#N	  =	          #	  jieshou

#include <bits/stdc++.h>
using namespace std;const int Maxn = 110, maxn = 20;
char fin[maxn], cmp[maxn][maxn];
char firstvt[maxn][maxn], lastvt[maxn][maxn];
char str[maxn][Maxn], nstr[maxn][maxn], mstr[maxn][maxn], st[maxn], stac[maxn];
int firstflag[maxn], lastflag[maxn], fcnt[maxn], lcnt[maxn];int is_fin(char c)
{for (int i = 0; fin[i] != '\0'; i++){if (fin[i] == c)return 1;}return 0;
}int site(char c)
{for (int i = 0; fin[i] != '\0'; i++){if (fin[i] == c)return i;}
}void get_firstvt(char s, int t)
{int i, j, ii, jj, tt;for (i = 0; i < t; i++){if (str[i][0] == s)break;}if (!firstflag[i]){int k = fcnt[i];for (j = 0; str[i][j] != '\0'; j++){if (j == 2 || str[i][j] == '|'){if (is_fin(str[i][j + 1]))firstvt[i][k++] = str[i][j + 1];else{if (is_fin(str[i][j + 2]))firstvt[i][k++] = str[i][j + 2];if (str[i][j + 1] != s){get_firstvt(str[i][j + 1], t);for (ii = 0; ii < t; ii++){if (str[ii][0] == str[i][j + 1])break;}for (jj = 0; jj < fcnt[ii]; jj++){for (tt = 0; tt < k; tt++){if (firstvt[i][tt] == firstvt[ii][jj])break;}if (tt == k)firstvt[i][k++] = firstvt[ii][jj];}}}}}firstvt[i][k] = '\0';fcnt[i] = k;firstflag[i] = 1;}
}void output_firstvt(int T)
{for (int i = 0; i < T; i++)get_firstvt(str[i][0], T);
}void get_lastvt(char s, int t)
{int i, j, ii, jj, tt;for (i = 0; i < t; i++){if (str[i][0] == s)break;}if (!lastflag[i]){int k = lcnt[i];for (j = 0; str[i][j] != '\0'; j++){if (str[i][j + 1] == '|' || str[i][j + 1] == '\0'){if (is_fin(str[i][j]))lastvt[i][k++] = str[i][j];else{if (is_fin(str[i][j - 1]))lastvt[i][k++] = str[i][j - 1];if (str[i][j] != s){get_lastvt(str[i][j], t);for (ii = 0; ii < t; ii++){if (str[ii][0] == str[i][j])break;}for (jj = 0; jj < lcnt[ii]; jj++){for (tt = 0; tt < k; tt++){if (lastvt[i][tt] == lastvt[ii][jj])break;}if (tt == k)lastvt[i][k++] = lastvt[ii][jj];}}}}}lastvt[i][k] = '\0';lcnt[i] = k;lastflag[i] = 1;}
}void output_lastvt(int T)
{for (int i = 0; i < T; i++)get_lastvt(str[i][0], T);
}void get_table(int T, int cnt)
{int x = 0, y = 0;int i, j, ii, jj;for (i = 0; i < T; i++){for (j = 0; str[i][j] != '\0'; j++){if (str[i][j] != '|')nstr[x][y++] = str[i][j];else if (str[i][j] == '|'){nstr[x][y] = '\0';x++;y = 0;nstr[x][y++] = str[i][0];nstr[x][y++] = '-';nstr[x][y++] = '>';}}nstr[x][y] = '\0';x++;y = 0;}char a = '#';cmp[site(a)][site(a)] = '=';for (i = 0; i < fcnt[0]; i++)cmp[site(a)][site(firstvt[0][i])] = '<';for (i = 0; i < lcnt[0]; i++)cmp[site(lastvt[0][i])][site(a)] = '>';for (i = 0; i < x; i++){for (j = 3; nstr[i][j + 1] != '\0'; j++){if (is_fin(nstr[i][j]) && is_fin(nstr[i][j + 1]))cmp[site(nstr[i][j])][site(nstr[i][j + 1])] = '=';if (is_fin(nstr[i][j]) && !is_fin(nstr[i][j + 1]) && is_fin(nstr[i][j + 2]) && nstr[i][j + 2] != '\0')cmp[site(nstr[i][j])][site(nstr[i][j + 2])] = '=';if (!is_fin(nstr[i][j]) && is_fin(nstr[i][j + 1])){for (ii = 0; ii < T; ii++){if (str[ii][0] == nstr[i][j])break;}for (jj = 0; jj < lcnt[ii]; jj++)cmp[site(lastvt[ii][jj])][site(nstr[i][j + 1])] = '>';}if (is_fin(nstr[i][j]) && !is_fin(nstr[i][j + 1])){for (ii = 0; ii < T; ii++){if (str[ii][0] == nstr[i][j + 1])break;}for (jj = 0; jj < fcnt[ii]; jj++)cmp[site(nstr[i][j])][site(firstvt[ii][jj])] = '<';}}}
}void output(int i, int j, char *str)
{printf("\t");for (int ii = i; ii <= j; ii++)printf("%c", str[ii]);
}int isDX(char c)
{if (c >= 'A' && c <= 'Z')return 1;return 0;
}void exchange()
{int ecnt = 0;for (int i = 0; i < 10; i++){int mcnt = 0;for (int j = 3; nstr[i][j] != '\0'; j++){if (isDX(nstr[i][j]) && strlen(nstr[i]) != 4)mstr[ecnt][mcnt++] = 'N';else if (!isDX(nstr[i][j]))mstr[ecnt][mcnt++] = nstr[i][j];elsebreak;}mstr[ecnt][mcnt] = '\0';if (strlen(mstr[ecnt]) != 0)ecnt++;}
}int get_process(char *st)
{exchange();int len = strlen(st);int t = 0;int bz = 1;int i = 0, j;stac[0] = '#';while (st[i] != '\0'){if (is_fin(stac[t]))j = t;elsej = t - 1;int a = site(stac[j]);int b = site(st[i]);if (cmp[a][b] == '<' || cmp[a][b] == '='){printf("\t%d", bz++);output(0, t, stac);printf("\t%c\t%c", cmp[a][b], st[i]);output(i + 1, len - 1, st);printf("\tyijin\n");t++;stac[t] = st[i];i++;}else if (cmp[a][b] == '>'){printf("\t%d", bz++);output(0, t, stac);printf("\t%c\t%c", cmp[a][b], st[i]);output(i + 1, len - 1, st);printf("\tguiyue\n");int ii, jj, kk;int flag = 0;for (ii = t; ii >= 0; ii--){for (jj = 0; jj < maxn; jj++){int lee = strlen(mstr[jj]);int kkn = 0;for (kk = lee - 1; kk >= 0; kk--){if (stac[ii] == mstr[jj][kk]){ii--;kkn++;}elsebreak;}if (strlen(mstr[jj]) == kkn){t = ii + 1;stac[t++] = 'N';stac[t] = '\0';t--;flag = 1;break;}elseii = ii + kkn;}if (!flag){printf("\tcuowu\n");return 0;}else{if (t == 1 && st[i] == '#'){printf("\t%d", bz++);output(0, t, stac);printf("\t=\t%c\t \tjieshou\n", st[i]);return 1;}break;}}}}
}int main()
{int T;while (~scanf("%d", &T)){int cnt = 0;memset(firstflag, 0, sizeof(firstflag));memset(lastflag, 0, sizeof(lastflag));memset(cmp, 0, sizeof(cmp));for (int i = 0; i < T; i++){scanf("%s", str[i]);fcnt[i] = lcnt[i] = 0;}for (int i = 0; i < T; i++){for (int j = 0; str[i][j] != '\0'; j++){if ((str[i][j] < 'A' || str[i][j] > 'Z') && (str[i][j] != '-' && str[i][j] != '>') && str[i][j] != '|')fin[cnt++] = str[i][j];}}fin[cnt++] = '#';fin[cnt] = '\0';output_firstvt(T);output_lastvt(T);get_table(T, cnt);scanf("%s", st);get_process(st);}return 0;
}

J - LL(1)文法系列(一)first集和follow集

Description
已知文法G[S]的表达式，计算文法中终结符的first集和follow集。在文法G[S]中使用’@’代表空。现在我们规定文法G[S]中每个表达式只包含一个语句，也就是说不会含有S->A|B这样的表达式。Input
第一行输入一个n(n<10)，表示表达式的个数，接下来n行，每行一个表达式。终结符和非终结符的个数都小于10
Output
按照终结符和非终结符输入的顺序输出。如果集合中包含’@’或’#’，要求’@’位于第一个，’#’位于最后一个。
输出格式为：
first[c] = a b c
follow[c] = a b c
每个非终结符后都有空格Samples
Sample #1
Input 
Output 
4
S->ABC
A->a
B->@
C->c
first[S] = a 
first[A] = a 
first[B] = @ 
first[C] = c 
follow[S] = # 
follow[A] = c 
follow[B] = c 
follow[C] = # 

#include <bits/stdc++.h>using namespace std;struct node
{char s1[50], s2[50];
}g[100];char s[110];
int num;
map<char, int> Map1;
map<char, int> Map2;int Map1_num;
int Map2_num;char s1[110], s2[110];int first[50][50];
int follow[50][50];int vis[110];
int acc[50];int select1[100][50];int c[50][50];
char sta[110];int cnt;void dfs1(char ch, int dis[])
{if(acc[Map1[ch]]){for(int i = 1;i<=Map2_num;i++){dis[i] = first[Map1[ch]][i];}return;}int value[20];memset(value, 0, sizeof(value));for(int i = 1;i<=num;i++){if(vis[i]) continue;if(g[i].s1[0]!=ch) continue;int j, k, len = strlen(g[i].s2);for(j = 0;j<len;j++){if(Map1[g[i].s2[j]]){vis[i] = 1;dfs1(g[i].s2[j], value);for(k = 2;k<=Map2_num;k++){if(value[k]) dis[k] = 1;}if(value[1] == 0) return;}else{dis[Map2[g[i].s2[j]]] = 1;break;}}if(j == len){dis[1] = 1;}}return;
}void dfs2(char ch, int dis[])
{int i, j, k, len, flag = 0;if(acc[Map1[ch]]){for(int i = 1;i<=Map2_num;i++){dis[i] = follow[Map1[ch]][i];}return;}for(i = 1;i<=num;i++){len = strlen(g[i].s2);for(j = 0;j<len;j++){if(g[i].s2[j] == ch){flag = 1;continue;}if(!flag) continue;if(Map1[g[i].s2[j]]){for(k = 2;k<=Map2_num;k++){if(first[Map1[g[i].s2[j]]][k]){dis[k] = 1;}}if(!first[Map1[g[i].s2[j]]][1]){flag = 0;}}else{dis[Map2[g[i].s2[j]]] = 1;flag = 0;}}if(!flag||vis[i]) continue;int value[20];memset(value, 0, sizeof(value));vis[i] = 1;dfs2(g[i].s1[0], value);for(i = 1;i<=Map2_num;i++){if(value[i]) dis[i] = 1;}}
}int main()
{int i, j, len;num = Map1_num = Map2_num = 0;Map1.clear();Map2.clear();Map2['@'] = ++Map2_num;s2[Map2_num] = '@';int m;scanf("%d", &m);while(m--){scanf("%s", s);len = strlen(s);num++;for(i = 0;i<1;i++){g[num].s1[i] = s[i];if(!Map1[s[i]]){Map1[s[i]] = ++Map1_num;s1[Map1_num] = s[i];}}g[num].s1[i] = '\0';for(i = 3;i<len;i++){g[num].s2[i-3] = s[i];if(s[i]>='A'&&s[i]<='Z'){if(!Map1[s[i]]){Map1[s[i]] = ++Map1_num;s1[Map1_num] = s[i];}}else{if(!Map2[s[i]]){Map2[s[i]] = ++Map2_num;s2[Map2_num] = s[i];}}}g[num].s2[i-3] = '\0';}memset(first, 0, sizeof(first));memset(acc, 0, sizeof(acc));for(i = 1;i<=Map1_num;i++){int value[20];memset(vis,0,sizeof(vis));memset(value,0,sizeof(value));dfs1(s1[i],value);for(j = 1 ; j <= Map2_num; j++){first[i][j] = value[j] ;}acc[i] = 1 ;printf("first[%c] = ", s1[i]);for(j = 1 ; j <= Map2_num ; j++){if( first[i][j] ){printf("%c ", s2[j]);}}printf("\n");}Map2['#'] = ++Map2_num ;s2[ Map2_num ] = '#' ;memset(follow,0,sizeof(follow));memset(acc,0,sizeof(acc));for(i = 1 ; i <= Map1_num ; i++){int value[20] ;memset(vis,0,sizeof(vis)) ;memset(value,0,sizeof(value));if( s1[i] == 'S' ) {value[ Map2['#'] ] = 1 ;}dfs2(s1[i],value);for(j = 1 ; j <= Map2_num; j++){follow[i][j] = value[j] ;}acc[i] = 1 ;printf("follow[%c] = ", s1[i]);for(j = 1 ; j <= Map2_num ; j++){if( follow[i][j] ){printf("%c ", s2[j]);}}printf("\n");}return 0;
}

K - LL(1)文法系列(三)预测分析程序

Description
已知文法G[S]的表达式，通过预测分析表，对输入串进行分析。在文法G[S]中使用’@’代表空。现在我们规定文法G[S]中每个表达式只包含一个语句，也就是说不会含有S -> A|B这样的表达式。Input
第一行输入一个n(n < 10)，表示表达式的个数，接下来n行，每行一个表达式。终结符和非终结符的个数都小于10最后一行输入字符串，长度小于20，输入串以#结尾Output
按照示例进行输出（从左到右按照栈、输入缓冲区、输出结果的顺序打印），使用\t进行格式控制，保证输入串合法。为方便表示，将输入串翻转，在当前串中输出。Samples
Sample #1
Input 
Output 
4
S->ABC
A->a
B->@
C->c
ac#
#S	#ca	S->ABC	
#CBA	#ca	A->a
#CBa	#ca	a
#CB	#c	B->@
#C	#c	C->c
#c	#c	c
#	#	#
acc

#include <cstdio>
#include <cstring>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
struct node
{char s1[10], s2[20] ;
} g[100];char s[100] ;
int num ;
map<char,int> Map1;//对终结符映射
map<char,int> Map2;//对非终结符映射
int Map1_num, Map2_num;//记录终结符个数，非终结符个数
char s1[100] , s2[100] ;//存储终结符和非终结符
int first[20][20] ;
int follow[20][20] ;
int vis[100];//禁止重复递归
int acc[20] ;//使用以求得的集合
int select1[100][20] ;
int c[20][20] ;
char sta[100] ;
int cnt ;
void dfs1(char ch,int dis[])
{if( acc[ Map1[ch] ] ){for(int i = 1 ; i <= Map2_num; i++)dis[i] = first[ Map1[ch] ][i] ;return ;}int value[20] ;memset(value,0,sizeof(value));for(int i = 1 ; i <= num ; i++){if( vis[i] ) continue ;if( g[i].s1[0] != ch ) continue ;int j , k , len = strlen(g[i].s2) ;for(j = 0 ; j < len ; j++){if( Map1[ g[i].s2[j] ] ){vis[i] = 1 ;dfs1(g[i].s2[j],value);for(k = 2 ; k <= Map2_num ; k++)if( value[k] ) dis[k] = 1 ;if( value[1] == 0 ) return ;}else{dis[ Map2[ g[i].s2[j] ] ] = 1 ;break;}}if( j == len )dis[1] = 1 ;}return ;
}
void dfs2(char ch,int dis[])
{int i , j , k , len , flag = 0 ;if( acc[ Map1[ch] ] ){for(int i = 1 ; i <= Map2_num; i++)dis[i] = follow[ Map1[ch] ][i] ;return ;}for(i = 1 ; i <= num ; i++){len = strlen(g[i].s2) ;for(j = 0 ; j < len ; j++){if( g[i].s2[j] == ch ){flag = 1 ;continue ;}if( !flag ) continue ;if( Map1[ g[i].s2[j] ] ){for(k = 2 ; k <= Map2_num ; k++)if( first[ Map1[ g[i].s2[j] ] ][k] ) dis[k] = 1 ;if( !first[ Map1[ g[i].s2[j] ] ][1] )flag = 0 ;}else{dis[ Map2[ g[i].s2[j] ] ] = 1 ;flag = 0 ;}}if( !flag || vis[i] ) continue ;int value[20] ;memset(value,0,sizeof(value));vis[i] = 1 ;dfs2(g[i].s1[0],value);for(i = 1 ; i <= Map2_num; i++)if( value[i] ) dis[i] = 1 ;}
}
int main()
{int i , j , k , len ;//freopen("data2.in", "r", stdin);//freopen("data2.out", "w", stdout);//输入num = Map1_num = Map2_num = 0 ;Map1.clear();Map2.clear();Map2[ '@' ] = ++Map2_num;s2[ Map2_num ] = '@';int m;scanf("%d", &m);while( m-- ){scanf("%s", s);len = strlen(s) ;num++ ;for(i = 0 ; i < 1 ; i++){g[num].s1[i] = s[i] ;if( !Map1[ s[i] ] ){Map1[ s[i] ] = ++Map1_num ;s1[Map1_num] = s[i];}}g[num].s1[i] = '\0' ;for(i = 3 ; i < len ; i++){g[num].s2[i-3] = s[i] ;if( s[i] >= 'A' && s[i] <= 'Z' ){if( !Map1[ s[i] ] ){Map1[ s[i] ] = ++Map1_num ;s1[Map1_num] = s[i];}}else{if( !Map2[ s[i] ] ){Map2[ s[i] ] = ++Map2_num;s2[Map2_num] = s[i];}}}g[num].s2[i-3] = '\0';}//求firstmemset(first,0,sizeof(first));memset(acc,0,sizeof(acc));for(i = 1 ; i <= Map1_num ; i++){int value[20];memset(vis,0,sizeof(vis));memset(value,0,sizeof(value));dfs1(s1[i],value);for(j = 1 ; j <= Map2_num; j++)first[i][j] = value[j] ;acc[i] = 1 ;}//求followMap2['#'] = ++Map2_num ;s2[ Map2_num ] = '#' ;memset(follow,0,sizeof(follow));memset(acc,0,sizeof(acc));for(i = 1 ; i <= Map1_num ; i++){int value[20] ;memset(vis,0,sizeof(vis)) ;memset(value,0,sizeof(value));if( s1[i] == 'S' ) value[ Map2['#'] ] = 1 ;dfs2(s1[i],value);for(j = 1 ; j <= Map2_num; j++)follow[i][j] = value[j] ;acc[i] = 1 ;}//求select1memset(select1,0,sizeof(select1));for(i = 1 ; i <= num ; i++){for(j = 0 ; j < strlen(g[i].s2) ; j++){if( Map2[ g[i].s2[j] ] && g[i].s2[j] != '@' ){select1[i][ Map2[ g[i].s2[j] ] ] = 1 ;break ;}for(k = 2 ; k <= Map2_num ; k++){if( first[ Map1[ g[i].s2[j] ] ][k] ) select1[i][k] = 1 ;}if( first[ Map1[ g[i].s1[j] ] ][1] == 0 ) break ;}if( j == strlen( g[i].s2 ) ){for(k = 2 ;  k <= Map2_num ; k++)if( follow[ Map1[ g[i].s1[0] ] ][k] ) select1[i][k] = 1 ;}}//预测分析表memset(c,0,sizeof(c)) ;for(i = 1 ; i <= num ; i++){for(j = 1 ; j <= Map2_num ; j++){if( select1[i][j] )c[ Map1[ g[i].s1[0] ] ][j] = i ;}}scanf("%s", s);len = strlen(s) ;for(i = 0 ; i < len/2 ; i++){swap( s[i], s[len-1-i] );}cnt = 0 ;i = len-1 ;char ch;sta[cnt++] = '#';sta[cnt++] = 'S';while( i >= 0 ){if( cnt == 0 ){printf("@\n");break ;}ch = sta[cnt-1] ;if( Map1[ch] ){j = c[ Map1[ch] ][ Map2[ s[i] ] ] ;if( j ){sta[cnt] = '\0' ;s[i+1] = '\0' ;printf("%s\t%s\t%s->%s\n", sta, s, g[j].s1, g[j].s2);cnt-- ;for(k = strlen( g[j].s2 ) - 1 ; k >= 0 ; k-- ){if( g[j].s2[k] != '@' )sta[cnt++] = g[j].s2[k] ;}}else{printf("@\n") ;break ;}}else{if( ch == s[i] ){sta[cnt] = '\0' ;s[i+1] = '\0' ;printf("%s\t%s\t%c\n", sta, s, ch);cnt-- ;i--;}else{printf("@\n") ;break;}}}if( i < 0 )printf("acc\n");return 0;
}

L - LL(1)文法系列(二)预测分析表

Description
已知文法G[S]的表达式，计算文法的预测分析表。在文法G[S]中使用’@’代表空。现在我们规定文法G[S]中每个表达式只包含一个语句，也就是说不会含有S->A|B这样的表达式。Input第一行输入一个n(n<10)，表示表达式的个数，接下来n行，每行一个表达式。终结符和非终结符的个数都小于10Output
按照终结符和非终结符输入的顺序输出。’#’作为非终结符的最后一个。
按照示例进行输出，使用\\t进行格式控制Samples
Sample #1
Input 
Output 
4
S->ABC
A->a
B->@
C->ca	c	#	
S	ABC			
A	a			
B		@		
C		c

#include <cstdio>
#include <cstring>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
struct node
{char s1[10], s2[20] ;
} g[100];char s[100] ;
int num ;
map<char,int> Map1;//对终结符映射
map<char,int> Map2;//对非终结符映射
int Map1_num, Map2_num;//记录终结符个数，非终结符个数
char s1[100] , s2[100] ;//存储终结符和非终结符
int first[20][20] ;
int follow[20][20] ;
int vis[100];//禁止重复递归
int acc[20] ;//使用以求得的集合
int select1[100][20] ;
int c[20][20] ;
char sta[100] ;
int cnt ;
void dfs1(char ch,int dis[])
{if( acc[ Map1[ch] ] ){for(int i = 1 ; i <= Map2_num; i++)dis[i] = first[ Map1[ch] ][i] ;return ;}int value[20] ;memset(value,0,sizeof(value));for(int i = 1 ; i <= num ; i++){if( vis[i] ) continue ;if( g[i].s1[0] != ch ) continue ;int j , k , len = strlen(g[i].s2) ;for(j = 0 ; j < len ; j++){if( Map1[ g[i].s2[j] ] ){vis[i] = 1 ;dfs1(g[i].s2[j],value);for(k = 2 ; k <= Map2_num ; k++)if( value[k] ) dis[k] = 1 ;if( value[1] == 0 ) return ;}else{dis[ Map2[ g[i].s2[j] ] ] = 1 ;break;}}if( j == len )dis[1] = 1 ;}return ;
}
void dfs2(char ch,int dis[])
{int i , j , k , len , flag = 0 ;if( acc[ Map1[ch] ] ){for(int i = 1 ; i <= Map2_num; i++)dis[i] = follow[ Map1[ch] ][i] ;return ;}for(i = 1 ; i <= num ; i++){len = strlen(g[i].s2) ;for(j = 0 ; j < len ; j++){if( g[i].s2[j] == ch ){flag = 1 ;continue ;}if( !flag ) continue ;if( Map1[ g[i].s2[j] ] ){for(k = 2 ; k <= Map2_num ; k++)if( first[ Map1[ g[i].s2[j] ] ][k] ) dis[k] = 1 ;if( !first[ Map1[ g[i].s2[j] ] ][1] )flag = 0 ;}else{dis[ Map2[ g[i].s2[j] ] ] = 1 ;flag = 0 ;}}if( !flag || vis[i] ) continue ;int value[20] ;memset(value,0,sizeof(value));vis[i] = 1 ;dfs2(g[i].s1[0],value);for(i = 1 ; i <= Map2_num; i++)if( value[i] ) dis[i] = 1 ;}
}
int main()
{int i , j , k , len ;//输入num = Map1_num = Map2_num = 0 ;Map1.clear();Map2.clear();Map2[ '@' ] = ++Map2_num;s2[ Map2_num ] = '@';int m;scanf("%d", &m);while( m-- ){scanf("%s", s);len = strlen(s) ;num++ ;for(i = 0 ; i < 1 ; i++){g[num].s1[i] = s[i] ;if( !Map1[ s[i] ] ){Map1[ s[i] ] = ++Map1_num ;s1[Map1_num] = s[i];}}g[num].s1[i] = '\0' ;for(i = 3 ; i < len ; i++){g[num].s2[i-3] = s[i] ;if( s[i] >= 'A' && s[i] <= 'Z' ){if( !Map1[ s[i] ] ){Map1[ s[i] ] = ++Map1_num ;s1[Map1_num] = s[i];}}else{if( !Map2[ s[i] ] ){Map2[ s[i] ] = ++Map2_num;s2[Map2_num] = s[i];}}}g[num].s2[i-3] = '\0';}//求firstmemset(first,0,sizeof(first));memset(acc,0,sizeof(acc));for(i = 1 ; i <= Map1_num ; i++){int value[20];memset(vis,0,sizeof(vis));memset(value,0,sizeof(value));dfs1(s1[i],value);for(j = 1 ; j <= Map2_num; j++)first[i][j] = value[j] ;acc[i] = 1 ;}//求followMap2['#'] = ++Map2_num ;s2[ Map2_num ] = '#' ;memset(follow,0,sizeof(follow));memset(acc,0,sizeof(acc));for(i = 1 ; i <= Map1_num ; i++){int value[20] ;memset(vis,0,sizeof(vis)) ;memset(value,0,sizeof(value));if( s1[i] == 'S' ) value[ Map2['#'] ] = 1 ;dfs2(s1[i],value);for(j = 1 ; j <= Map2_num; j++)follow[i][j] = value[j] ;acc[i] = 1 ;}//求select1memset(select1,0,sizeof(select1));for(i = 1 ; i <= num ; i++){for(j = 0 ; j < strlen(g[i].s2) ; j++){if( Map2[ g[i].s2[j] ] && g[i].s2[j] != '@' ){select1[i][ Map2[ g[i].s2[j] ] ] = 1 ;break ;}for(k = 2 ; k <= Map2_num ; k++){if( first[ Map1[ g[i].s2[j] ] ][k] ) select1[i][k] = 1 ;}if( first[ Map1[ g[i].s1[j] ] ][1] == 0 ) break ;}if( j == strlen( g[i].s2 ) ){for(k = 2 ;  k <= Map2_num ; k++)if( follow[ Map1[ g[i].s1[0] ] ][k] ) select1[i][k] = 1 ;}}//预测分析表memset(c,0,sizeof(c)) ;for(i = 1 ; i <= num ; i++){for(j = 1 ; j <= Map2_num ; j++){if( select1[i][j] )c[ Map1[ g[i].s1[0] ] ][j] = i ;}}for(i = 1 ; i <= Map2_num ; i++){if( i == 1 ) printf("\t") ;elseprintf("%c\t", s2[i]) ;}printf("\n") ;for(i = 1 ; i <= Map1_num ; i++){printf("%c\t", s1[i]) ;for(j = 2 ; j <= Map2_num ; j++){if( c[i][j] == 0 ) printf("\t") ;else printf("%s\t", g[ c[i][j] ].s2) ;}printf("\n") ;}return 0;
}

M - LR(1)文法

Description
已知文法G[S]的表达式求文法的LR(1)的项目集和Go函数.要求使用广度优先搜索,同时按照字典序进行转换,以保证项目集的序号正确.Input
单组输入,当输入一个@时输入结束.注意: 在输入中以@代表空.规定:文法S的拓广文法为$->SOutput
输出文法的项目集和Go函数,参考示例中的格式Samples
Sample #1
Input 
Output 
S->rD
D->Dai
D->i
@
Package: 0
$->.S
S->.rD
Package: 1
$->S.
Package: 2
S->r.D
D->.Dai
D->.i
Package: 3
S->rD.
D->D.ai
Package: 4
D->i.
Package: 5
D->Da.i
Package: 6
D->Dai.
0 1 S
0 2 r
2 3 D
2 4 i
3 5 a
5 6 i

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<cstring>
#include<unordered_map>
#include<algorithm> // 用于排序using namespace std;vector< vector<char> > G; // 文法G[S]产生式
unordered_map<char, set<char>> ts; // 终结符及它的first集合
unordered_map<char, set<char>> nts; // 非终结符及它的first集合
map< map<string, char>, string> table; // LR分析表struct C { // 闭包结构vector< vector<char> > project; // 项目集vector< set<char> > outlook; // 展望集unordered_map<char, int> go; // GO函数
};vector<C> c; // 闭包集void show_Symbol() {// 输出非终结符for (unordered_map<char, set<char>>::iterator it = nts.begin(); it != nts.end(); it++) {cout << it->first;}cout << endl;// 输出终结符for (unordered_map<char, set<char>>::iterator it = ts.begin(); it != ts.end(); it++) {cout << it->first;}cout << endl << endl;
}void show_Closure() {// 打印项目集for (unsigned int i = 0; i < c.size(); i++) {cout << "Package: " << i << endl;for (int j = 0; j < c[i].project.size(); j++) {for (int k = 0; k < c[i].project[j].size(); k++) {if (k == 1) cout << "->";if (c[i].project[j][k] == ' ') cout << ".";else cout << c[i].project[j][k];}cout << endl;}}// 修正 Go 函数输出顺序for (unsigned int i = 0; i < c.size(); i++) {vector<pair<char, int>> goItems(c[i].go.begin(), c[i].go.end());// 按照符号顺序进行排序，保证输出顺序正确sort(goItems.begin(), goItems.end(), [](const pair<char, int>& a, const pair<char, int>& b) {return a.first < b.first;});for (auto& it : goItems) {cout << i << " " << it.second << " " << it.first << endl;}}
}void read_G() { // 读取文法G[S]->G'[M]，并区分终结符和非终结符char ch;int i = 0;vector<char> v;char X;set<char> m;nts['M'] = m;while (ch = getchar()) {if (ch == '@') break;if (ch == '\n') {if (!v.empty()) G.push_back(v);v.clear();i = 0;continue;}if (ch != ' ' || ch != '\t') {if (ch == '|') {G.push_back(v);v.clear();i = 3;v.push_back(X);continue;}i++;if (i == 1) {X = ch;nts[ch] = m;}else if (i != 2 && i != 3 && ch != '~') ts[ch] = m;if (i != 2 && i != 3) v.push_back(ch);}}if (G.empty()) exit(0);v.clear();v.push_back('$');v.push_back(G[0][0]);G.insert(G.begin(), v);for (unordered_map<char, set<char>>::iterator it = nts.begin(); it != nts.end(); it++) {unordered_map<char, set<char>>::iterator iter;iter = ts.find(it->first);if (iter != ts.end()) ts.erase(iter);}
}void get_First() {for (auto& it : ts) it.second.insert(it.first); // 终结符的first集合是它自己int r = 0;int change = 1;while (change) {if (r == 20) break;r++;change = 0;for (auto& it : nts) {for (unsigned int i = 0; i < G.size(); i++) {if (G[i][0] == it.first) {unsigned int size = it.second.size();unordered_map<char, set<char>>::iterator iter = ts.find(G[i][1]);if (ts.find(G[i][1]) != ts.end() || G[i][1] == '~') {it.second.insert(G[i][1]);if (it.second.size() > size) change = 1;}else {unsigned int col = 1;while (1) {int flag = 0;unordered_map<char, set<char>>::iterator itt = nts.find(G[i][col]);for (auto& iter : itt->second) {if (iter == '~') flag = 1;else it.second.insert(iter);}if (flag) {col++;if (G[i].size() <= col) {it.second.insert('~');break;}else if (ts.find(G[i][col]) != ts.end()) {it.second.insert(G[i][col]);break;}}else break;}if (it.second.size() > size) change = 1;}}}}}
}void get_Closure() {int i = 0;C clo;c.push_back(clo);while (1) {if (i == c.size()) break;if (i == 0) {vector<char> v(G[0]);v.insert(v.begin() + 1, ' ');c[i].project.push_back(v);set<char> m;m.insert('#');c[i].outlook.push_back(m);}for (unsigned int j = 0; j < c[i].project.size(); j++) {for (unsigned int k = 0; k < c[i].project[j].size(); k++) {if (c[i].project[j][k] == ' ') {if (k == c[i].project[j].size() - 1) break;for (unsigned int x = 0; x < G.size(); x++) {if (G[x][0] == c[i].project[j][k + 1]) {vector<char> v(G[x]);v.insert(v.begin() + 1, ' ');int exist = 0;for (unsigned int y = 0; y < c[i].project.size(); y++) {if (c[i].project[y] == v) {exist = y;break;}}if (exist == 0) c[i].project.push_back(v);set<char> m;bool kong = true;int t = 0;while (kong) {kong = false;if (k + t + 1 == c[i].project[j].size() - 1) {for (auto it : c[i].outlook[j]) m.insert(it);}else if (ts.find(c[i].project[j][k + t + 2]) != ts.end()) {m.insert(c[i].project[j][k + 2 + t]);}else {set<char> m1((nts.find(c[i].project[j][k + 2 + t]))->second);for (auto it : m1) {if (it == '~') {kong = true;t++;}else {m.insert(it);}}}}if (exist) {for (auto it : m) {c[i].outlook[exist].insert(it);}}else c[i].outlook.push_back(m);}}break;}}}for (unsigned int j = 0; j < c[i].project.size(); j++) {for (unsigned int k = 0; k < c[i].project[j].size(); k++) {if (c[i].project[j][k] == ' ') {if (k == c[i].project[j].size() - 1) break;vector<char> new_closure_pro(c[i].project[j]);new_closure_pro[k] = new_closure_pro[k + 1];new_closure_pro[k + 1] = ' ';set<char> new_closure_search(c[i].outlook[j]);bool dif = false;for (unsigned int x = 0; x < c.size(); x++) {for (unsigned int y = 0; y < c[x].project.size(); y++) {dif = false;if (new_closure_pro == c[x].project[y]) {if (c[x].outlook[0].size() != new_closure_search.size()) {dif = true;continue;}auto iter = c[x].outlook[0].begin();for (auto it : new_closure_search) {if (it != *iter) {dif = true;break;}iter++;}if (dif == false) {c[i].go[new_closure_pro[k]] = x;break;}}else dif = true;if (dif == false) break;}if (dif == false) break;}if (c[i].go.count(new_closure_pro[k]) != 0 && dif) {c[c[i].go[new_closure_pro[k]]].project.push_back(new_closure_pro);c[c[i].go[new_closure_pro[k]]].outlook.push_back(new_closure_search);break;}if (dif) {C new_closure;new_closure.project.push_back(new_closure_pro);new_closure.outlook.push_back(new_closure_search);c.push_back(new_closure);c[i].go[new_closure_pro[k]] = c.size() - 1;}}}}i++;}
}int main() {read_G();cout << endl;get_First();get_Closure();show_Closure();return 0;
}

N - 翻译布尔表达式

Description
大家都学过了布尔表达式的翻译，其中有一个拉链－回填技术，这次我们就练习这个技术。Input
输入为一行字符串，例如： a < b or c < d and e < f每个符号都用空格间隔。其中逻辑运算符包含 and 和 or ， 关系运算符包含 < 、> 、<= 、 >= 、== 、 != 。Output假链跳到０，真链跳到１，表达式序号从100开始排。Samples
Sample #1
Input 
Output 
a < b or c < d and e < f
100(j<,a,b,1)
101(j,_,_,102)
102(j<,c,d,104)
103(j,_,_,0)
104(j<,e,f,100)
105(j,_,_,103)

#include<bits/stdc++.h>
using namespace std;string str, x;
int num = 100, True = 1, False = 100;// 序号、真、假
vector<string>v;
int main()
{//cin >> str; 无法输入空格getline(cin, str);str += " #"; // 自己额外加的一个结束标志stringstream strr(str);// while(strr >> x){// 以空格为分割点，将str中的字符（串）赋给xif(x == "or" || x == "#"){if(x == "or") False += 2;else False = 0;int len = v.size();for(int i = 0; i < len - 3; i += 3){printf("%d(j%s,%s,%s,%d)\n", num, v[i+1].c_str(), v[i].c_str(), v[i+2].c_str(), num + 2);// 真链num ++;printf("%d(j,_,_,%d)\n", num, False);// 假链False = num++;}printf("%d(j%s,%s,%s,%d)\n", num, v[len-2].c_str(), v[len - 3].c_str(), v[len - 1].c_str(), True);True = num ++;printf("%d(j,_,_,%d)\n", num, False);num++;v.clear();if(x == "#") break;// 读到结束符停止}else if(x == "and") False += 2;else v.push_back(x);}return 0;
}

O - DAG优化

O - DAG优化
Description
大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。Input
输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 + - * /例如：A=B+COutput通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。PS:保证AB的值不同Samples
Sample #1
Input 
Output 
3
A=B+C
B=B+B
A=C+C
B=B+B
A=C+C

#include<bits/stdc++.h>
using namespace std;
struct nd {char ch;vector<char>val;//附加标记，就是图中节点右侧的变量int left = -1, right = -1;//指针，使用链式前向星思想
}point[200];
int num = 0;//point数组中已使用的下标，每使用一个num++,即num就是DAG图中的行数
string ans[200];//存放重构语句
bool flag[200];//标记重构的语句bool find_val(int id, char ch);//查找id节点中val是否存在ch
int add(char ch);//添加叶子节点
void add_op(char op, char ch, int left, int right);//添加运算符节点
char chose_var(int id);//遍历id节点的val中是否有AB
void save(char ch);//依据要保留的字符ch进行删除无用变量
void dfs(int id);//以id为起点进行dfs遍历int main()
{int t;string sentence;cin >> t;for (int i = 0; i < t; i++) {cin >> sentence;//输入形如a=b+c的语句int left = add(sentence[2]), right = add(sentence[4]);//建立叶子节点add_op(sentence[3], sentence[0], left, right);//建立运算符节点}for (int i = 0; i < num; i++) {//重构代码if (point[i].left != -1 && point[i].right != -1) {//如果不是叶子节点,重构一条语句，分析中有解释为什么要在写一个exist函数ans[i].push_back(chose_var(i));//对于每一个选取的变量都要判断，下面两个变量也一样ans[i].push_back('=');ans[i].push_back(chose_var(point[i].left));ans[i].push_back(point[i].ch);ans[i].push_back(chose_var(point[i].right));}}save('A'), save('B');//因为最后要保留AB所以分别依据A和B进行删除无用变量for (int i = 0; i < num; i++)//结果输出if (flag[i])cout << ans[i] << endl;return 0;
}
bool find_val(int id, char ch) {//查找id节点中val是否存在chfor (char t : point[id].val)//迭代遍历if (t == ch) return true;return false;
}
int add(char ch) {//添加叶子节点for (int i = 0; i < num; i++)//如果节点存在，有叶子节点或者附加标记中有返回节点号if (ch == point[i].ch || find_val(i, ch)) return i;point[num].ch = ch;return num++;
}
void add_op(char op, char ch, int left, int right) {//添加运算符节点for (int i = 0; i < num; i++)//如果有类似运算符节点则在该节点的附加标记中添加变量，如何是类似的分析中解释if (point[i].ch == op && point[i].left == left && point[i].right == right) {point[i].val.push_back(ch); return;}point[num].ch = op;//建立新的运算符节点point[num].val.push_back(ch);point[num].left = left;point[num].right = right;num++;
}
char chose_var(int id) {/*该函数是综合了两种功能，在重构代码是等号两边的变量都能用，不需要在左右子树中写一长串判断了*/if (!point[id].val.size()) return point[id].ch;for (char tt : point[id].val)if (tt == 'A' || tt == 'B') return tt;return point[id].val[0];
}
void save(char ch) {for (int i = num - 1; i >= 0; i--) {//删除无用语句，在分析中有详细解释if (ans[i][0] == ch) {dfs(i);  return;}}
}
void dfs(int id) {//以id为起点进行dfs遍历if (point[id].left != -1 && point[id].right != -1){flag[id] = true;dfs(point[id].left);dfs(point[id].right);}
}

P - 简单的代码生成程序

P - 简单的代码生成程序
Description
通过三地址代码序列生成计算机的目标代码,在生成算法中,对寄存器的使用顺序为:寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用Input
单组输入,给定输出的三地址代码的个数和寄存器的个数.所有的变量为大写字母,寄存器的数量不超过9Output
参照示例格式输出,不需要将最后的寄存器中的值写回内存不再使用变量不用写回内存Samples
Sample #1
Input 
Output 
4 2
T:=A-B
U:=A-C
V:=T+U
W:=V+U
LD R0, A
SUB R0, B
LD R1, A
SUB R1, C
ADD R0, R1
ADD R0, R1

#include <bits/stdc++.h>
using namespace std;
char s[300][300];
char p[300];
int n,m,top;
int get(char ch){for(int i=0;i<m;i++){if(p[i]==ch){return i;}}return -1;
}int use(int x,char ch){for(int i=x;i<n;i++){if(s[i][3]==ch||s[i][5]==ch){return i;}}return n;
}int find(int x){if(top<m) return top++;int ans = -1;int t=-1;for(int i=0;i<m;i++){int k = use(x,p[i]);if(k>ans){ans=k;t=i;}}return t;
}void print1(char ch){if(ch=='+') cout<<"ADD ";else if(ch=='-') cout<<"SUB ";else if(ch=='*') cout<<"MUL ";else if(ch=='\\') cout<<"DIV ";}void print2(char ch){int x = get(ch);if(x!=-1){cout<<"R"<<x<<endl;}else cout<<ch<<endl;
}int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>s[i];}for(int i=0;i<n;i++){int x=get(s[i][3]);if(x==-1){x=find(i);if(p[x]!='\0'&&use(i,p[x])<n){cout<<"ST R"<<x<<", "<<p[x]<<endl;p[x]=NULL;}cout<<"LD R"<<x<<", "<<s[i][3]<<endl;}print1(s[i][4]);cout<<"R"<<x<<", ";print2(s[i][5]);p[x]=s[i][0];}
}