Syntax analysis / Parsing
基本过程
- 输入 Token： 接收词法分析器生成的词法单元流（tokens stream）作为输入。
- 匹配文法规则： 解析器尝试根据定义的文法规则（通常是 CFG ）识别 token 序列的结构。
- 构建语法分析树： 每当一组 token 与某个文法规则匹配时，解析器在语法分析树中添加相应的节点，表示一个高级结构被识别。
- 错误检测： 如果当前的 token 不能根据文法规则进行匹配，解析器报错。错误报告可能包括错误类型、位置和可能的修正建议。
- 继续或终止： 如果遇到错误，解析器可能会尝试从错误中恢复，以便继续解析后面的 tokens，或者直接终止解析过程。
- 成功完成： 如果所有 tokens 都被成功匹配并且整个输入字符串被完整地解析成一个语法分析树。
Given the following two CFGs over the alphabet Σ = {a, b, c}, the most restrictive
language that can describe them among following:
每个类别都是比前一个更广泛的语言类别的超集。这里，“最受限的”语言类型是指包含的语言种类最少的那个，即
自顶向下
Top-Down
回溯递归下降
Recursive descent parsing
在遇到解析决策点时尝试各种可能性，如果一个选择失败了就回溯并尝试另一个选择。
- 它预测哪个产生式是正确的可能非常困难，导致解析器重复尝试并回溯。
- 它无法直接处理左递归的文法规则，容易导致解析器陷入无限递归。
- 在某个非终结符的推导过程中，最左边的符号是它自己的规则，例
消除左递归
Eliminate left recursion
参考视频：https://www.bilibili.com/video/BV1BS4y1M7a9
（核心即引入一个新变量）
- 例：
LL(1)
LL(k)，预测解析，一种避免回溯的技术 (A recursive descent variant without backtracking)。
这种方法只需要向前看 个符号，就可以决定应用哪条文法规则进行解析。
构建过程
First(X) 所表达的是非终结符 X 所有可能的开头终结符号的集合（单词的开头）
- 如果一个非终结符产生一个终结符或 ε，那么这个终结符或 ε 在它的 First 集合中： ⇒ First(A) = {1, ε }
- 如果一个非终结符 A 产生了另一个非终结符 B，那么 First(B) （ε 除外 ）的符号放入 First(A)
- 如果 A 推导出的是一个序列：A -> XYZ
- X 无法推出 ε，则直接把 First(X) 放入 First(A)
- X 能够推出 ε，那么先将 First(X)/ ε 放入后，查看 Y 的 First(Y)，依此类推
Follow(X) 所表达的是非终结符 X 所有可能的后随终结符号的集合 （单词的后面部分）
- 对于文法的开始符号 S，将 $ (或者#) 放入 Follow(S)
- 如果有一个产生式 A → αBβ
- B 后不为空 【α 什么都行（终结符/非终结符/ ε），β 不能是 ε 】
- β 是终结符，则直接把 β 放入 Follow(B)
- β 是非终结符
- 无法推出 ε，把 First(β)（ε 除外 ）的符号加入 Follow(B)
- 推出 ε：则转为下一个情况（把 Follow(A) 也加入 Follow(B) ）
- B 后为空：相当于（产生式 A → αB），把 Follow(A) 的符号放入 Follow(B)
例题
FIRST set
看产生式左边
- FIRST(S) = { a, b }
- FIRST(Q) = { b, FIRST(R), 0 } = { b, a, 1, 0 }
- FIRST(V) = { 0, ) }
- FIRST(R) = { a,1 }
FOLLOW set
看产生式右边
- FOLLOW(S) = { $ }
- FOLLOW(Q) = { Follow(S) } = { $ }
- FOLLOW(V) ={ Follow(S), 1 } = { $, 1 }
- FOLLOW(R) = { (, First(Q)} = { (, b, a, 1, 0 }
Predict parsing table
对于每条文法规则 A → α，执行以下操作：
- 对于 First(α) 中的每个终结符 a，将 A → α 填入预测分析表中 A 的行和 a 的列。
- 如果 α 推导出 ε，那么对于 Follow(A) 中的每个终结符
b，也在A行b列填入该产生式。
自底向上
Bottom-Up: Shift-Reduce parsering (移位归约)
LR(0)
构建过程
使用项目(item) 来表示产生式中解析的位置：一个项通常由一个文法规则组成，其中点号
. (viable prefix) 在产生式中移动，表示当前解析进度的位置。- 移进 (Shift)：解析器读入下一个输入符号，并将这个符号以及转移到的新状态压入栈顶。此时，项目中的点号会相应地移动到下一个位置。
- Left string can be implemented by a stack. Top of the stack is the |
- Shift pushes a terminal on the stack
- 规约 (Reduce)：如果点号在最右边，意味着已经识别出一个规则的右侧部分，解析器应执行规约操作，即按照某个规则来规约栈顶的符号。
- pops 0 or more symbols off of the stack
- pushes a non-terminal on the stack
例题
Augmented grammar
在原始文法的基础上增加一个新的产生式，从而形成的扩展文法。目的是提供一个唯一的起始点，以便更容易地控制分析过程。
- 对现有文法，给开始符添加一个 E’，并把含有 的产生式拆开，进行展开。
Items
GOTO/ACTION parsing table
- r 的下标对应扩展文法中的序号
SLR(1)
Simple LR Parser
构建过程
步骤几乎同上，只是多一步通过 follow 集，解决 LR(0) 中的冲突
什么是冲突 → 解析器在解析过程中不能明确决定采取哪个动作
- 移入/归约冲突：在某个状态下，既可以执行移入操作（
.后面存在终结符），也可以执行归约（.在最后面）操作，而不考虑下一个输入符号。
- 归约/归约冲突：在某个状态下，有两条或更多的产生式都可以用来归约，而分析器无法决定使用哪一条。
例题
Augmented grammar
Items
FOLLOW set
- FOLLOW(S’) = { # }
- FOLLOW(E) = { +, ), # }
- FOLLOW(T) = { +, ), # }
- FOLLOW(F) = { +, *, ), # }
GOTO/ACTION parsing table
LR(1)
构建过程
关于向前搜索符 (lookahead)
（
a 即向前搜索符）- 文法开始符，a = $
（看前面的产生式，寻找紧跟在 后面的 B —— 先看前，再看后）
- β 为 ε：?? = a，（保持不变，没有其他符号可以看到）
- β 不为空
- β 是终结符：?? = β
- β 是 非终结符：?? = FIRST(β)
例题
Augmented grammar
Items
GOTO/ACTION parsing table
- r 根据向前搜索符决定