LR语法分析概述
一．计算识别活前缀
二．计算LR项目集合识别活前缀的DFA
三．判断是不是合法LR(0)文法
四．构造SLR分析表
五．LR分析
采用的技术及平台安装
使用python语言，IDE为PyCharm，部署过程只需安装python对应版本，安装IDE即可。
算法分析
一．计算识别活前缀
数据结构：list数据结构，用来存储LR项目
算法：采用for循环遍历的方法，对于每一个产生式添加‘.’，将结果添加到用于存储LR项目的list数据结构中。
二．计算LR项目集合识别活前缀的DFA
数据结构：定义了两个字典数据结构C和DTran，分别用来存储产生的DFA项目和状态转移关系，其中C，key为数字，代表状态编号，value为list，表示LR项目的集合；DTran中key为数字，表示状态编号，valu为一个list，而list中记录了多个key-value值，表示经过那个文法符号到达哪一个状态。
算法：
1. 对所有未标记的状态（这里采用比较的方法确定是否标记），求出当前状态可以接受的字符有哪些，比如E->.E-T的可接受字符为非终结符E，再有可以接受字符的情况下，调用求下一状态转移的函数closure和goto，类似词法分析中的最小子集法的步骤，得出状态转移。
2. 然后对求得的项目集与已标记的状态集比较，看是否是新的状态，若是，则加入状态集C，若不是，则标记为旧状态
3.在求完后记录状态转移。
三．构造first集合
数据结构：，first集合和follow集合用字典来存储，比如F作为key值，{+，-}作为value值,它是一个list集合表示F的first集合。
算法：
1.提取产生式左部和右部，倒序对产生式进行循环，在循环时进行三个条件的判断，有一点要说明，比如条件三，要将已经求得的first（A）加入到first（B）时，由于采用字典来表示，所以要访问A的fist集合直接通过A这个key值就可以获取。
2.在这一过程中，由于存在id和num这样，由多个小写字母构成的终结符，需要特别的对他们进行识别，这里采用预先定义的方法，在Note.txt文件中表明了这类终结符，通过文件流提取他们，作为string，在程序中进行判断。
3. 现在说明三个条件，条件一和条件二，简单的将相应内容加入即可，对于条件三，首先需要在字符串头部尾部加上ε，由于采用字典方法存储first集合，所以在取文法的first集合时直接按key值取即可，然后进行相应判断。
四．构造follow集合
数据结构：follow集合用字典来存储，比如F作为key值，{+，-}作为value值,它是一个list集合表示F的follow集合
算法：
1. 求follow集合的过程类似于求first集合，定义好字典follow后，求每个非终结符的follow集合元素集fl（list数据类型）。
2. 对非终结符正序循环，再循环体中，对三个条件进行判断。对于条件一，简单处理即可。对于条件二，找到A->aBb，后，因为这一步和条件三的判断条件有重合之处，所以先判断有没有ε，若有，则取follow（A）加入fl，然后直接取first（b）,对first（b）循环加入fl，跳过ε，这就完成条件二和条件三一部分内容的判断。
3. 对于条件三，找到A->aB，follow（A）加入fl。最后在三个条件都判断完成后，建立非终结符和fl的key-value联系，即将其以字典形式存储起来。
五．判断是不是合法LR(0)文法
数据结构：使用先前定义的字典结构C，以及list类型的文法，字典类型的follow集合。
算法：对C中的所有的LR项目，采用循环比较的方法，即第一个和第二个，第三个，第n个比较，观察两两之间是移进/归约冲突还是归约/归约冲突，如果是第一种冲突，则比较’.’后的第一个字符和follow(B)（B是第二个LR项目的文法左部）是否有交集，若是第二种冲突，比较follow(A) ，follow(B)是否有交集。在没有交集的情况下，才能说明该文法是合法的LR文法，否则不是。
六．构造SLR分析表
数据结构：使用字典C，字典DTran。Arow 和 grow表示action和goto一行的内容集合list。
算法：
1.构造一个方便进行坐标访问的文法，用list，为后续计算服务。因为后续构造需要用到使用坐标来定位产生式的文法。
2. 对每一个状态转移，如果纵坐标是非终结符，action[I,x]=Sj,如果不是，goto[I,x]=j
3.对于每个属于本状态的可规约项目，如果是初态的产生式，则action[I,#]=acc，如果不是，则按照规则对action和goto进行填写，即添加相应的内容到arow和grow中。
4. 将arow和grow作为本状态的有意义的内容
七．LR分析
数据结构：定义一个list表示stack栈，存储三大格局中的栈内容。使用action和go。
算法：
1. #判断w的当前输入是否是特殊字符，这是因为存在id，mod，num等多个字符表示一个终结符的情况。
2. 通过设定根据w的当前字符和栈顶元素查找action表的情况，将情况分为4种，分别是移进，归约，成功，出错。
3.在归约条件中，注意计算栈顶元素时考虑id，num这种终结符。
4. 按照相应条件设置操作，各部分操作不复杂，在移进时，将下一状态当前输入字符进栈；在归约时，弹出栈顶相应个数的字符，暴露出当前栈的栈顶状态，将产生式左部符号进栈
，新栈顶元素进栈。
流程图（绘制并说明算法流程）
程序运行截图（根据实验指导书第3节提供的内容及要求显示输出结果，并提供对应交互信息）
测试用例1：输入abbcde
测试用例2：输入abcde
测试用例3：id+id*id
程序模块说明
程序分析（主要介绍编程中出现的错误以及修改的说明以及实验心得）
1.由于first和follow集合与自上而下文法分析中的用法一样，所以直接迁移代码，体会到函数接口的重要性，因为要想使用上一个实验的first和follow集合，要保证函数参数的一致。
2.经过三次实验的锻炼，对于数据结构的设计，算法流程的设计，以及结合编程语言自身的特点进行编程上，更加的灵活和得心应手了，举个例子，first和follow采用字典是非常合适的存储方式，对于后续直接根据文法的非终结符取其first集合，非常方便。还有，action和goto表，采用字典方式存储，可以达到只存储有意义的数据，不浪费空间。
3. python函数的返回值可以是多个，按照下标来取即可，比如构造移进归约分析表时，函数返回action和goto两个字典，可以通过下标0,1来取。
4．加深了对于上述各个算法的理解。
