LL语法分析概述（主要介绍LL语法分析的主要功能）
1. 消除产生式左递归
2. 消除产生式左因子
3. 构造FIRST和FOLLOW集合，构造预测分析表
4. 模拟器
5.输出成功语法的语法树，识别错误语法部分。
采用的技术及平台安装（主要介绍采用了什么开发语言，如何部署软件运行环境，简要说明不超过300字）
使用python语言，IDE为PyCharm，部署过程只需安装python对应版本，安装IDE即可。
算法分析（主要介绍采用的算法及数据结构，以及如何用数据结构实现算法，包含：数据结构和算法分析两部分内容，在对应算法分析部分，必须给出示例说明算法）
一．消除左递归
数据结构：文法采用list集合表示，一些用来存放中间结果的量也大量使用list集合。
算法：
（一）首先，要取得文法的左部和右部，此时用到python的re.split(r'::=', G)，G是文法的一个完整产生式，比如E::=E+F,它是一个字符串，通过split将此文法分为两部分，E和E+F，分别是产生式左部和右部。
（二）由于消除左递归是从第一个和第二个进行查找，所以如果第一个产生式含有直接左递归，则会遗漏掉对它进行消除直接左递归的操作，所以第一步对第一个非终结符的产生式进行消除直接左递归的操作，消除左递归的过程在下面会讲到。
（三）对于提取的右部，由于他们基本上是由‘|’符号分开，比如E|E+F|E-F，也以字符串形式表示，所以运用re.split(r'\|'，ex)正则表达式函数将右部按照|一个一个分开，得到E，E+F，E-F，这样，就可以比较两组产生式右部是否具有Ai->AjR的形式，进行相应替换。
（四）替换操作之后，就是消除直接左递归了，由于进行消除直接左递归也是类似于替换和重组的过程，所以在这里定义了两个list，分别是Aa和b，分别表示第一个字符是本非终结符的集合和第一个字符不是本非终结符的集合，然后按照规则进行替换重组，组合成一个个字符串，比如，”E::=TE'”，“E'::=+TE'|ε”，删除文法中有直接左递归的这个产生式，然后插入新生成的两个产生式。
（五）重复上述过程，直到循环到最后一个产生式。
二．消除左因子
数据结构：list
算法：
（一）同样，需要提取左部和右部，方法同上一个算法一样。对于提取到的右部，它们以字符串形式表示，用多层循环的方法求右部的最长公共前缀，第一个和第二个比较，和第三个直到第n个，将得到的当前这一组的最长公共前缀和存储最长公共前缀的中间变量比较，如果大于，则新求出的前缀作为当前的最长公共前缀。
（二）求得最长公共前缀后,定义了两个list集合，b和r，分别表示具有公共前缀的右部和不具有公共前缀的右部，用于替换和重组。
（三）组合成两个新到的string，将文法（用list集合表示）中有公共前缀的那个产生式删去，在其后插入这两个新的产生式。
（四）重复这一过程，直到将文法中的左因子全部消去。
三．求非终结符的first集合
数据结构：，first集合和follow集合用字典来存储，比如F作为key值，{+，-}作为value值,它是一个list集合表示F的first集合。
算法：
（一）提取产生式左部和右部，倒序对产生式进行循环，在循环时进行三个条件的判断，有一点要说明，比如条件三，要将已经求得的first（A）加入到first（B）时，由于采用字典来表示，所以要访问A的fist集合直接通过A这个key值就可以获取。
（二）在这一过程中，由于存在id和num这样，由多个小写字母构成的终结符，需要特别的对他们进行识别，这里采用预先定义的方法，在Note.txt文件中表明了这类终结符，通过文件流提取他们，作为string，在程序中进行判断。
（三）现在说明三个条件，条件一和条件二，简单的将相应内容加入即可，对于条件三，首先需要在字符串头部尾部加上ε，由于采用字典方法存储first集合，所以在取文法的first集合时直接按key值取即可，然后进行相应判断。
四．求任意文法序列的first集合
数据结构：list集合存储求得的first结果
算法：
（一）由于非终结符的first以求得，而终结符的first集合是他本身，所以对于任意文法序列，按照求任意文法序列的first集合的算法的判断条件，寻找第一个具有其first集合不含ε的文法符号，将结果一字符形式存入结果list集合中。
五．求follow集合
数据结构：follow集合用字典来存储，比如F作为key值，{+，-}作为value值,它是一个list集合表示F的follow集合
算法：
（一） 求follow集合的过程类似于求first集合，定义好字典follow后，求每个非终结符的follow集合元素集fl（list数据类型）。
（二）对非终结符正序循环，再循环体中，对三个条件进行判断。对于条件一，简单处理即可。对于条件二，找到A->aBb，后，因为这一步和条件三的判断条件有重合之处，所以先判断有没有ε，若有，则取follow（A）加入fl，然后直接取first（b）,对first（b）循环加入fl，跳过ε，这就完成条件二和条件三一部分内容的判断。
（三）对于条件三，找到A->aB，follow（A）加入fl。最后在三个条件都判断完成后，建立非终结符和fl的key-value联系，即将其以字典形式存储起来。
六．构造预测分析表
数据结构：预测分析表table用两层的字典来表示，比如E这一行的预测分析表，E：[( : TE’, - : TE’, id : TE’]，E是key，list作为value存储了三个字典元素，这三个元素表示为（ : TE’, (是key，TE’是value。
算法：
（一）对文法的每个产生式进行循环，在循环体内，执行对于预测分析表构造算法中条件二，三的判断，并执行相应操作，对于条件二，对于first（a）的每个终结符b，加入a到table[A,b]中。
（二）对于条件三，如果ε在first（a）中，则取follow（A），对于他的每一个终结符b，加入a到table[A,b]中。
（三）由于只对在判断过程中涉及到的终结符添加项到表中，所以会出现有的终结符不在预测分析表的纵坐标上，不过这表明这一列的表都填error，不影响程序的正确性。
七．驱动器
数据结构:运算符栈采用list集合来表示，由于python将stack的特性加入list，所以list本质上也可是stack。定义error这一字典，存储不能正确识别的字符。
算法：
（一）初始化符号栈，当栈和输入序列w都不指向‘#’，循环下述内容、
（二） 如果栈顶元素是终结符，且等于w的当前字符，则弹栈，将w的下标后退一位。
（三）如果栈顶元素是终结符，查预测分析表，即table[x,a]，弹栈，将对应产生式右部倒序压栈。
（四）不满足上述条件的其他情况都视作错误情况。
（五）值得注意的是，当栈顶元素是终结符时，需要判断它是不是特殊的终结符，如id，num等等。在将产生式右部倒序压栈时，需要对带有单引号的非终结符（他们是在消除左递归和提取左因子时出现的）进行特殊处理，不要将EF’倒序为’FE,而应该是F’E.
流程图（绘制并说明算法流程）
程序运行截图（根据实验指导书第3节提供的内容及要求显示输出结果，并提供对应交互信息）
1.测试用例：
L::=E;L|!
E::=E+T|E-T|T
T::=T*F|T/F|TmodF|F
F::=(E)|id|num
2．测试用例二
3,测试用例3
程序模块说明
(6)程序分析（主要介绍编程中出现的错误以及修改的说明以及实验心得）
1.正则表达式在处理字符串时的灵活性很大。
2. python数据结构设计上的简化，使得编程者不用纠结太多数据结构的选择，以及他对于类型的放宽，使得编程者能将更多的精力放在算法和业务上，而不是程序实现的复杂性上。
3.字典：集合（字典）的这一组合数据结构，是矩阵的变种，他不是通过数字坐标来访问，而是两个key值，这在某些程序设计中会提供给编程者更多的方便。
4.python list去重可以通过简单的一行代码解决。
网友评论