type
status
date
slug
summary
tags
category
icon
password
文法与语法
语言的定义（这里怎么TM又有个语言啊，上面词法也有一个语言）是语法规则加上语义规则
语法的基本概念
- 字母表：跟词法分析中的字母表是一样的
- 词汇：对应着词法分析中的语言中的一个元素，也就是定义在字母表上的串
- 词法规则：就是降格的文法规则，通常是正则表达式
只有当一个词汇满足了词法规则，他才是一个有效的词汇（也就是当一个词汇是满足了当前程序语言规定的某个正则表达式的时候，他才是一个有效的词汇）
- 语法规则：是一个词汇的序列（对一些确定的词汇构成的一个词汇串就是一个句子），抽象出了句子的结构
语法的三种表示方法：
- 自然语言描述：没必要看，zeq上课也没讲
- 形式化描述：就是书上讲的文法
- 转换图/语法图：也就是一个自动机，这个自动机的字母表（也就是状态转换条件）是当前语言的有效词汇罢了
有一些文法的状态图不是很好看出来（如左递归的文法等）
关于语法的BNF形式化描述相关概念如下图：
终结符和非终结符不多做赘述，就是一个不可分解，一个还能继续分解
产生式，就是文法的某一条规则（非终结符->（终结符|非终结符）*）
还有一些概念，可能会遇到：
要记住这里的Vt还有Vn是代表终结符和非终结符（记忆方法：非终结符的非是not，所以是Vn）
上面的这个文法的定义要了解（文法是一个四元式，包含了终结符、非终结符、产生式、开始符号）
文法是对语法的一种形式化描述（但是在zeq这里没有特别区别文法和语法）
一些文法的表示法
如上面的两张图，希腊字母一般是代表终结符和非终结符组成的串，小写字母一般是终结符，大写字母一般是非终结符，一般默认第一个产生式的左边的非终结符就是开始符号
上例中由于阿拉法是在产生式左侧的，所以一定要能做推导，也就是阿拉法至少要含有一个非终结符
四种文法
- 0型文法：就是对产生式左右两侧不做任何限制，只要产生式左侧含有非终结符即可
- 1型文法：在0型文法的基础上规定产生式左边串的符号个数要小于右边串符号的个数，所以0型文法包含1型文法
注意：根据1型文法的定义，空串产生式不是1型文法，但是这里将开始符号的空串产生式当做特例，并且开始符号不能出现在产生式的右侧，这个时候非终结符推导出空串是也是一个特例，也是一种1型文法
- 2型文法：要求产生式的左边只能有一个非终结符，产生式左边不做要求（认为2型文法一定是1型文法，所以如果出现文法改造的话尽量不要将开始符号放在产生式的右侧）
- 3型文法：在2型文法的基础上（也就是产生式的左边只能有一个非终结符），要求产生式右边必须以终结符开始
最左推导和最右推导
- 最左推导：在将句型推导成句子的过程中，每次都对最左边的非终结符进行推导
- 最右推导：在将句型推导成句子的过程中，每次都对最右边的非终结符进行推导
- 最右推导也被称为规范推导（最右推导被称为规范推导主要是因为在自底向上的分析中总是最左规约，生成的语法树就相当于是把文法做最右推导得到的语法树，所以最左规约也被称为规范规约）
这个时候就出现了两种推导情况，也就是文法的二义性
文法的句子和句型
- 句子是有终结符组成的，而句型是由非终结符或终结符组成的
- 句型是句子的一种抽象
- 句子一定是句型，但是句型不一定是一个句子
也就是下图所说的区别：
文法代表的语言：文法产生的所有的句子（全部由非终结符组成）的集合
求文法推导出的语言：从下向开始符号推导即可
求一个上下文有关文法推导出的语言（需要从上向下进行推导）
具体过程如下：
文法的等价
当两个文法导出的所有句子的集合（文法导出的语言）是相同的，那么这两个文法是等价的
文法的推导树
注意上面的句子有两棵推导树，所以这个文法是有二义性的，也就是下图的说明（注意这里说的是句子而不是句型）：
每一个节点的直接子节点从左向右排列就对应着文法的一个产生式
推导树的相关概念（推导树是在做文法推导的时候产生的，推导树也称为语法树，想想语法分析的时候，那个时候就是在做文法的推导，然后根据推导来构建树，构建出来的树就是语法树。如果我们进一步将我们通过文法推导得到的语法树进行简化的话，就比如说将操作符上提等，这个时候出来的树是抽象语法树，而不是语法树，语法树就是每一个非终结符和终结符都对应着一个节点的）。按道理来说语法树的创建过程中，每个非终结符和终结符都是一个节点，但是有的时候会直接将子节点提升（在做题的时候就不提升了，但是实验中其实一直都有用子节点提升）
- 推导树的边缘：推导树的所有叶节点从左向右链接
语言的抽象（实际上就是将正则表达式转换为文法）
- 正则表达式中的+号：转换为cC|c
- 正则表达式中的*号：转换为cC|空
- 正则表达式中的链接：转换为AB（需要将A和B推导出的结果链接时）
tips：当推导出的语言中有一些字母是有关系的（如终结符a，b都必须出现相同次数等），这个时候通常在文法的一个产生式中进行处理
这些题可以再做一做，在文法语法的那一个ppt的最后
自上而下的语法分析
语法分析总论
- 语法分析的目标：构建输入程序的语法树（或者构建一个抽象语法树）
- 语法描述的工具：语法分析是采用上下文无关文法（就是产生式的左边只有一个非终结符）
- 语法分析：根据给定的上下文无关文法，判断当前的输入串（输入程序）是否是给定文法的一个句子。如果是，就构建出该程序的语法树；如果不是就拒绝该串
自上而下的语法分析
自上而下：从文法的开始符号出发，猜测程序（也就是输入串）的推导序列
自上而下语法分析的过程
将每一条文法的每一个产生式都当成是当前节点（每个结点都是一个句型，注意单一的非终结符号也是一个句型）的出边，这样从开始符号开始，就可以构建一个图（经过处理可以成为有限自动机，因为这个时候还没有自动机的字母表，只是对文法产生式的枚举，成为一个自动机之后，当前的语法分析方法就变成了预测分析法，没有处理就单纯的对图进行遍历的话就是递归下降分析法），所以语法分析实际上就是对这一张图的遍历，直到找到跟当前输入串匹配的节点，也就是：
自上而下语法分析的三种方法
广度搜索法（了解即可）
对图不做任何处理，直接从开始符号开始（第一步操作是先将开始符号入队），进行广度优先搜索，在图中搜索当前的输入串
广度优先算法的问题
- 效率低下，时间空间资源消耗大（就像ACM的时候说的，广度优先搜索容易爆栈）
主要原因是因为广度优先搜索查找所有分支，但是实际上正确的分支只有一条，即广度优先算法要检查很多不匹配的句型。文法的推导常常会导致句型中含有多个非终结符，这个时候的分支数就是每一个非终结符产生式的数量之和，也就是高分支因子
广度优先算法的改进（这个是算法本身的问题）
- 排除不可能句型：根据当前的输入串去舍弃一些分支（当前的句型前缀如果跟当前输入串的前缀不同，那么这个句型就可以舍弃，这里的前缀指的是最前面的一个终结符串）
- 高分支因子：每次推导的时候只推导句型中的一个非终结符（采用最左推导），而不是将所有非终结符的排列组合进行枚举（分支数量是指数级增长的）
这样的算法称为最左广度优先算法
仍然存在的问题（这个就是文法本身的问题了）
- 左递归：虽然最终还是能找到输入串（对比递归下降，如果递归下降分析的文法中存在左递归就会导致死递归，就没办法找到输入串了），但是左递归会导致广度优先算法的问题再次暴露出来，不可能句型没办法排除（因为没有终结符串前缀），分支因子也不会减少（每次推导并不会减少非终结符的数量），最终导致效率还是很低下
- 公共左因子/空串产生式（注意在推导某个非终结符时，该终结符的空串产生式也是一个分支，这个分支的句型就是在当前句型的基础上去掉这个非终结符 ）：最终也能找到输入串（递归下降分析法如果存在公共左因子或者空串产生式的话仍然能找到输入串并且没什么影响），但是导致没办法随意排除句型（也就是不能立即判断能否舍弃某个分支，并且如果是公共左因子的情况检查的终结符串前缀的非终结符数量也可能需要调整，因为有的时候仅看一个终结符是没办法明确舍弃哪个分支的，此时就需要更多的输入串信息），下图是一个空串产生式影响的例子：
此时就会出现之前的问题，也就是一直在检查不可能的句型
（最左）广度优先算法的总结
- 时间复杂度（检查不需要的分支且需要检查的分支很多）和空间复杂度（队列）都很高
算法本身的问题没办法处理，但是文法是可以改造的
文法改造（关于自上而下分析）
- 公共左因子（注意公共左因子是一个符号串，也就是说非终结符也是算公共左因子的。并且看公共左因子的时候不对产生式右边的句型进行推导）：消除（提取）公共左因子，如下例：
具体的消除算法如下（即一直提取公共左因子直到某条文法的各个产生式没有公共左因子）：
- 左递归：消除直接、间接左递归，直接左递归的消除如下例：
具体的直接左递归消除算法如下（消除左递归最关键的是要知道文法代表的语言是什么，也就是看明白语言应该以什么开始，什么部分在重复，如上面的直接左递归的例子，要能看出来文法p代表的语言是由β开头后面跟上个阿拉法的符号串，说明语言是以β开始，并且重复部分是阿拉法，这个时候就可以将β提前，也就是消除后的第一条文法，然后在实现\个阿拉法的文法，最后链接在一起即可）：
消除间接左递归如下例（只要通过文法将间接左递归化成直接左递归然后按照直接左递归的方法来处理即可，具体化成哪个非终结符的直接左递归是没有影响的，并且被带入的文法在处理之后的文法中是不需要写出的，因为在消除左递归带入的时候就已经含有该文法的信息了，如下图中S对应的文法，但是下图中S由于是开始符号，所以保留）：
一个更复杂的消除间接左递归的例子（这个例子就是把被带入的文法全部去掉了）：
注意消除左递归的时候消除后的文法要符合规范（产生式中不能存在括号）
递归下降分析法（最左深度搜索法）
最左是代表每次递归的时候都做最左推导，也就是调用最左非终结符对应的分析函数
优点
- 空间小：没有队列
- 实现简单：递归
缺点
- 需要回溯
与广度优先搜索法的区别
- 广度优先搜索法适用于所有文法（出现左递归和公共左因子的时候只不过是需要遍历的分支数多一点），但是最左深度搜索法没办法处理左递归（会导致死递归）
- 广度和深度的时间复杂度都是指数级的（因为理论上需要遍历的图是一样的），但是广度因为需要使用队列，空间复杂度指数级增长，但是深度通过递归解决了这个问题
预测分析法
预测分析法也是最左推导，因为每次都是比较前缀的（当前输入串的前缀必须是出现在左边第一个非终结符的前缀）
预测分析法可以通过自动机实现，但是有点麻烦
无论是广度优先搜索还是深度优先搜索都需要回溯（广度的队列还有深度的递归函数返回都是需要回溯的体现），而回溯就说明了当前的算法其实是在试错的，也就是时间复杂度比较高。所以不希望回溯，也就出现了预测算法
预测算法的核心思想：根据输入的串来选择（预测）要走的分支
由上面的说明知道，预测分析法的时间复杂度更低（因为每次选择都是走正确的路），但是要求也更多（文法需要能预测，导致其没办法处理所有的文法，如向前搜索一个的预测分析法就只适用于LL1以上的文法。实际上如果向前搜索的符号越多就会使得越多的文法能够预测）
这个表还不是LL1预测分析表，但是是雏形，最上面一行表示当前待识别的tok（也就是当前输入串的中还未识别的第一个tok）
小知识：LL1中第一个L代表从左向右扫描输入串，第二个L表示使用最左推导，数字1表示向前看一个字符
可以对产生式进行编号，然后填预测分析表的时候就只要填写产生式的需要即可
小知识：输入串的结束符号为#或者$
预测分析的过程:：根据输入串的k个字符（k就是LLk中的k）进行查表，然后确定应该选用哪一个产生式来进行推导（查到的产生式序号）
这里说的逆序压栈的意思就是#是栈底，所以需要将产生式逆序之后压入栈，这个时候匹配的终结符就在栈顶了，就可以跟输入串中的符号进行匹配消除
这里也只是预测分析法的一种情况，如果终结符的第一个符号不是终结符的话，那么就需要去求该非终结符的first集，然后该产生式接收所有first集中的字符（这也是为什么消除了左递归和公共左因子但是文法还是不是LL1文法的一个原因，因为消除公共左因子的时候并不对非终结符进行推导，但是预测分析的时候就需要对非终结符进行推导，就是求first集）
预测分析语法分析器拒绝输入串的情况（错误处理）
- 语法分析器维护的栈内已经只有结束符了，但是输入串还未识别完（就是自动机走到终态，但是输入串并未被识别完的情况），也就是下图的情况：
- 当前文法的产生式没办法匹配当前的向前搜索符（也就是自动机走到了某个状态，但是根据当前的向前搜索符没办法进行状态转移的情况，也就是查表的时候发现格子是空的）
- 总结一下，就只有当能做到下推栈内只剩下结束符号并且当前输入符号也是结束符号的时候才会接受输入串（这个情况的反面只有三种种情况，第一种就是下推栈为空但是输入串中还有符号，也就是上面所说的第一种情况，第二种就是下推栈不为空，但是输入串已经到空了，这种情况本质上就是当前没办法进行状态转移了，第三种情况就是下推栈和输入串都不为空，这种情况本质上也是当前没办法进行状态转移了）
预测语法分析器的组成
- 一个下推栈（下推不知道是逆序压栈的意思还是向下推导的意思），也就是上面的句型推导栈，或者说符号栈，如果栈顶匹配输入串的终结符，就将栈顶弹出，并且将输入串指针向后移
- 一个分析表，根据这个表和当前的向前搜索符确定当前应该选择的产生式
如下图：
预测分析器的状态
- 如果栈顶符号为结束符号，并且当前输入串为空（也只剩下结束符号），就说明输入串被接受
- 如果栈顶符号（为终结符）和输入串的当前符号（向前搜索符）相同并且不为空，就说明当前串目前为止是合法的，但是还没有识别完，这个时候栈顶出栈，输入串指针下移
- 如果当前符号为非终结符，那么根据预测分析表进行产生式的选择。如果能选择到产生式，就将栈顶的非终结符弹出，将产生式右侧逆序压栈（在栈内就是正序的了）；但是如果没办法选择到产生式，就说明当前串被拒绝了（也就是查表找到了空的格子）。
预测分析表的构造（预测分析法的关键）
- 手动构造，具体方法如下（其中t为输入串的前缀单个终结符）
通过填表的顺序来很大程度上保证这个手动构造的正确性：先填右侧以终结符开头的产生式，然后再填右侧以非终结符的产生式（填写这个的时候就要去看非终结符的first集或者该非终结符在预测分析表上已经填写的产生式），如下图：
- 算法构造（编程实现）
- 求first集：当某个产生式的右侧第一个符号为非终结符的时候就需要用到该非终结符的first集。下图实际上就是根据非终结符TERM的first集填入的4（这个时候相当于对非终结符term进行了推导，所以还是那句话，消除了公共左因子并不代表就满足了LL1文法的要求，消除了只能说明表面上没有岔路，但是first集如果有交集的话还是有岔路的）
- 注意求出了first集一个符号的first集只能确定当前符号能接受哪些输入符号，具体要选择哪一个产生式还需要求产生式右侧部分的first集（LL（1）文法保证一个非终结符的产生式的first集没有交集，所以对于一个输入符号，他最多只属于一个产生式的first集）
- 求follow集
所以最方便的做法是自下而上填写预测分析表（然后再根据follow集处理空串产生式），也就是上面的图的做法。
first集的定义（也就是某个非终结符如果能得到以某个终结符开头的串，那么这个终结符就属于这个非终结符的first集，只有当某个符号能推到出空串的时候，空串才属于这个符号的first集）：
first集的构造方法：
这里的推导符号就是单词推导的意思
就是如果能第一个非终结符能推到出空串的话就在X的first集中加入第二个符号的非空终结符
还需要对最后一条规则再做一点补充，就是当X经过多次推导后能推到出空串，那么空串也在X的first集内
终结符的first集就是他自己本身（而不是自己构成的集合）
first集的计算顺序一般是自下而上（就是要求在左侧的开头的非终结符的first集要先求出来，然后才能求在当前产生式右侧的符号的first集），然后先填写明显的first集元素（如产生式右侧第一个符号就是终结符）
要求某个符号的first集，就去找该符号在左侧的产生式（求follow集就是在产生式的右边找该符号），然后运用上述规则
求first集的一个示例
然后只需要根据first集来填写预测分析表即可（first集中有的符号，当前符号都可以识别）
为什么还需要follow集？：因为有的时候某些串需要被推导为空（follow集就是处理空串产生式的），此时输入串的前缀就需要在当前要被推到为空串的follow集内
也就是说如果当前输入符号在当前下推栈的栈顶符号的follow集内，那么说明如果将当前符号推导为空，有可能会出现当前的输入符号，所以这个时候选择将当前符号推导为空。
在输入串中要考虑结束符（下图就是考虑了非终结符end的follow集，这里follow集中包含了结束符，所以end能推到为空串）
如上图的最后一列
也就是下面这张图所说地follow集的作用是:
follow集的定义如下：
也就是某个符号后面会跟上哪些符号
follow集构造的方法如下：
相较于求first集，follow集就需要查找产生式的右侧，去寻找需要求follow集的符号（first集是看右边），然后去看该符号后面的情况。first集是自下而上判定的，但是follow集就是反过来自上而下判定的（因为产生式右边的follow集需要先确定，不然规则三没办法使用）。根据规则二，还一定要先求出来first集然后才能去求follow集
注意规则二的使用需要去掉first集中的空串
注意规则三，算follow集的时候要想明白哪些符号是能产生出空串的（也就是哪些符号的first集中含有空串）
最后根据两个集合来完善预测分析表
最上面一行仍然是指输入串的第一个字符。当当前输入串的第一个字符是在某个符号的follow集中，且当前符号是可以推到为空的时候，就将当前符号推导为空串（只有LL1文法才能这样，因为LL1文法要求当前的文法其他的规则的first集是不含这个字符的，这个时候产生式的选择就是唯一的）
预测分析表的具体构造算法如下：
先求first集处理非空产生式，然后通过follow集来处理空串产生式，当预测分析进行时如果进入了空格就表示出错
使用预测分析法的时候仍然需要消除左递归还有公共左因子（左因子和左递归都会导致无法预测，这个时候是因为两个产生式的first集有交集），具体左递归预测分析的示例如下（这个文法就不是LL1文法了，因为LL1预测分析没办法处理这个文法）：
非LL1文法体现在预测分析表上就是存在一个格子内有不止一个产生式
LL1文法的要求如下：
这里第一个条件就说明了这两个产生式不能都推出空（如果两个产生式都能推出空的话，那么这两个产生式的first集中就都有空串，这个时候first集就有交集了），第二条规则说明推空产生式跟推实际产生式不冲突
小总结：
如何快速求解预测分析表？
最方便的做法是自下而上根据first集填写预测分析表（此时如果已经填写了非终结符A对应的行，那么如果A的上面的非终结符B有产生式B->A...那么就可以直接将B行中在A行中有填写的列填上该产生式，原理是如果有产生式B->A...，那么就代表当前产生式的first集包含Afirst集中的非空部分，这个时候如果当前符号在A的 first集中，就一定在该产生式的右侧的first集中，所以可以直接填写A行中相应的列。如果A可以推导出空的话就需要查看下一个非终结符），然后再根据follow集处理空串产生式。
如果不求速度的话，下面的做法正确性更高：
- 求解所有非终结符的first集
- 根据上一步算出的所有非终结符的first集求解出所有产生式右侧的first集
- 根据上一步算出的产生式first集填写产生式
- 求解所有非终结符的follow集
- 判断哪些产生式经过若干次推导之后能够产生空串（只需要看那些非终结符的first集中含有空串，因为first集中有空串当且仅当该非终结符能推导出空串。找到这些非终结符之后再去找他们在左侧的那一些产生式，然后再判断哪一些能够推导出空串即可）
- 根据follow集填写上一步得到的产生式（这些产生式都是经过若干步推导能够得到空串，所以都需要填写。此时LL（1）文法保证这些产生式都不会填写到已经有产生式的格子里，也就是LL（1）文法要求的first集和follow集没有交集）
注意剩余没有填写的格子都是代表出错的
自下而上的语法分析
自下而上：就是从输入串出发，不断规约成开始符号（也就是猜测规约序列）
自下而上的语法分析方法：
- 广度搜索法：就是尝试当前输入符号的每一种规约（可以加上限制，做最左规约）
- 深度搜索法：就是尝试当前输入符号的每一种规约（可以加上限制，做最左规约）
- LR分析法：是有向的，预测的（有向其实就是预测的意思，每一次规约都是正确的，相当于自下而上的预测分析法）
注意：句柄规约（注意和某个产生式体匹配的最左子串不一定是句柄，这也说明了句柄规约和最左规约是有区别的）倒过来就是最右推导。
此外，文法的二义性可能导致某个状态下符号栈内有多个句柄。如果一个文法是无二义性的，那么任何时候符号栈内都只能有一个句柄
自下而上的语法分析最重要的就是知道应该对哪些串进行规约（也就是如何找到句柄），知道如何规约之后剪枝就迎刃而解了（剪枝就是将树最终剪得只剩下根节点，也就是规约为了开始符号）
每一次都进行最左规约并不一定是正确的，如上图
自下而上语法分析的相关概念（也可以说是文法的相关概念）
- 句型：就是将推导树的叶节点自左至右连接（根据之前的定义，句型是若干终结符和非终结符的组合）
这么想的话推导树跟语法树有一点点不一样，语法树好像叶节点全是终结符，但是推导树的叶节点如果相连是句型的话，就说明推导树的叶节点不一定全是终结符
- 句柄：每次进行处理的子串，也就是正确的、待规约的串。句柄总是出现在符号栈的顶部，也就是最左直接短语
- 移进：将输入串的符号直接放到符号栈内，或者说是将终结符从右区（输入串）移到左区（符号栈）
- 规约：将左区的符号进行归纳，与文法的推导相对应
- 短语：任何子树的边缘（推导树的边缘是将树的所有的叶子节点从左向右链接起来，但是这里好像是不一样的）都是子树根的短语。短语的严格定义如下（注意这里的阿拉法和delta可以是空串。要注意这里前面一个t推导符号是经过若干次推导，也就是*，但是后面的推导符号是经过最少一次推导，也就是+ ）：
体现在语法树上就是任何子树（所以只要遍历一遍内部节点就好了）的边缘（也就是叶节点，此时不要求叶节点是同层的）从左向右链接起来。所以短语的个数应该等于非叶子节点（内部节点）的个数
为什么一定是子树的边缘呢？因为推导树的边缘链接起来才是一个句型，如果已知一个句型并且已经构建了他的推导树，那么根据上面的定义，短语一定是句型的一个部分，所以短语一定是在边缘
上例中β是该句型关于非终结符A的短语（因为β是A推导出来的也就是A是根）
下面是一个求句型短语的例子（注意以当前根节点为根的树也算是一个子树，所以当前句型也是一个短语）
- 直接短语：仅有一代（算上根只有两层）的子树的边缘是相对于子树根的直接短语（因为此时子树就只有两层，所以叶节点一定是同层的）。所以当前句型的句柄就是最左直接短语
自下而上语法分析的核 心思想，根据产生式（构造自动机，根据输入串逆向选择最右推导序列）并且关注当前位置，具体的例子如下图
严格的定义如下：
这个时候β旁边没有其他的符号并且只经过一次推导，就说明这个产生式的语法树是只有两层的（根节点A是第一层），这个时候就称β是相对于根（这里是A）的直接短语
这样每次识别一个输入串中的符号就是一次状态转移，这个时候就能用到状态图（状态图中的每一个状态实际上是跟产生式的最右推导一一对应的），也就是有限自动机
文法相关概念课后习题
前置知识：直接推导，也就是做单步的推导
小技巧：求每步推导所得句型的句柄，实际上就是看哪一些符号是通过这一步推导得到的，这些符号串在一起就是当前句型的句柄（原理是：句柄规约实际上就是最右推导的逆过程，所以每一次最右推导产生的符号就是当前需要规约的东西，也就是句柄），这个时候就是从上往下填的
还有一种方法就是直接句柄剪枝，根据推导树找到句柄然后向上剪枝，这个时候就是从下往上填的
所以考试的时候就能用两种方法做，然后交叉检验一下
LR方法相关概念
- 规范句型：由最右推导（规范推导）得出的句型
- 活前缀（原理是句柄一定是在符号栈的栈顶出现）：规范句型中，不含句柄之后任何符号的前缀
活前缀的严格定义如下：
由于为规范句型，所以A一定是最右边的非终结符，所以w里面是不含非终结符的，而β是推导得出的，可能含有非终结符
活前缀的示例如下：
此时句柄为阿拉法β，所以前面的所有前缀都是活前缀（活前缀的个数应该等于包含句柄的字符总个数）
- 项目：在产生式右部的符号中添加一个原点，表示当前的处理状态（就是符号栈和输入串之间的分界）。项目有如下四种
- 规约项目：当前原点在产生式的最后，需要进行规约（对应action表中的规约操作）
- 移进项目：当前原点在一个终结符之前，期待将这个终结符移进（对应action表中的移进操作）
- 待约项目：当前原点在一个非终结符之前，期待这个终结符规约得到（对应goto表的状态转移操作）
- 接受项目：当前原点在一个产生式的最后，并且这个产生式的左侧是开始符号，此时规约就产生了开始符号，达到了LR分析的目的——将输入串规约为开始符号，此时（自动机）就接受输入串。（对于2型文法而言，文法的开始符号一定不会出现在产生式的右侧，如果产生式右侧有开始符号就需要对文法进行改造，将其改造为上下文无关文法）
如何计算一个文法的所有项目：
就是在每一个产生式的右侧的各个位置都加上点
- 项目与活前缀的关系——项目的有效性
项目的有效性具体定义如下：
这里的A就是句柄的项目
或：
还是上面那一句话，如果当前识别的活前缀对当前项目是合法的（就是通过识别前面的活前缀到达了当前的项目），就说这个项目对当前已经识别的活前缀有效
- 有效项目集：对同一个活前缀有效的集合（所以这个集合里面的每一个项目实际上都是识别了同一个前缀之后到达了这个状态）
有效项目集的计算（从定义出发，沿着一条边进行了一次状态转移之后形成的项目一定是对同一个活前缀有效的，然后在这些项目的基础上进行闭包运算，经过这些操作就能构建出一个项目集）：
第二条规则的证明如下（实际上就是从定义出发）：
项目集规范族：所有有效项目集的集合，如下图（从开始符号对应的产生式开始计算有效项目集，计算出第一个项目集之后逐个去识别符号然后进行状态转移，然后在得到的若干个项目的基础上继续求项目集）：
如何求LR（0）项目集规范族：
格式如上（里面的go表示从某个项目集识别了某个符号到达的项目集，如go（I0，B）就是从I0项目集识别了符号B之后到达的项目集）。求项目集规范族的时候一定要按照这个格式来（每一个能识别的字符都写出来），这样子写的话画状态转移图的时候也不会漏边
如何根据文法构建一个有限自动机（bison做的工作就是这个。准确来说，bison就是构造了一个分析程序，和一个LR分析表。分析程序构造自动机的框架，而分析表提供状态转移的函数，这两个合在一起就变成了这个确定有限自动机）
每一个非终结符就是一个状态，每个产生式的每一个位置带上点都是一个新的状态（这个是时候就不是最右推导对应的规约的自动机了，我们的目标就是找到对应最右推导的自动机），终结符（非终结符转移也行）转移的时候就是在两个状态之间加入对应的终结符（或者非终结符），也就是上面x（上面的x可能是终结符，也可能是非终结符）的例子；当需要识别一个非终结符时，还需要额外在当前状态和对应的非终结状态之间加上一条空边
这个加号的状态转移就像是一次闭包运算，因为下面可以接受一个非终结符E，就是可以接受一个非终结符T。。。
这个就是将上面的非确定有限自动机确定化后的结果（好像不需要使用之前确定化的那个方法，直接对进行了闭包运算的产生式进行符号的逐个识别加边即可）
具体的构建确定有限自动机的方法如下：
这个第一条规则就是上面所提到的闭包运算，第二条规则就是上面说的对每一条规则进行符号的逐个识别并且加上边
由于当前的自动机并不是对应着最右推导的自动机，而是通过一种枚举状态（相当于广度优先创建了一个图，最右推导只是其中的一条识别路径）来生成的自动机，所以这个时候自动机识别到了一个句柄（就是对某一个状态有一个产生式的点在最右侧），并不一定是我们需要的句柄，所以我们需要对此进行确认
LR（0）语法分析
在来一次小知识（原来真的是最右推导的意思）：
注意这个0，说明没有向前搜索符
如果没有状态栈来同步记录之前的状态的话，那么每次规约结束的时候都需要重启自动机（因为这个状态没有后续的状态了），并且重启自动机再次进行搜索这个时候就需要从符号栈的栈底开始重新看一遍了，这样是有很多重复操作的，所以需要状态栈来记录之前的状态便于状态的回溯（这样就不用重启自动机了）
符号栈和状态栈能够同步的原因是每次状态转移都只识别了一个符号，这样的话一个状态就对应一个符号，当进行规约的时候一些符号出栈，那么出栈几个符号，就说明前面的第几个状态需要当前规约产生的符号， 所以符号栈和状态栈是同步的，符号栈出几个符号，状态栈退几个状态，但是每次出栈之后要重新识别当前栈顶规约生成的符号。上面所说的也就是下图所说的记录自动机上一次的状态（这样就可以一直运行自动机直到符号栈内只有开始符号）：
注意：维护状态栈的时候，在启动自动机的时候（此时还未识别输入串）就需要将开始状态的状态编号压入状态栈
如下图：
LR语法分析的表示方式
LR（0）分析表——action表（指出当前状态下应该执行移进操作还是规约操作还是接受操作还是报错操作）和goto表（指出状态的转移目标）
下面给出一个action表和goto表的实例：
可以发现goto表是处理非终结符的（但是goto表中没有开始符号，goto表中代表的是规约后放在符号栈栈顶的非终结符，这个时候没必要去考虑开始符号，因为当符号栈栈顶出现了开始符号的时候就说明出现了接受项目，也就是规约结束了，这个时候就不用进行goto状态转移了。而且就算在goto表中加上了开始符号，开始符号那一列也是全空的，因为没有边的条件是开始符号，这是因为开始符号不会出现在产生式右侧），而action表是处理终结符的，但是要注意，goto表的处理的非终结符是规约生成的、放在符号栈栈顶的，但是action表处理的终结符就是输入串的第一个终结符。总结一下，action表根据当前的输入串的第一个终结符来决定是移进还是规约还是接受还是拒绝，而goto表是根据某次规约生成的符号进行状态转移，跟输入串无关。
注意action表中的s的右下角的数字代表的是经过这个操作之后应该转移到哪一个状态。而r右下角的数字是代表按照哪一个产生式进行规约的（所以这个时候要先对产生式小小地编一下号）
要记住这个表的横轴纵轴代表的是什么
LR分析器的结构：
这里的驱动程序实际上就是一个自动机（状态图）
上面的只是一个action表和goto表的概论，下面开始详细介绍
action表（行上是终结符）
移进操作：
所以action表的第一行全是终结符（代表的是输入符号）
j的含义就是识别了当前的输入符号后会到达哪一个状态
规约操作：
j就是代表当前规约是按照哪一个产生式进行规约的。只需要提供是按照哪一个产生式规约的即可，因为进行规约时对栈的操作就是状态和符号出栈，然后在符号栈中压入规约生成的符号，而出栈几个符号这个信息是包含在规约产生式中的（产生式右侧有几个符号就出几个符号）
然后规约之后栈顶就是规约生成的符号，这个时候就需要查goto表进行状态转移（所以goto表的第一行全是非终结符，goto表是在进行规约的时候查的）
接受状态与出错状态：
接受状态就是当某个状态能够根据结束符进行操作（某个规约式的左侧是开始符号并且当前输入的符号是结束符），此时自动机就接受源程序
出错状态就是查action表之后发现当前格是空的，也就是不能执行任何操作，此时就说明自动机无法进行状态转换了，所以自动机拒绝当前输入串
当某一个状态（项目集）里的项目都是规约项目的时候，该状态在goto表中的行都进行规约操作（接受项目除外，接受项目直接在表内填acc，注意接受项目实际上就是一种特殊的规约项目）
goto表
goto表的第一行是规约生成的非终结符
goto表的含义如下：
这里说规约后，所以就是当action表中进行了规约操作了之后（之后就是指状态已经回退并且非终结符已经放入符号栈内的时候）需要去查goto表进行状态转移,但是实际上构建goto表的时候只要看自动机的非终结符的状态转换边即可
文法改造（关于自下而上分析）
自下而上的语法分析可以识别左递归和公共左因子，但是没办法处理非1型文法，所以只需要对非1型文法进行改造（也就是改造文法使接受项目只有一个）
自上而下语法分析不能处理左递归是因为会出现死递归（出现死递归主要是在递归下降分析法中，广度没有特别大的影响，左递归对预测分析法的影响就是first集有交集）。有公共左因子的时候（广度需要向前看更多的符号，递归下降分析法没什么影响，但是预测分析法中的first集会有交集）
为什么需要改造文法：因为LR分析认为，当规约项出现开始符号的时候就接受这个输入串（也就是出现接受项目的时候），这要求接受符号必须是正确且唯一的，但是如果开始符号出现在产生式的右侧，那么这个时候规约生成开始符号就不代表着这个串已经识别完成了（也就是当前虽然规约为开始符号，但是不一定是接受项目）。此外还需要保证开始符号的产生式是唯一的，因为如果是不唯一的话这几个产生式都可以是接受项目，此时接受项目不是唯一的，所以需要改造文法将文法改造为1型文法（让开始符号不出现在产生式右侧）上面所说的也就是下面这个问题：
如何改造文法：将文法改造为拓广文法（也就是不认为原来的开始符号是文法的开始符号，而是单独增加一个开始符号，也就是一个唯一的接受项目，接受项目实际上就是对应着自动机的结束状态集合中的一个元素，也就是一个项目集）。上面所说的具体如下图：
LR（0）的不足
没办法处理两种冲突
- 移进规约冲突：当一个状态（项目集）内既有移进项目又有规约项目的时候，就会出现移进规约冲突（如下面SLR开头的例子），这个时候句柄可能已经出现（此时就应该进行规约），也可能没有出现（此时就应该进行移进）。此时LR（0）分析 法选择能规约就进行规约（就是规约的优先级大于移进）。虽然通过项目集的状态转移已经排除了大多数的错误情况（此时已经不是移进符号串能规约就规约了，这个时候需要自动机走到了一个规约项目才进行规约），但是仍然有一些情况没办法排除。
- 规约规约冲突：当一个状态（项目集）内有多个规约项目的时候，就会出现规约规约冲突。此时已经确定了要进行规约，就说明句柄实际上已经出现了，但是不知道规约的产生式是哪一个
SLR（1）语法分析
SLR（1）是一个简单的LR（1）分析
LR（0）语法分析的缺陷：没有办法处理移进规约冲突（也就是当一个项目集中存在一个规约项目又存在一个移进项目的时候，这个时候action表上的移进操作和规约操作冲突，也就是action表内的一个格子里面有两个操作）
也就是下面有效项目集I8的情况（项目集内有规约项目又有移进项目）：
SLR（1）的核心思想
SLR（1）能处理的文法在出现两种冲突的时候需要满足如下要求（满足要求的称为SLR（1）文法。是不是SLR（1）文法是跟文法有没有改造没关系的，改造了并不会改变文法的类型）：
具体操作如下（所以此时就不是像LR（0）那样能规约就规约了，就是不是整行都是规约。根据下面的规则进行修改后的LR（0）分析表就是SLR（1）分析表）：
注意这里虽然不需要first集，但是还是需要求出来first集（因为follow集的求解需要first集，看产生式右边，并且是从上到下的）
LR（1）语法分析
LR（1）核心思想
通过上下文信息，缩小follow集（就是求解向前搜索符），来准确预测当前应该进行的操作，也就是下图：
注意这里是有错的，并不是把first（β）当成项目的向前搜索符，而是将first（βα）当成当前符号的向前搜索符，其中β是一样的，但是要加上α，α就是当前项目的向前搜索符
下面给出具体的构造LR（1）项目集规范族的方法（如下图）：
也就是：
- 将结束符号作为开始项目的向前搜索符
- 在当前项目集中做闭包运算，每次做闭包运算的时候都要看后面符号(加上向前搜索符)的first集，也就是上面说的βα的first集，并且将这个first当成当前做闭包运算生成的项目的向前搜索符，直至项目集不再增大。
- 在这个项目集上进行符号识别获取其他状态的初始项目，并且做这样的状态转移的时候向前搜索符要继承。
- 继续执行上述的过程直至不再产生新的项目集
注意如果两个项目本身是一样的，但是他们的向前搜索符不同，这种情况在LR（0）和SLR（1）中认为是同一个项目，但是在LR（1）分析中，就认为不是同一个项目，需要继续做闭包运算。也就是下图的这种情况：
LR（1）文法
如果一个文法的LR（1）分析表中没有多重入口（就是能被LR（1）分析器分析），那么这个文法就是LR（1）文法。
文法之间的包含关系
分析方法的分析能力（也就是能识别的文法数量）：LR（1）>LALR（1）>SLR（1）>LR（0）
所以如果一个文法是LR（0）文法，就一定是SLR（1）文法，就一定是LALR（1）文法，就一定是LR（1）文法，反之不然
LR（1）分析相关概念
- 心：LR（1）项目中与LR（0）中相同的部分，也就是前面的产生式状态部分
- 向前搜索符：当前产生式进行规约需要查看的符号集合，也就是相对于LR（0）多出来的那一部分
- 同心集：对于两个LR（1）项目集，如果他们的心是相同的（此时就不考虑向前搜索符了），那么他们就是同心集
LR（1）分析通过向前搜索符的不同，使一些同心集分裂了，进而使项目集规范族中的项目集个数增加，如下图：
同心集的合并及LALR（1）语法分析
同心集的合并实际上就是对LR（1）文法项目集规范族进行的自动机简化
自动机简化算法如下：
确定有限自动机的化简
两个化简的条件
第一个就是如果两个状态是等价状态，那么他们当前的状态一定要是一样的，也就是说终态不可能和非终态等价。所以划分集合的时候是将当前的状态集划分为终态集合和非终态集合，并且每一次判断蔓延性条件的时候都是在同一个集合内判定
第二个就是如果两个状态是的等价状态，那么他们识别字符后到达的状态应该是一样的
到这里就可以发现，这个生成的集合其实就是最终化简后的自动机的状态，所以只要当当前自动机的两个状态经过任意的字符运算之后的结果落在同一个集合（也就是化简后的自动机的状态），那么就认为这两个旧状态满足蔓延性条件
当两个状态满足这两个条件的时候就说明他们是等价状态
当两个状态都没有下一个状态（如项目集中的规约项目），这个时候认为他们是不一样的
经过合并同心集之后没有产生冲突的项目集规范族就是LALR（1）项目集规范族（LALR（1）项目集的数量与LR（0）和SLR（1）相同）
但是由于LALR仍然考虑的是向前搜索符而不是follow集，所以分析能力强于SLR（1），但是合并之后少了很多精细的部分，导致其分析能力弱于LR（1）
如何合并同心集？
- 首先对一个LR（1）项目集进行书写简化，也就是在项目集中，如果两个项目具有同样的心，那么就通过/（说白了就是两个同心项目的向前搜索符取丙级223）将他们的向前搜索符连接起来以代表两个项。即下图的表示法：
- 然后对同心集进行处理，将所有同有同心集合并，然后两个同心集中对应的同心项的向前搜索符取并集并且用/连接之后称为生成项目集中该项目的向前搜索符
LR分析法异同
分析能力
- LR（1）最强
- LALR（1）次之
- SLR（1）再次
- LR（0）最弱
相同点
- 分析·表的形式：都是action表和goto表
- 控制程序（操作）：都是移进、规约、接受拒绝等操作
不同点
- 分析表的内容不同，或者说限制条件不同
- LR（0）：进行规约操作时直接进行规约（也就是能规约就规约）
- SLR（1）：进行规约时查找follow集，当前输入符号在follow集内才进行规约
- LALR（1）：进行规约时查找向前搜索符，当前输入符号在向前搜索符集合内才进行规约
- LR（1）：进行规约时查找向前搜索符，当前输入符号在向前搜索符集合内才进行规约
所以这些文法都是在改进进行规约时的条件
LR分析法可能存在的冲突（并不是说LR（1）分析法就没有冲突了，只是冲突少了）
- 移进规约冲突：同一个格子内既有移进操作又有规约操作（此时没办法确定句柄是否出现）
- 规约规约冲突：同一个格子内有多个规约项目（此时句柄已经出现，但是没办法确定哪一个是句柄）
LR分析法总结
- LR（0）：分析表简单，但是只能处理无冲突的文法
- SLR（1）：通过follow集的求解能解决一类移进冲突问题，分析表是在LR（0）基础上改进的，所以分析表跟LR（0）相同
- LR（1）：通过求解向前搜索符解决大部分冲突，但是分析表也最大
- LALR（1）：分析能力强于SLR（1），但是分析表并没有变大
小总结：
- 求LR（0）分析表就是单纯的做闭包运算，然后填表
- 求SLR（1）分析表先求出first集和follow集然后再进行闭包运算，然后填表
- 求LR（1）分析表就不需要求first集和follow集（SLR（1）本质上也是只用到了follow集，但是求follow集需要先求出来first集）了，而是直接求项目集规范族（也就是做闭包运算。这个时候要带上向前搜索符的求解），然后填表
- LALR（1）本质上就是求LR（1）然后合并同心集，然后填表
- 那么如何填表（对每一个LR分析方法来说填表都是一样的）？
- 首先根据计算闭包时的go函数填写移进项目和goto表（因为这些方法的限制实际上都是在限制规约操作，所以移进操作和状态转移操作总是能先写的）
- 找出含有规约项目的项目集
- 然后根据不同的文法进行规约操作的填写
- LR（0）：整行都填写规约操作
- SLR（1）：只有当当前输入符号在待约产生式左侧符号的follow集中才填写规约操作
- LR（1）：只有当当前输入符号在待约产生式左侧符号的向前搜索符集合中时，才填写规约操作
- LALR（1）：同LR（1）
- 作者:Noah
- 链接:https://imnoah.top/article/Compiler/Chapter4
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。