基于C++设计与实现的 LL1 语法分析程序(编译原理)【100012210】

# 编译原理 LL1 语法分析器 编译环境：Microsoft Visual Studio 2019 Windows SDK 版本：10.0 平台工具集：Visual Studio 2019（v142） 语言：C++ ## 1 需求：LL1 语法分析程序的设计与实现。  拓展需求：还能自动够造 LL1 文法的 first 集和 follow 集，为 LL1 文法自动构造预测分析表。 ## 2 核心算法 ①整个程序的模型如图所示：  分析栈、分析表的数据结构详见【3、变量和函数】。 ②first 集的构造 使用深度优先遍历递归的方法，当遍历完所有的非终结符的产生式右部，first 集构造完成。详见注释。   ③follow 集的构造 不能采用深度优先遍历的方法，否则求给出的测试样例【其它文法 1】会无限循环，因为非终结符之间的 follow 集是互相依赖的，因而采用了另一种方法解决了这个问题。就是无限循环求所有非终结符的 follow 集，直到所有的 follow 集都不再增大为止，跳出循环。详见注释。     ④预测分析表的构造算法是利用课本上的算法 4.2  ⑤预测分析控制程序算法是利用课本上的算法：  但是该算法有点小瑕疵，就是最后while循环的出口判断条件有问题，不应该是只是【栈顶文法符号X不为‘$’】，而应为【栈顶文法符号X不为‘$’&&所指向的输入符号a不为‘$’】。 输入形式： 先输入文法的产生式个数，然后输入产生式，该文法必须为LL1文法（消除左递归和左公因子），然后输入1或0，决定是否要进行分析，然后再输入要分析的字符串，该字符串需要用i代表数字，以‘$’结尾。 输入的文法默认第一个输入的产生式的左部为起始符，非终结符仅为一个大写字母，终结符仅为一个小写字母和各种符号，且用~代替 epsilon,且输入的文法必须满足 LL1 文法的条件。输入的要分析的字符串需要用 i 代表数字，以‘$’ 结尾。我认为没有必要把 i 也就是题目中的 num 细化为数字，因为这些操作已经在词法分析中完成了，语法分析只需完成分析类似于这种字符串的输入是否被接受就可以了。 输出形式： 先输出该文法的first集和follow集，再输出该文法的LL1预测分析表，最后输出用户输入的待分析字符串的分析过程， 详见【5、测试样例】所示： ## 3 变量和函数 类： ``` class PF//Production formula,产生式的类 { public: string left;//产生式的左部 set<string> right;//产生式的右部 PF(char s[])//构造函数，确定产生式左部 { left = s; } void insert(char s[])//插入产生式右部的函数 { right.insert(s); } }; ``` 全局变量： ``` vector<PF> PF_vector;//产生式 ``` 使用一个 vector 数组，每个元素为 PF 类的对象，来存放输入的产生式。 ``` map<string, set<char> > first;//first集 map<string, set<char> > follow;//follow集 ``` 使用了map哈希key的类型为string，存放产生式的左部，value的类型为char的set,用来存放对应key的first集和follow集。 ``` vector<map<char, string>> predict_table;//LL1分析表 ``` 使用一个vector数组，每个元素为一个map，该vector的每一个map分别对应PF\_vector中每个产生式的左部的非终结符所在的预测分析表的行，map的key为终结符，value为对应表项中的产生式的右部 ``` vector<char> A;//分析栈 vector<char> B;//剩余串 map<string, int> PF_map;//存储每个非终结符对应的编号，key为非终结符，value为编号 vector<char> letter;//所有的终结符,在构造预测分析表的时候创建完毕 int B_point = 0, input_len = 0;//B_point 为输入串指针，input_len 为输入串长度 ``` 函数： **first 集的构造：** ``` void first_construction() //构造并输出 first 集 void DFS(int x)//为构造 first 集深度优先遍历 PF，递归调用 ``` **follow 集的构造：** ``` void follow_construction()//构造并输出 follow 集 void add_follow(const string& str1, const string& str2)//将 str1 的 follow 集加入到 str2 的 follow 集中 ``` **预测分析表的构造：** ``` void predict_table_construction()//构造并输出 LL1 分析表 bool check_first(const string& str, char ch)//检查 ch 是否属于 str 的 FIRST 集合bool check_follow(const string& str, char ch)//检查 ch 是否属于 str 的 FOLLOW 集合 ``` **预测分析控制程序：** ``` void analyse()//预测分析控制程序 void print_A()//输出分析栈 void print_B()//输出剩余串 ``` **主 函 数 ：** ``` int main() ``` PS：关于每个函数内部详细实现详见 main.cpp 中写好了详细的注释，我几乎对每一步操作的目的和函数的目的都写了详细的注释。 ## 4、详细代码 详见附件源.cpp，在此处不再赘述。 ## 5、测试样例 我写的这个语法分析程序普适性较高，不仅对课本上的算数运算文法能实现求first集和follow集，自动生成预测分析表，以及对字符串进行分析，还对几 乎所有的LL1文法都可以实现，只要输入的文法按照【2 核心算法】中的【输入形式：】的要求即可。在这里我已课本上的算数运算文法为例，其余各种样例输入和输出截图详见附件，其它文法1为follow集循环依赖文法（求follow集不可以用递归求，否则该文法会无限循环），其它文法2为起始符可推空文法（如果不按严格算法4.2构造分析表，也就是作业中把A->~产生式加入到A的follow集所对应的终结符的表项中的做法其实是不准确的，而应把A可以推空的产生式加入到A的follow集所对应的终结符的表项中，否则就会导致无法识别某些字符串的错误，例如其它文法2就是无法识别空串的错误，但该文法确实可以识别空串）。 1、 输入 10 E->TA A->+TA A->-TA A->~ T->FB B->\*FB B->/FB B->~ F->(E) F->i 1 i+i\*(i-i)$ 1 i\*i/(i)$ 1 i/(i+i)-$ 1 i\*\*(i-i)$ 1 \*i-i$ 0  2、 输出：       ## 6、实验总结 LL1 语法分析器实验让我更深入的了解了求 first 集，求 follow 集，构造预测分析表和分析字符串的各种算法，也让我发现了我曾经忽略的部分细节，如样例中其它文法 2 构造分析表时的错误，还提高了我的编程能力，总之让我受益匪浅。