- 语法分析简介
- 上下文无关文法（Context-Free Grammar，CFG）
- 自上而下的语法分析
- 自下而上分析法
语法分析简介
语法分析（Syntax Analysis），也称为解析器（Parser），是编译过程中的第二个阶段，紧随词法分析之后。语法分析的主要任务是根据源代码中识别出的词法单元（Token）序列，按照给定的语法规则（通常是上下文无关文法）来构建抽象语法树（Abstract Syntax Tree，AST） 或 语法分析树（ Parse Tree），以便后续的语义分析、中间代码生成等阶段使用
上下文无关文法（Context-Free Grammar，CFG）
定义
例子
文法产生式的推导
产生式的推导是指根据文法的产生式规则，从起始符号（通常是文法的开始符号）出发，通过一系列推导步骤生成一个或多个句子的过程
步骤
- 初始状态： 从文法的起始符号开始，作为推导的初始状态
- 选择产生式： 根据当前推导所处的状态（即当前推导所得的符号串），选择一个适当的产生式进行推导。通常有多个产生式可以选择，需要根据文法规则进行选择
- 替换： 根据选择的产生式，将产生式右部的非终结符替换为相应的终结符或非终结符序列，从而生成新的符号串
- 重复： 重复步骤2和步骤3，直到无法再应用产生式进行推导
最左推导
在文法的推导过程中,每一步推导总是选择最左边的非终结符进行替换，直 到推导出目标符号串，称为最左推导（最右推导相反）
与推导相关的概念
注意：
- ABC等大写字母表示非终结符
- abc等小写字母表示终结符
- αβδ等希腊字母表示终结符或非终结符
上面的定义看起来很难，其实一点都不简单，下面这个例子理解起来会容易一些
例子
可以通过语法树来求解：
- 短语：一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语
- 由根节点 E 推出：E+T * F+i
- 由子树节点 E 推出：E + T * F
- 由子树节点 T 推出：T * F
- 由子树节点 T (或 F )推出：i
- 直接短语：当子树不包含其他更小的子树时，该子树叶节点所组成的字符串就是该句型的直接短语。
- 最小子树 T 推出：T * F
- 最小子树 F 推出：i
- 句柄：最左边的直接短语
规约
- 在语法分析中，规约通常是在符号串中匹配到一个产生式右部时，将其替换为该产生式左部的非终结符
- 如果归约是最右推导的逆过程（从左侧开始反推），则称为规范规约
例子
活前缀（可行前缀）
定义
活前缀与句柄的关系
- 活前缀已含有句柄的全部符号 (可归约) A→αβ · ，产生式右部 αβ（句柄）已经出现在栈顶，用A→αβ 进行归约
- 活前缀只含有句柄的一部分符号，A→α·β ，α 已经出现在栈顶，期待从余留输入串中看到能由β推出的符号串
- 活前缀不含有句柄的任何符号，A→· αβ ，期待从余留输入串中能看到 αβ 推出的串
语法分析树
文法的二义性
定义：
消除方法
- 利用优先级（如四则运算优先级）
- 利用结合性（如左结合性）
- 改写文法
左递归文法
定义
左递归 是编译原理中的一个问题，出现在语法规则中。如果语法规则包含左递归，递归下降分析器（如 LL 分析器）在解析输入时可能会陷入无限循环，导致语法分析失败。为了解决这个问题，需要消除左递归。
左递归分为以下两种
如何消除
直接左递归
间接左递归
提取公式左因子
定义
左因子提取 是编译原理中的一个技术，用来解决文法中的左公共因子问题。左因子提取通常用于处理 LL(1) 分析器，使得语法在解析时避免歧义。左因子问题的典型形式是，当多个产生式以相同的前缀开头时，分析器不知道选择哪个产生式。为了解决这个问题，我们将这些具有公共前缀的产生式合并。
如果一个非终结符的多个产生式有相同的前缀，则称这些产生式具有左公共因子。例如，文法中有以下规则：
A → αβ1 | αβ2
其中 α 是两个产生式的公共前缀。在这种情况下，递归下降分析器在看到前缀 α 时不知道是继续匹配 β1 还是 β2 ，因此会导致解析的歧义。
方法
自上而下的语法分析
定义
自上而下分析是一种语法分析方法，从文法的开始符号出发，尝试构建一个推导树， 以验证输入符号串是否符合给定文法。自上而下分析在某些情况下是有效的
局限性
- 左递归：自上而下分析对于左递归文法处理起来比较困难。左递归可能导致自上而下分析进入无限循环，难以正确地完成分析，必须消除左递归。
- 左公因子的处理：自上而下分析在处理文法中存在左公因子的情况时。左公因子可能导致分析器无法确定选择哪个产生式进行推导，影响分析的准确性。
- 可能存在回溯：自上而下分析在面对文法中存在多个可能的推导路径时，可能会出现非确定性，分析器可能需要尝试多个路径，在遇到错误时可能需要回溯到之前的状态重新尝试其他分析路径，会增加分析的时间复杂度
递归下降分析
递归下降分析是一种常见的自顶向下的语法分析方法，用于判断一个输入字符串是否符合给定文法规则。在递归下降分析中，每个非终结符对应一个分析函数，通过递归调用这些函数来分析输入字符串。以下是递归下降分析方法的详细步骤：
- 准备工作：首先需要准备好文法的产生式集合，改写文法消除左递归、提取公共表达等，每个非终结符对应编写一个分析函数。通常会有一个主函数作为入口，用于开始分析过程
- 编写分析函数：对于每个非终结符 A，编写一个对应的分析函数 A()。在分析函数中，根据文法规则选择相应的产生式进行推导
- 递归调用：在分析函数中，如果遇到一个非终结符 B，则递归调用B() 函数进行分析；这样可以逐步展开并分析整个输入字符串
- 匹配终结符：在分析函数中，如果遇到一个终结符（如标识符、关键字等），则需要匹配输入字符串中的相应部分，以确保输入符合文法规则
- 错误处理：如果在分析过程中发现输入字符串不符合文法规则，需要进行错误处理，通常是报告语法错误并尝试恢复分析过程
- 递归下降分析：通过递归调用各个分析函数，逐步分析整个输入字符串，直到达到文法的终结符或无法继续推导
LL(1)
定义
LL(1)文法是一种特殊的上下文无关文法
- L：从左到右扫描输入串
- L：用左推导规则构建推导过程
- 1：在每一步分析时，只需查看输入串中的一个符号和栈顶符号
如果在每一步分析时，需要查看输入串中的k个符号和栈顶的k个符号,则称为 LL(k)文法
First 集
定义
对于文法G的所有非终结符的每个候选式,其首终结符集称为FIRST集
计算方式
上述所有算法目的只有一个：找到 X 最先可能出现的终止符
- 如 ② 当 X1 可以推出 ε 时，就可能在 X2 中出现终止符，故在 FIRST(α) 中加入 FIRST(X2) ，以此类推
- 如 ④ 当所有FIRST集中都含有 ε 最后可能会推出 ε ，故加入集合
例子
FOLLOW集
定义
对于文法G的非终结符的后继符号集称为FOLLOW集
计算方式
预测分析表
- 预测分析表是一个二维表，行表示文法中的非终结符，列表示文法中的终结符（包括输入符号和结束符号$）。
- 每个表项包含一个产生式或一个错误标记。产生式指示应该使用哪个产生式进行推导，错误标记表示分析过程中的错误
构建方法
- 如果存在产生式 A → α ，则对于 First(α) 中的每个终结符 a ，将产生式 A → α 添加到表项 M(A, a) 中
- 如果 ε ∈ First(α) ，则对于 Follow(A) 中的每个终结符 a ，将产生式 A → α 添加到表项 M(A, a) 中
- 如果 ε∈ First(α) 且 $ ∈ Follow(A) ，将产生式 A → α 添加到表项 M(A, $) 中
例子
分析过程
LL(1)文法特点
- LL(1)文法每个非终结符的每个产生式都有一个唯一的前缀；能够根据当前的非终结符和输入符号预测使用哪个产生式，避免回溯
- LL(1)文法中的产生式的First集和Follow集之间两两不相交，或者如果有ε 产生式，则这些产生式的First集和Follow集之间两两不相交即：
- 对于每一个非终结符
A，如果A → α和A → β是两个产生式，则First(α)和First(β)不能有交集（也就是不能有相同的符号）。 - 如果
A → α中的α可以推导出空串ε，则First(α)和Follow(A)之间也不能有交集。 - 假设文法中有产生式
A → α和A → β，如果First(α)和First(β)有交集，那么当解析器看到这个交集中出现的符号时，它无法确定该选择A → α还是A → β。这样就会导致歧义和错误的解析。 - 如果产生式
A → α包含ε，那么还需要考虑Follow(A)集。如果First(α)中有ε且First(α)和Follow(A)有交集，也会导致解析器在遇到 Follow 集中的符号时不知道应该结束解析还是继续选择下一个产生式。
- 对于每一个非终结符
- LL(1)文法可以构建LL(1)预测分析表M，用于预测分析过程
判断文法是LL(1)文法的条件
总结
自下而上分析法
定义
- 自下而上语法分析是一种基于推导的语法分析方法，它从输入字符串开始，逐步将输入字符串规约为起始符号，通过构建语法树或分析栈来实现。
- 通过重复执行移进和归约操作，分析栈逐步演变，直到最终只包含起始符号；如果在分析过程中，最终分析栈只包含起始符号，并且输入字符串已经被完全处理，则分析成功，输入字符串符合文法。
- 自下而上的分析方法中，LR分析器是一种常用的分析器类型，包括LR(0)、SLR、LR(1)、LARL等；LR分析器通过构建LR自动机和分析表来实现自下而上的语法分析，具有较强的表达能力和效率
递进-规约
- 自下而上语法分析从输入字符串的左端开始，逐步将输入符号移入分析栈。移进操作将输入符号移入分析栈，并继续处理下一个输入符号。
- 当分析栈顶部的符号序列匹配一个文法的右侧产生式时，可以执行归约操作；归约操作将栈顶的一些符号替换为一个非终结符，这个非终结符是产生式的左侧符号
例子
LR语法分析技术
定义
- LR(k)语法分析：是一种有效的自下而上的语法分析方法，L——从左向右扫描输入串；R——反向构造最右推导序列
- K表示在做出语法分析决定移进或规约时，需要向前看 K(K≥0) 个符号
- 向前看0个符号，就是LR(0)分析法；向前看1个符号，就是LR(1)分析法
- 大多数用上下文无关文法描述的语法结构，都可用LR分析器来识别
- LR分析器的分析过程可用LR自动机来描述
结构
LR(0)文法
在LR(0)文法中，每个项目只包含文法产生式的左部和右部，只考虑每个项目的当前状态，不包含向前看符号。LR(0)项的形式为 [ A→α∙β ]，表示已分析到产生式 A→αβ 的某个位置。
项与LR(0)自动机
项目的分类
构建LR(0)文法项集的方法
例子
如果有拓展文法为S → Ab； A → abC； C → d，那么 C→d 不在初始项集中
GOTO函数与LR(0)自动机
构建项集规范族
构建LR(0)分析表的算法
例子
LR(0)语法分析过程的一般步骤：
- 构建LR(0)自动机： 根据文法构建LR(0)自动机，包括初始状态、状态扩展、状态转移等。
- 初始化： 将初始状态压入分析栈中，并读入输入符号串的第一个符号。
- 状态转移和规约，重复以下步骤直到分析完成：
从分析栈顶取出当前状态，并根据当前输入符号a和自动机转移边- 如果当前状态有转出边a，则将输入符号a移入符号栈，并将转向的状态压入状态栈。
- 如果是规约操作，则根据规约表中的产生式进行规约操作，将产生式右部符号弹出，将产生式左部符号压入分析栈，并根据新的状态和产生式左部符号在LR(0)分析表中查找对应的动作
- 如果是接受操作，则分析成功，输入符号串符合文法。
- 错误处理： 如果在分析过程中遇到无法识别的输入符号或无法进行移入或规约操作的情况，可能会发生错误。此时需要进行错误处理，通常是报告语法错误或尝试恢复分析过程。
例子
移进方法举例（以 0 到 1 为例）
- 通过状态栈顶 0 和输入串最左符号 id 找到 s5, 进行移进
- 转移到状态 5， 并将 5 压入状态栈， id 压入符号栈
规约方法举例（以 6 到 7 为例） - 通过状态栈顶 5 和输入串最左符号 id 找到 r6，进行规约（r6 对应 F→id）
- 规约完成后通过状态栈顶 7 和符号栈顶F找到GOTO 10，转移到状态 10， 并压入状态栈顶
LR(0)中的项目冲突
解决办法
- 如果 a 属于 FOLLOW(A) 集，说明在A之后出现的第一个终止符是 a ，故进行规约
- 如果 a 属于 {a1, a2, a3,…, am} 那么说明 a 是某个右式的一部分而不能是 A 的后续终止符，故移进
SLR(1) 语法分析方法
定义
- SLR(1)表示“Simple LR parser for a single lookahead token ” ，意为“简单的左到右解析” ，是自底向上的语法分析方法
- 由于SLR(1)文法考虑了Follow集合，因此可以在规约时更准确地确定使用哪个产生式进行规约，减少规约冲突的可能性。相比之下，而LR(0)文法则不考虑 Follow 集合，只根据项目的状态转移来构建分析表，LR(0)文法可能会存在更多的规约冲突
- SLR(1)文法通常比LR(0)文法更强大，可以覆盖更多类型的文法；LR(0)文法更容易构建，但是在某些文法可能无法准确地进行语法分析
SLR(1) 分析表构造算法
SLR(1) 与 LR(0) 构建分析表非常相似，区别在于，当前者在进行规约操作时，只有后续符号出现在FOLLOW集中才进行规约，而后者则直接规约
例子
判断文法是否是SLR(1)文法
SLR(1)分析器的工作过程
- 初始化：将初始状态（通常是包含文法的起始符号的项目）压入分析栈中，并读入输入符号串的第一个符号
- 状态转移和规约：重复以下步骤直到分析完成：
从分析栈顶取出当前状态，并根据当前输入符号和当前状态在SLR(1)分析表中查找对应的动作- 如果是移入操作，则将当前输入符号移入分析栈，并将新的状态压入分析栈
- 如果是规约操作，则根据规约表中的产生式进行规约操作，将产生式右部符号弹出，将产生式左部符号压入分析栈，并根据新的状态和产生式左部符号在 SLR(1) 分析表中查找对应的动作
- 如果是接受操作，则分析成功，输入符号串符合文法
- 错误处理：如果在分析过程中遇到无法识别的输入符号或无法进行移入或规约操作的情况，可能会发生错误。此时需要进行错误处理，通常是报告语法错误或尝试恢复分析过程。
- 分析结果：如果分析成功并且输入符号串符合文法，则分析过程结束，可以得到语法分析树或其他分析结果。如果分析失败或遇到错误，则需要进行相应的错误处理
工作方式与 LR(0) 相同
例子
SLR(1)文法是无二义性的，但无二义性文法可能不是SLR(1)文法
例子
SLR(1) 冲突问题分析
以上分析表明，SLR(1)中解决LR(0)冲突的FOLLOW集可能会大于实际即将面临的输入符号集。不妨把即将面临的输入符号集称为超前信息。LR(1)分析法就是利用超前信息解决以上冲突的
LR(1)分析器
定义
LR(1) 的有效项集
例子
SLR(1) 是对 LR(0) 的改进，能够通过 Follow 集减少部分冲突，但其上下文敏感性较弱，容易在复杂文法中产生冲突。LR(1) 更加精确，它通过引入展望符号（向前搜索符号）增强了对上下文的控制 (展望符号集合比FOLLOW集合更小或相等，以避免错误规约) ，从而减少冲突，适用于更加复杂的文法。
LR(1) 分析表构造
例子
LR(1) 分析法的不足
- 随着文法的复杂度增加，LR(1)项集族的大小也会增长，导致分析表变得庞大，占用更多的内存空间。这可能会影响分析的效率和速度
- 相对于其他自底向上的分析方法，如SLR(1)，LR(1)分析法的性能可能不如其它方法高效。LR(1)项集族的构建和分析表的生成可能需要更多的时间和资源
- 由上例中可以看到，有些状态集除了搜索符不同外是两两相同的
- 解决办法：合并同心集，构造LALR分析表
合并同心集算法
定义
在合并同心集算法中，两个仅展望符号不同但项目内容相同的项目集会被合并。这样合并后，多个项目的展望符号会存储在同一个状态中，并在具体操作时（例如移进或归约）再根据展望符号的不同进行区分。这大大减少了状态的数量。
构造方法
例子
几种至下而上分析法的差异
规约上
- LR(0) 分析考虑所有终结符
- SLR(1) 分析考虑FOLLOW 集
- LR(1) 分析仅考虑 LR(1)项目中的搜索符
- LALR 分析考虑的是LR(1)项目合并之后的搜索符
构造分析表上
