Syntactic analysis
Review of Lexical Analysis
Aims of syntactic analysis
The task of the syntactic analysis phase is essentially to build a parse tree
⮚with the root: the distinguished symbol, “<program>” or whatever
⮚The leaves: the sequence of tokens from the lexical analysis phase
⮚with each branch point in the tree sanctioned by a rule form the grammar
详细解读：语法分析的目标 (Aims of Syntactic Analysis)
语法分析 (Syntactic Analysis) 是编译器中非常关键的阶段，其主要任务是根据词法分析阶段生成的 Token 序列，建立一棵 解析树 (Parse Tree)，以检查代码的结构是否符合上下文无关文法 (CFG) 的规则。
1. 解析树的组成
根节点 (Root)：
• 解析树的根节点是 区分符号 (Distinguished Symbol)，通常是文法的起始符号，比如 <program>。
• 示例：对于一个程序代码，根节点会对应 <program>，表示代码的最顶层结构。
叶子节点 (Leaves)：
• 解析树的叶子节点是由 词法分析器 生成的 Token 序列。
• 每个叶子节点代表源代码中的一个词法单元，比如关键字 (if, while)、标识符 (num, count)、常量 (123)、运算符 (=, +) 等。
分支点 (Branch Points)：
• 解析树中的每个分支点对应一个 文法规则 的应用。
• 每个分支点的出现都受到 上下文无关文法 (CFG) 的规则 “批准 (Sanctioned)”。
• 这些分支点代表代码的结构，比如表达式、语句块、函数定义等。
2. 解析树的结构示意
假设语句 int count = 5;，其对应的文法如下：
<program> → <declaration>
<declaration> → <type> <identifier> = <value> ;
<type> → int
<identifier> → count
<value> → 5
对应的解析树：
<program>
|
<declaration>
/ | \
<type> <identifier> <value>
| | |
int count 5
解析树说明：
根节点：<program> 是文法的起始符号，表示程序的起始结构。
分支点：<declaration> 由文法规则拆分成 <type>, <identifier> 和 <value>。
叶子节点：int, count 和 5 分别是 Token，对应于词法分析器的输出。
3. 语法分析的目标
• 检查语法正确性：确保源代码的结构遵循定义的文法规则。
• 构建解析树：解析树是后续编译阶段 (如语义分析、代码生成) 的基础。
• 验证 Token 序列：确保词法分析器生成的 Token 序列可以按照文法规则被解析。
• 错误定位：如果代码不符合语法规则，语法分析器可以报告并定位语法错误。
4. 解析树的用途
• 输入到语义分析器：在解析树的基础上进行类型检查、变量声明验证等语义分析。
• 生成中间代码：通过解析树将程序转换为中间表示形式。
• 优化代码：解析树有助于优化代码结构，如合并常量、简化表达式等。
5. 语法分析方法
语法分析一般通过 上下文无关文法 (CFG) 进行，主要分为两种方式：
- 自顶向下分析 (Top-Down Parsing)：
• 从文法的起始符号开始，逐步展开文法规则，尝试匹配 Token 序列。
• 例：LL(1) 分析器。
- 自底向上分析 (Bottom-Up Parsing)：
• 从 Token 序列开始，逐步归约成文法的起始符号。
• 例：LR(0)、SLR(1)、LALR(1)、LR(1) 分析器。
总结
• 语法分析的目标 是构建一棵 解析树，它表示源代码的语法结构。
• 根节点 是文法的起始符号，叶子节点 是词法分析阶段的 Token 序列。
• 每个分支点都由文法规则批准，确保代码结构符合语法规则。
• 解析树是编译器后续阶段的基础，如语义分析、中间代码生成和代码优化。
Aims of syntactic analysis
⮚Perhaps carry out semantic checks at the same time
⮚This phase may instead generate a sequence of machine code instructions, or some other intermediate form of the program, a bit at a time
⮚If the syntax of the program is invalid, to give as many and as helpful error messages as possible
详细解读：语法分析的目标 (Aims of Syntactic Analysis)
语法分析 (Syntactic Analysis) 是编译器中的一个关键阶段，主要目标是分析源代码的结构，并确保其符合语法规则。同时，这一阶段还可能执行其他重要任务，如语义检查、代码生成及错误处理。以下是具体内容的解读：
1. 执行语义检查 (Semantic Checks)
• 含义：在语法分析的过程中，部分语义检查可以同步进行。
• 示例：
• 确保 变量已声明：例如，int x = y + 1; 中，如果 y 未声明，就会触发错误。
• 类型检查：例如，确保赋值语句 int x = "hello"; 中的类型不匹配错误被检测到。
• 运算符和操作数的合法性：如整数加法操作符 + 不能用于字符串连接。
• 目的：尽早发现代码中的语义错误，减少后续阶段的错误传播，提高编译器的效率。
2. 生成中间代码或机器码 (Code Generation or Intermediate Form)
• 含义：语法分析不仅限于构建 解析树 (Parse Tree)，它还可以逐步生成中间代码或机器码指令。
• 工作流程：
• 将程序分解为符合语法的单元。
• 逐步生成对应的机器码或中间代码。
• 示例：
• 语句 a = b + c 在语法分析阶段可以直接转化为：
LOAD b
ADD c
STORE a
• 生成的 中间代码 可以被优化器进一步处理，然后由目标代码生成器转化为可执行的机器代码。
• 优势：
• 减少额外阶段的复杂性。
• 通过逐步代码生成，帮助早期发现错误。
3. 错误检测与报告 (Error Handling)
• 含义：如果代码的语法无效，语法分析器的任务之一是提供尽可能多且有用的错误信息。
• 目标：
• 检测错误：识别代码中违反语法规则的部分。
• 定位错误：指出错误发生的具体位置。
• 提供建议：提供明确的错误消息和修正建议，帮助开发者快速定位并解决问题。
• 示例错误信息：
• Syntax Error: Missing ';' at line 5
• Unexpected token '}' at line 10
• Type Error: 'int' cannot be assigned to 'string' at line 8
• 优质错误报告的特点：
• 尽量一次性检测多个错误：而不是在每个错误处停止分析。
• 提供上下文信息：解释错误的来源和修正方法。
• 用户友好：错误消息易于理解，避免技术细节过多。
总结
语法分析的目标包括以下三个方面：
同步语义检查：在语法分析时检测变量声明、类型检查等语义错误。
生成代码：逐步生成机器码指令或中间代码，为后续的优化和目标代码生成提供基础。
错误处理：在语法错误出现时，提供尽可能多且有帮助的错误信息，帮助开发者快速定位和修复问题。
语法分析阶段不仅仅是构建解析树，它为编译器的后续阶段提供了结构化的程序表示，同时提高了编译器的错误检测能力和用户友好性。
Review: parsing tree
解析树 (Parsing Tree) 详细解读
Two Parsing Strategy
Search problem – given the root and the leaves, to find the appropriate labeled branch points in between
●Top-down parsing strategy