编译原理SLR（1）⽂法的C++实现（基于SLR（1）分析法的语法制导翻译及中间代码⽣成程。。。
本⽂参考⾃:
程序功能描述
完成以下描述赋值语句 SLR(1)⽂法语法制导⽣成中间代码四元式的过程。
G[A]:
A→V=E
E→E+T∣E-T∣T
T→T*F∣T/F∣F
F→(E)∣i
V→i
[设计说明] 终结符号i为⽤户定义的简单变量，即标识符的定义。
[设计要求]
（1）构造⽂法的SLR(1)分析表，设计语法制导翻译过程，给出每⼀产⽣式对应的语义动作；售后服务体系
（2）设计中间代码四元式的结构；
（3）输⼊串应是词法分析的输出⼆元式序列，即某赋值语句“专题1”的输出结果，输出为赋值语句的四元式序列中间⽂件；
设计两个测试⽤例（尽可能完备），并给出程序执⾏结果四元式序列。
主要数据结构描述
在实验中主要使⽤结构体进⾏各类属性的封装。此外，还⽤到了stack和list的结构，其中stack主要由数组进⾏简易实现，便于输出栈内内容；list使⽤C++ STL中的list进⾏动态的添加。以下对每⼀部分进⾏详细说明。
此处使⽤ntence结构体对于项⽬集族中的每个产⽣式的属性进⾏封装。finish表⽰该产⽣式是否完成规约，即点操作是否进⾏完毕；tag 即⽤来表⽰当前点的位置，因产⽣式包含有左部和->符号，故从3开始计数；string类的str⽤于存储产⽣式的字符串。
typedef struct
粽子要蒸多久{
int finish = 0; //是否结束
int tag = 3; //当前圆点的位置
string str;
}ntence;
此处⽤act结构体对构造的ACTION表进⾏存储。在实验中，我并没有使⽤⼆维数组进⾏ACTION表的存储，⽽是选⽤了⼀维的结构体：I代表输⼊的⽬前的状态，Vt代表输⼊的终结符号，tag⽤于表⽰是r类还是s类，action⽤于记录对应的r类的产⽣式标号或s类状态标号。 typedef struct
{
int I; //当前状态
char Vt; //终结符号
char tag; //r||s
中药木香int action; //动作
}act;
同上，此处使⽤结构体go对GOTO表进⾏存储。I表⽰输出的当前状态，Vn表⽰输⼊的⾮终结符，next_I表⽰GOTO的转移结果，形如GOTO(I, Vn) = next_I。
typedef struct
{
int I; //当前状态
char Vn; //⾮终结符
int next_I; //转移状态
}go;
此处使⽤I进⾏构造项⽬集族时状态的存储。number对应于该项⽬的序号，如I0/I1等；l则为list<ntence>类型，⽤于存储该状态中的产⽣式。
typedef struct
}I; //状态
此处使⽤siyuanshi进⾏四元式的存储，形同四元式：(op, arg1, arg2, result)。在此不再赘述。
typedef struct
{
char op;
char arg1;
char arg2;
char result;
}siyuanshi;
此处使⽤var进⾏符号表的存储。在构造四元式的过程中，需要对于上⼀次的操作中新⽣成的结果进⾏记录，以便⽣成新的四元式时作为参数加⼊其中；故结构体中的name代表某⼀运算结果的变量名，如A/B/C/D；string类的value表⽰该变量对应的算术表达式（属性）。 typedef struct
{
char name;
string value; //place
}var; //变量
以下是⼀些变量的定义。在这些过程中⽤到了⼤量的list：⾸先进⾏状态集的定义，以list的形式对状态进⾏存储；之后是list-char的FIRST 与FOLLOW集的定义；之后是list形式的ACTION表和GOTO表的定义，以及list-char的Vn/Vt集。最后，input⽤来存储输⼊串，在分析过程中也会使⽤input来主要进⾏分析。
list<I> DFA; //状态集
list<char> *First; //FIRST集
list<char> *Follow; //FOLLOW集
list<act> ACTION; //ACTION[i][j]
list<go> GOTO; //GO[i][j]
list<char> Vt; //终结符号集
list<char> Vn; //⾮终结符号集
char input[100];
下⾯是分析栈、符号栈以及其属性栈的定义，分别存储状态号、符号以及其代表的属性，并且设⽴栈顶指针。下⾯使⽤list结构进⾏四元式的存储、记录可以产⽣四元式的产⽣式标号以及变量表中变量的存储。最后，在G[]数组中，进⾏⽂法的定义。本实验为⾃动造表，故此处可修改⽂法，仅作细微改动即可。
int S[100]; //分析栈
int S_top = 0; //分析栈栈顶
char T[100]; //符号栈 栈顶与分析栈总相同
string value[100]; //存储符号的属性
list<siyuanshi> L_sys; //四元式
list<int> sys; //产⽣四元式的状态集
list<var> V; //变量表
int result_count = 0;
string G[11] = { "S->A", "A->V=E","E->E+T","E->E-T","E->T","T->T*F","T->T/F","T->F","F->(E)","F->i","V->i" };
程序结构描述：
整个程序较为庞⼤，⾃动构造⽂法分析所需的表，包括Vt/Vn/FIRST/FOLLOW/ACTION/ GOTO/变量表，之后进⾏SLR(1)分析，并且构造四元式。在这⾥进⾏详细说明：
完成整个程序的思路是：
->读取⽂件(获取输⼊的实验⼀运⾏结果、得到表达式)
摸鱼儿辛弃疾->扫描⽂法(构建终结符号、⾮终结符号集、First/Follow集)
->造表(构造项⽬集族、构造ACTION/GOTO、设置四元式)
->SLR分析(判断是否可以被分析程序接受、⽣成四元式)
扫描⽂法：scan()将⽂法数组G[]中的string字符串进⾏扫描，构造终结符号集和⾮终结符号集；之后按照SLR(1)⽂法中FIRST集和FOLLOW集的构造⽅法进⾏这两个集合的构造。在构造FIRST集时，⽤到了find函数，⽤来不断地递归查找产⽣式⾸符号为⾮终结符号的产⽣式，以构造FIRST集；在构造FOLLOW集时，使⽤到了findVn函数，⽤来返回指定的⾮终结符对应的标号，以进⾏FOLLOW集的计算。同时，通过不断的循环、加⼊，当所有⾮终结符的FOLLOW集总⼤⼩不变时，跳出循环，构造完成。⾄此，造表前的准备⼯作全部完成，接下来进⼊造表阶段。
造表：table()完成整个项⽬集族的⽣成以及ACTION/GOTO的构造，以及在造表过程中对于四元式的标注，也是个⼈认为整个程序中最难的部分。
⾸先，进⾏初始设定：添加⽂法的起始符号对应的产⽣式，⽤以从初态进⾏迭代；之后将该产⽣式(点还处在最开始的部位tag=3, 尚未进⼊规约状态finish=0)加⼊第⼀个状态I0中，接下来进⾏⼀波循环操
作：⾸先对于当前所有的项⽬集族进⾏闭包操作，该功能被封装在闭包函数closure()中（函数中对于每⼀个点操作的⾮终结符均进⾏闭包操作，加⼊该状态中，最终返回经过闭包操作的该状态）；之后对于当前状态的每⼀条待移进的产⽣式分别进⾏移进操作，并添加为新的状态，等待循环到该状态时的闭包操作。在移进过程中，对于不是规约的（即尚可移进的）产⽣式，若点操作为⾮终结符，置GOTO(当前状态, ⾮终结符) = 新状态号；若为终结符，则置ACTION(当前状态，终结符号) = s+新状态号。若存在移进时的相同符号，则加⼊同⼀状态中，不再另设新状态。之后即为对于新状态的加⼊判断：若新状态的闭包操作closure()已经在已形成的项⽬集族中出现了，则不再添加这个新状态，并且修改对应的ACTION或者GOTO（⼀个pop()操作+⼀个push()操作）；否则添加。对于需要规约的产⽣式，⾸先对其进⾏判断是否可以产⽣四元式：若可以，则进⾏记录，以便之后判断；否则不进⾏记录。⾄此，造表结束，接下来正式进⼊分析阶段。
SLR分析：SLR()完成最终整个SLR(1)⽂法的分析任务，也包括分析过程中完成的四元式构建。在分析过程起始时，⾸先将状态I0压⼊栈中，分析开始：若ACTION(栈顶，当前符号)不是acc（在程序中为r0），则开始循环：如果是err（在程序中使⽤0代替），报错；否则如果是sj，状态栈、符号栈、属性栈均压栈，读取下⼀个符号；如果是ri，则通过需要规约第i条产⽣式，对于三个栈，执⾏第i条产⽣式右部的符号数次pop()操作，同时更新属性栈，⽤以后续的四元式⽣成⼯作；在⽣成四元式时，⾸先判断正在规约的产⽣式是否可以产⽣四元式，同时确定四元式的op，其次判断两个参数（arg1，arg2）
是否为变量or变量组成的表达式。如果是表达式，则查找之前的符号表，进⾏代替操作。若中间不报错⽽跳出循环，则成功匹配。⾄此，按照事先约定好的输出格式进⾏输出，分析任务完成。
程序测试：
测试⽤例
在本程序中，使⽤⽂件进⾏读取表达式的操作。测试输⼊串放在中，测试⽤例如下：
测试⽤例1：
12,<i>
32,<=>
12,<a>
23,<*>
28,<(>
12,<b>
创意早餐
21,<+>
12,<c>
29,<)>
33,</>
12,<d>
测试⽤例2：
12,<r>
32,<=>
28,<(>
12,<a>
21,<+>
12,<e>
29,<)>
33,</>
12,<b>
23,<*>
28,<(>
12,<c>
22,<->
12,<d>
29,<)>
测试结果
测试1：
读⼊实验⼀结果：12,<i>
32,<=>
12,<a>
23,<*>
28,<(>
12,<b>
21,<+>
12,<c>
29,<)>
33,</>
12,<d>
输⼊串为：i=a*(b+c)/d#
终结符号集：=+-*/()i#
⾮终结符号集：SAVETF FIRST
S i
A i
V i
E ( i
T ( i
F ( i
FOLLOW
S #
A #
V =
E # + - )
T # + - * / )
F # + - * / )
状态0：
S->·A
A->·V=E
检验科个人总结
V->·i
状态1：
S->A·
V->i·
状态4： A->V=·E E->·E+T E->·E-T E->·T T->·T*F T->·T/F T->·F F->·(E) F->·i
状态5： A->V=E· E->E·+T E->E·-T 状态6： E->T· T->T·*F T->T·/F 状态7： T->F·
金锁记作者
状态8： F->(·E) E->·E+T E->·E-T E->·T T->·T*F T->·T/F T->·F F->·(E) F->·i
状态9： F->i·
状态10： E->E+·T T->·T*F T->·T/F T->·F F->·(E) F->·i
状态11： E->E-·T T->·T*F T->·T/F T->·F F->·(E) F->·i
状态12： T->T*·F F->·(E) F->·i
轻轻近义词状态13： T->T/·F F->·(E) F->·i
状态14： F->(E·) E->E·+T E->E·-T 状态15： E->E+T· T->T·*F
