编译技术3-2

🎯 Formalisms for Syntax Analysis

📘 语法分析的形式体系

📌 Context-Free Grammars (CFG) 上下文无关文法

CFG（Context-Free Grammar）是一种用于描述编程语言语法结构的形式系统。 它比正则表达式更强大，能描述嵌套、递归等复杂结构。

📖 CFG 和文法 (CFG and Grammars)

  • CFG 是正则语言的严格超集。
  • 与正则表达式类似，但引入了递归规则。
  • 形式为：A → α，其中 A 是非终结符，α 是符号串（可包含终结符和非终结符）。

🔁 Derivations (推导)

推导描述了如何使用产生式将非终结符逐步替换成终结符，直到生成一个合法字符串。

📐 Derivation Step（推导步骤）

设 G 中有产生式：A → β

若存在字符串 v = αAγ，w = αβγ，其中 α、γ ∈ (VT ∪ VN)*， 那么称 v ⇒ w 是一个推导步骤。

一般形式：

1
X1 X2 ... Xi-1 Xi Xi+1 ... Xn  ⇒  X1 X2 ... Xi-1 Y1 Y2 ... Ym Xi+1 ... Xn

如果存在产生式 Xi → Y1 Y2 ... Ym。

📚 Function of Derivation（推导的作用）

CFG 规则定义了哪些 token 序列是语法合法的。

示例文法：

1
2
exp → exp op exp | (exp) | num
op → + | - | *

合法表达式：(34-3)*42 非法表达式：(34-3*42（括号未闭合）

🌳 Concrete and Abstract Syntax Trees（具体与抽象语法树）

  • 具体语法树（Concrete Syntax Tree）保留了所有文法细节。
  • 抽象语法树（Abstract Syntax Tree）更简洁，只表达程序结构要点。

⚠️ Ambiguity（歧义）

  • 如果一个字符串存在多种语法树（推导路径），则该文法是歧义的。

🧮 Derivation 示例

我们使用下列文法：

1
2
exp → exp op exp | (exp) | num
op → + | - | *

推导 (34-3)*42 的过程如下：

  1. exp
  2. ⇒ exp op exp （exp → exp op exp）
  3. ⇒ exp op num （exp → num）
  4. ⇒ exp * num （op → *）
  5. ⇒ (exp) * num （exp → (exp)）
  6. ⇒ (exp op exp) * num （exp → exp op exp）
  7. ⇒ (exp op num) * num （exp → num）
  8. ⇒ (num - num) * num （op → -）
  9. ⇒ (34 - 3) * 42 （exp → num）

最终我们得到合法表达式字符串：(34 - 3) * 42

✅ 小结 Summary

项目 内容
推导（Derivation） 用产生式替换非终结符，生成终结符串
单步推导 一个非终结符 → 替换为右部符号串
目标 从起始符号推导出一个全由终结符组成的串
应用 检查表达式是否合法，构造语法树

✅ 推导的传递闭包（The Transitive Closure of ⇒）

📌 英文原文定义：

The transitive closure of ⇒, denoted as ⇒*, is defined to be the transitive closure of the derivation step relation ⇒.
We say that:

α ⇒* β if and only if there exists a sequence of zero or more derivation steps (n ≥ 0):

α₀ ⇒ α₁ ⇒ α₂ ⇒ … ⇒ αₙ₋₁ ⇒ αₙ
such that α = α₀ and β = αₙ.

If n = 0, then this is a zero-step derivation, so: > α = β

📙 中文解释：

符号 ⇒ 表示“一步推导”，也就是用某条产生式将某个非终结符替换成产生式右侧。

而 ⇒* 表示“零步或多步推导（推导的传递闭包）”，表示从某个符号串出发，经过若干（包括0）步推导，能得到另一个符号串。

  • 若 α ⇒* β，意思是： 存在一个推导序列： 
    1
    α₀ ⇒ α₁ ⇒ α₂ ⇒ … ⇒ αₙ，且 α₀ = α，αₙ = β
  • 如果 n = 0，表示不需要任何推导，那么： 
    1
    α = β

✅ CFG 所定义的语言（The Language of a CFG）

📌 英文原文定义：

Let G be a context-free grammar with start symbol S.

The language defined by G, denoted as L(G), is:

L(G) = { s ∈ VT* | S ⇒* s }

Where:

  • S is the start symbol
  • VT is the set of terminal symbols (tokens)
  • s is a string made only of terminals
  • S ⇒* s means s can be derived from S using 0 or more steps

📙 中文解释：

设 G 是一个上下文无关文法（CFG），它的开始符号是 S，那么文法 G 所定义的语言（Language of G）是：

L(G) = { 所有从 S 推导出的只包含终结符的字符串 }

换句话说：

  • s ∈ VT*：s 是由终结符组成的字符串（也称作“句子”sentence）
  • S ⇒* s：从开始符号 S 出发，可以通过若干步推导，得到字符串 s

✅ 总结图示：

1
2
3
S ⇒* s      （s 是由终结符组成的句子）
↓
s ∈ L(G)    （s 属于文法 G 所定义的语言）

✅ 句型和句子（Sentential Form and Sentence）

📌 句型（Sentential Form）：

在上下文无关文法（CFG）中，句型（Sentential Form） 是指在推导过程中，某个符号串（可以包含终结符和非终结符的混合）可以由起始符号通过一系列推导步骤得到。

定义： - S 是 G 的开始符号，如果 S ⇒* α，其中 α ∈ (VN ∪ VT)*，则 α 是 G 的一个句型（sentential form）。

📌 句子（Sentence）：

当一个句型只包含 终结符 时，它被称为 句子（Sentence）。

  • 句子是一个 句型，如果它只包含终结符，那么它就是一个 句子。
  • 也就是说，句子是从起始符号 S 通过零或多步推导，最终得到的，只包含终结符的符号串。

✅ 例子：推导过程与句型

语言 G 的文法定义：

G: 

1
2
S → 0S1
S → 01

推导过程： 1. S ⇒ 0S1 （使用规则 S → 0S1） 2. 0S1 ⇒ 00S11 （再次使用 S → 0S1） 3. 00S11 ⇒ 000S111 （再次使用 S → 0S1） 4. … 直到最终： 5. 0n-1S1n-1 ⇒ 0n1n （n ≥ 1）

  • L(G) 是 G 所定义的语言： 
    1
    L(G) = { 0ⁿ1ⁿ | n ≥ 1 }

在这个例子中，S、0S1、00S11、000S111 都是 G 的句型，而 00001111 是 G 的一个句子。

✅ 设计一个文法（Designing a Grammar for L）

问题： 给定一个语言 L，该语言由 0 和 1 组成，语言中的每个字符串包含相同数量的 0 和 1。设计一个文法 G 来生成这个语言。

语言 L 的描述： - 每个字符串都有相同数量的 0 和 1。 - 例如：01, 0011, 000111, 等等。

文法 G 的设计：

  1. 文法定义： 

    1
    2
    3
    A → 0B | 1C
    B → 1 | 1A | 0BB
    C → 0 | 0A | 1CC

  2. 文法解释：

    • A 是开始符号，它可以推导为 0B 或 1C。
    • B 负责推导出包含 0 和 1 的部分，它可以通过 1 或递归的 0BB 来进行推导。
    • C 与 B 类似，负责推导出包含 0 和 1 的部分，使用类似的递归规则来生成。

  3. 推导过程：

    • A → 0B，然后通过 B 推导出 1，再使用规则继续推导直到达到字符串 0n1n 的形式。
    • 通过递归的定义，文法确保了每个字符串都有相同数量的 0 和 1。

✅ 总结：

  1. 句型（Sentential Form）：一个从起始符号出发，通过推导步骤得到的符号串，可以包含非终结符和终结符的混合。
  2. 句子（Sentence）：一种特殊的句型，其中只包含终结符，且可以通过零或多步推导得到。
  3. 设计文法（Grammar Design）：通过适当的文法规则，能够产生满足特定条件的语言，例如具有相同数量的 0 和 1 的语言。

✅ 解析树（Parse Trees）

📌 解析树的功能（Function of Parse Trees）：

  • 解析树是表示一个 符号串 结构的有用方式，它能有效地展示推导的过程。
  • 解析树用于将 推导过程 可视化，从而更直观地理解文法如何生成特定的句子。

📌 解析树的定义（Definition of Parse Tree）：

解析树是一个 有根的标记树，具有以下特性：

  • 根节点：标记为文法的 开始符号 S。
  • 叶节点：标记为 终结符 或 ε（空字符串）。
  • 非叶节点：标记为 非终结符。
  • 如果一个节点的标签是 A，并且该节点有 n 个子节点，其标签为 X1, X2, ..., Xn（可能是终结符或非终结符），则根据文法规则 A → X1X2…Xn ∈ P，表示该节点的推导规则是 A → X1 X2 … Xn。

✅ 推导和解析树（Derivations and Parse Trees）

  • 推导（Derivation） 是一系列句型的转换，通过应用一系列产生式来完成。
    • 例如，推导可以表示为：S ⇒ … ⇒ …。
  • 解析树 是推导过程的可视化表示。
    • 解析树的 根节点 是文法的 开始符号。
    • 对于一个产生式 X → Y1 Y2 ... Yn，在树中，X 节点会添加 Y1, Y2, ..., Yn 作为其子节点。

✅ 示例：推导和解析树

文法定义：

1
2
3
E → E + T | T
T → T * F | F
F → (E) | i

目标：推导并画出字符串 i + i * i 的推导过程及其解析树。

img

✅ 解析树（Parse Tree）总结

📌 解析树的特点：

  • 叶节点为终结符（Terminals at the leaves）：解析树的叶节点表示文法的终结符，也就是最终的符号，如字母、数字等。
  • 内部节点为非终结符（Non-terminals at the interior nodes）：非叶节点表示文法中的非终结符，它们是通过产生式规则来展开的部分。
  • 左-右遍历叶节点对应原始输入（A left-right traversal of the leaves is the original input）：对解析树进行左到右的遍历，叶节点的顺序即是原始输入的顺序，反映了语法规则如何生成这个字符串。

📌 解析树与推导（Derivations）的关系：

  • 一个字符串的解析树通常对应多个推导（A parse tree of a string corresponds in general to many derivations of the string）：同一个字符串可能通过不同的推导规则得到，但这些推导都可以生成相同的解析树。
  • 推导不唯一表示字符串结构，而解析树则可以（Derivations do not uniquely represent the structure of the strings they construct, while parse trees do）：推导过程是逐步的，而解析树则直接展示了语法结构。虽然不同的推导可能产生相同的结果，但解析树明确展示了结构。
  • 解析树抽象了推导的本质特征（Parse trees abstract the essential features of derivations）：解析树去除了推导过程中表面上的差异（如推导步骤的顺序），只保留了结构的本质，便于分析和理解。

📌 总结：

解析树是从语法推导到语法结构的桥梁，能够清晰地表示字符串如何通过文法生成。它提供了一种结构化的方式来表示语法的合法性，并且通过左-右遍历，能够重建原始输入。相比推导过程，解析树在结构的展示上更具唯一性和准确性。

✅ Leftmost Derivation 左推导

📌 定义（Definition）:

左推导（Leftmost derivation） 是指在每一步推导中，总是选择最左边的非终结符进行替换，直到最终得到一个只包含终结符的字符串。

  • 在一个推导步骤中，我们始终从最左边的非终结符开始进行替换。
  • 这种推导方法确保了每一步替换的顺序。

📌 左推导的步骤（Steps of Leftmost Derivation）:

在进行左推导时，假设我们有一个上下文无关文法（CFG）：

  • 选择当前最左边的非终结符。
  • 根据该非终结符的产生式规则替换它。
  • 继续重复这个过程，直到得到一个完全由终结符组成的句子。

📌 例子（Example）:

假设我们有以下文法 G(exp)，其中：

  • exp → exp op exp | (exp) | num
  • op → + | - | *

我们希望推导出字符串 "num+num"。

左推导的过程（Leftmost derivation steps）：

  1. 初始符号：exp
  2. 第 1 步：应用规则 exp → exp op exp
    • 结果：exp op exp
  3. 第 2 步：对最左边的 exp 应用规则 exp → num
    • 结果：num op exp
  4. 第 3 步：对 op 应用规则 op → +
    • 结果：num + exp
  5. 第 4 步：对剩下的 exp 应用规则 exp → num
    • 结果：num op num

最终，我们得到了目标字符串 "num + num"。

img

📌 左推导的特点（Features of Leftmost Derivation）：

  • 唯一性（Uniqueness）：每一步总是替换最左边的非终结符，这使得推导过程具有较强的规则性和一致性。
  • 清晰性（Clarity）：左推导有助于清晰地展示如何从起始符号逐步推导到目标字符串，特别适合编程语言的语法分析和编译器设计。
  • 应用广泛（Wide Application）：左推导在许多语法分析算法中都很重要，尤其是在自顶向下的解析（如 LL 解析）中。

📌 总结（Summary）：

左推导是一种在推导过程中始终选择最左边非终结符进行替换的推导方法。它保证了每一步推导的顺序，并通过逐步替换，最终得到目标字符串。左推导在编译原理和语法分析中起着至关重要的作用，能够清晰地展示语法的生成过程。

✅ Rightmost Derivation 右推导

📌 定义（Definition）:

右推导（Rightmost derivation） 是指在每一步推导中，总是选择最右边的非终结符进行替换，直到最终得到一个只包含终结符的字符串。

  • 在每个推导步骤中，我们始终从最右边的非终结符开始进行替换。
  • 这种推导方法确保了每一步替换的顺序。

📌 右推导的步骤（Steps of Rightmost Derivation）:

在进行右推导时，假设我们有一个上下文无关文法（CFG）：

  • 选择当前最右边的非终结符。
  • 根据该非终结符的产生式规则替换它。
  • 继续重复这个过程，直到得到一个完全由终结符组成的句子。

📌 例子（Example）:

假设我们有以下文法 G(exp)，其中：

  • exp → exp op exp | (exp) | num
  • op → + | - | *

我们希望推导出字符串 "num+num"。

右推导的过程（Rightmost derivation steps）：

  1. 初始符号：exp
  2. 第 1 步：应用规则 exp → exp op exp
    • 结果：exp op exp
  3. 第 2 步：对最右边的 exp 应用规则 exp → num
    • 结果：exp op num
  4. 第 3 步：对最右边的 exp 应用规则 exp → num
    • 结果：exp op num
  5. 第 4 步：对 op 应用规则 op → +
    • 结果：exp + num
  6. 第 5 步：对最左边的 exp 应用规则 exp → num
    • 结果：num + num

最终，我们得到了目标字符串 "num + num"。

img

📌 右推导的特点（Features of Rightmost Derivation）：

  • 唯一性（Uniqueness）：每一步总是替换最右边的非终结符，这使得推导过程具有较强的规则性和一致性。
  • 清晰性（Clarity）：右推导有助于清晰地展示如何从起始符号逐步推导到目标字符串，特别适合编程语言的语法分析和编译器设计。
  • 应用广泛（Wide Application）：右推导在许多语法分析算法中都很重要，尤其是在自底向上的解析（如 LR 解析）中。

📌 左推导与右推导的关系（Relation between Leftmost and Rightmost Derivation）：

  • 左推导和右推导对于它们所构造的字符串是唯一的。
  • 左推导和右推导与语法树有着唯一的对应关系。具体来说，左推导和右推导分别对应了不同类型的解析树：左解析树和右解析树。

📌 总结（Summary）：

右推导是一种在推导过程中始终选择最右边非终结符进行替换的推导方法。它保证了每一步推导的顺序，并通过逐步替换，最终得到目标字符串。右推导在编译原理和语法分析中起着至关重要的作用，能够清晰地展示语法的生成过程，并与右解析树对应。

✅ Abstract Syntax Trees (ASTs) 抽象语法树

📌 抽象语法树的需求 (Need for Abstract Syntax Trees):

  • 解析树（Parse Tree）包含了编译器生成可执行代码所需的过多信息。
    • 例如，解析树中包含了所有的语法细节，这些信息对编译过程并不都是必须的。
    • 许多编译器阶段实际上只需要“抽象”的信息，而不是过多的语法细节。

📌 AST与解析树的比较 (AST vs. Parse Tree):

  • 抽象语法树（AST）是解析树的一种简化形式。
    • 操作符通常出现在内部节点，而不是叶子节点。
    • 列表结构（例如数组、参数等）会被“展平”。
    • 语法细节（例如括号、逗号、分号等）被省略。
  • AST相比解析树更为简洁，并且更适合后续的编译阶段。它通过去除冗余信息，保留了程序的核心语法结构，使得编译器可以更高效地进行后续优化和生成目标代码。
img
img

📌 抽象语法树的定义 (Definition of Abstract Syntax Trees):

  • 抽象语法树（AST）是对源代码中的令牌序列的抽象表示。
  • AST去除了不必要的语法细节（如括号、逗号等），但保留了语法的核心信息（如运算符和操作数）。
  • 抽象语法树在编译过程的后期阶段，尤其是进行代码优化和生成目标代码时，比解析树更加高效。

📌 编译器中的抽象语法树 (AST in Compilers):

  • 解析器（Parser）会通过解析树的所有步骤，但通常只会构造抽象语法树（AST）。
  • 抽象语法树更适合后续编译阶段的处理，因为它简化了不必要的语法信息，帮助提高编译效率。

📌 例子 (Example):

假设我们有以下文法，描述了一个简单的 if 语句：

1
2
3
4
<statement> → <if-stmt> | other
<if-stmt>   → if (<exp>) <statement> <else-part>
<else-part> → else <statement> | ε
<exp>       → 0 | 1

给定字符串 “if (0) other else other”，我们可以构造它的 解析树 和 抽象语法树。

  1. 解析树 (Parse Tree)：
    • 解析树会详细地显示所有的语法规则，包括 if、( )、else 等所有符号。
    • 树的结构可能会非常详细，包含了所有的符号和非终结符。
  2. 抽象语法树 (Abstract Syntax Tree, AST)：
    • 抽象语法树会去除语法细节，如括号、空格和冗余符号。
    • 内部节点将包含 if 语句和条件表达式，而不是 if、(、) 等符号的每个细节。
    对于 “if (0) other else other” 的 AST 可能如下：
img

📌 AST的优点 (Advantages of AST):

  1. 简洁性（Simplicity）：AST省去了冗余的语法信息，保留了程序的核心逻辑。
  2. 易于处理（Easier to Process）：去除语法细节后，AST更加简洁和清晰，便于后续的优化和代码生成。
  3. 高效性（Efficiency）：AST比解析树更为高效，因为它减少了不必要的层级和细节，能够帮助编译器更高效地进行后续处理。

📌 总结 (Summary):

  • 抽象语法树（AST） 是程序代码的一种简化表示，它去除了语法细节，如括号、逗号、分号等，保留了程序的核心逻辑结构。
  • AST 是编译器生成目标代码时的主要数据结构，它简洁、清晰、高效，适合进行后续的优化和代码生成。
  • 解析树虽然详细，但包含了编译时并不需要的冗余信息，而 AST 提供了更精简、更有用的结构。

✅ 挑战：歧义 (Challenge: Ambiguity)

📌 什么是歧义 (What is Ambiguity)?

  • 歧义在语法中指的是某个字符串可以通过多种不同的方式被解析（即有多个不同的解析树或最左推导/最右推导）。
  • 歧义可能会导致解析器无法确定哪种语法规则应用于某个输入。

📌 歧义的例子 (Example of Ambiguity)：

考虑下面的算术运算文法：

1
E → E - E | E * E | (E) | i

对于字符串 “i - i * i”，它有两种不同的解析树，分别对应两种不同的最左推导：

  1. 第一个推导 (First Derivation)：

    1
    E → E * E → E - E * E → i - E * E → i - i * E → i - i * i

  2. 第二个推导 (Second Derivation)：

    1
    E → E - E → i - E → i - E * E → i - i * E → i - i * i
    img
img

如上所示，“i - i * i” 有两个不同的解析树，说明此文法是歧义的。

📌 歧义的定义 (Definition of Ambiguity)：

  • 歧义文法 (Ambiguous Grammar)：如果存在一个字符串 w 属于某文法 G 的语言 L(G)，且这个字符串可以生成多个不同的解析树（或最左推导/最右推导），那么这个文法 G 就是歧义的。

📌 歧义的挑战 (Challenge of Ambiguity)：

  • 歧义是编程语言语法中常见的问题。例如：
    • 优先级和结合性 (Precedence and Associativity)：运算符的优先级和结合性可能导致歧义。比如，i - i * i，* 和 - 的优先级问题。
    • 悬挂的 else 问题 (Dangling Else Problem)：if-then-else 语句的嵌套可能导致歧义，编译器无法确定 else 应该匹配哪个 if。

📌 如何解决歧义 (How to Deal with Ambiguity)：

  1. 使用消歧规则 (Disambiguating Rules)：
    • 消歧规则是对文法进行调整，指定优先级或明确某些语法规则的应用，从而消除歧义。
    • 例如，对于算术运算，可以通过指定乘法的优先级高于加法来消除歧义。
  2. 重写文法 (Rewriting the Grammar)：
    • 重写文法可以通过增加语法规则来避免歧义。例如，通过将运算符的优先级和结合性在文法中显式地表示出来。
    • 优先级：可以为文法中的运算符增加明确的优先级规则。例如，将乘法运算优先于加法运算。
    • 结合性：对于同一优先级的运算符，可以通过重写规则指定它们的结合性（如左结合或右结合）。

✅ 消歧规则 (Disambiguating Rule)

📌 什么是消歧规则 (What is a Disambiguating Rule)?

  • 消歧规则指的是一种规则，规定在遇到歧义时，应该选择哪个解析树作为正确的解析树。换句话说，消歧规则帮助我们在多个解析树中确定一个最符合要求的树。

📌 消歧规则的例子 (Examples of Disambiguating Rules)：

  • 规则 1 (Rule 1)： 强制 \* 的优先级高于 -，即乘法的优先级大于减法。
  • 规则 2 (Rule 2)： - 运算符是左结合的。也就是说，在没有明确优先级指示时，- 操作符会从左到右结合。
img

📌 不改变文法，使用消歧规则 (Disambiguating Rule Without Changing Grammar)：

  • 通过消歧规则，语法结构不再单纯依赖于文法本身的定义，语法结构的正确性需要借助额外的规则来判断。
  • 消歧规则让我们在文法仍然保持不变的情况下，明确每个操作符的优先级和结合性，避免歧义。

📌 重写文法 (Rewriting the Grammar)：

  • 为了使文法明确构造正确的解析树，我们可以重写文法，通过引入优先级和结合性规则来消除歧义。
  • 重写文法实际上是将文法拆解成多个部分，每个部分对应不同的优先级。

📌 重写文法的示例 (Example of Rewriting Grammar)：

我们开始时的文法是：

1
E → E - E | E * E | (E) | i

我们通过引入优先级来修改这个文法：

  1. 添加优先级：将 * 和 - 操作符分组，分别定义不同的规则。

    1
    2
    3
    E → E - E | T
    T → T * T | F
    F → (E) | i

    现在，乘法 \* 操作符的优先级高于减法 - 操作符。这样，i - i \* i 不再是歧义的，且其左推导如下：

    1
    E → E - E → T - E → F - E → i - E → i - T → i - T * F → … → i - i * i

  2. 添加结合性 (Associativity)：我们还可以通过改变规则的递归顺序来添加结合性。

    • 左结合 (Left Associative)：左递归规则使操作符从左到右结合。
    • 右结合 (Right Associative)：右递归规则使操作符从右到左结合。
    1
    2
    3
    4
    E → E-T| T
    T → T*F | F
    F → (E)| i

    例如，i - i - i 的左推导是：

    1
    E → E - T → E - T - T → T - T - T → … → i - i - i

📌 结合性与递归 (Associativity and Recursion)：

  • 通过左递归和右递归规则来控制操作符的结合性：
    • 左递归规则：使操作符左结合。
    • 右递归规则：使操作符右结合。

📌 最终重写文法 (Final Rewritten Grammar)：

1
2
3
E → E - T | T
T → T * F | F
F → (E) | i

为了处理 i - i \* i 和 i - i - i，我们已经为它们定义了正确的推导和结构：

  • i - i \* i 的左推导：

    1
    E → E - E → T - E → F - E → i - E → i - T → i - T * F → … → i - i * i

  • i - i - i 的左推导：

    1
    E → E - T → E - T - T → T - T - T → … → i - i - i

📌 总结 (Summary)：

  • 消歧规则允许我们在多个可能的解析树中选择正确的解析树，通常是通过指定操作符的优先级和结合性来实现的。
  • 重写文法是通过改变文法规则来明确指定优先级和结合性，从而消除歧义。
  • 例如，通过引入优先级规则将 \* 放在 - 之前，我们能够确保运算的正确性并消除歧义。

✅ Summary / 总结

Syntax Analysis (Parsing) / 语法分析：

  • Syntax analysis (parsing) extracts the structure from the tokens produced by the scanner. / 语法分析从扫描器生成的词法单元中提取结构。
  • It transforms a linear sequence of tokens into a hierarchical structure that reflects the syntactic structure of the source code. / 它将一个线性顺序的词法单元转换为反映源代码语法结构的层次结构。

Context-Free Grammars (CFGs) / 上下文无关文法：

  • Languages are usually specified by context-free grammars (CFGs). / 语言通常由上下文无关文法 (CFGs) 来指定。
  • CFGs define the syntax of a language by specifying how to generate strings of symbols. / CFGs通过指定如何生成符号串来定义语言的语法。

Parse Tree / 解析树：

  • A parse tree shows how a string can be derived from a grammar. / 解析树显示了如何从文法中推导出一个字符串。
  • It represents the full syntactic structure of a string according to the grammar. / 它代表了根据文法的完整语法结构。

Ambiguity in Grammar / 文法中的歧义：

  • A grammar is ambiguous if a string has more than one parse tree. / 如果一个字符串有多个解析树，则文法是歧义的。
  • Ambiguity arises when the same string can be derived in different ways, leading to different syntactic structures. / 当同一个字符串可以通过不同方式推导出来，导致不同的语法结构时，就会出现歧义。

Abstract Syntax Tree (AST) / 抽象语法树：

  • Abstract syntax trees (ASTs) contain an abstract representation of a program's syntax. / 抽象语法树 (ASTs)包含程序语法的抽象表示。
  • Unlike parse trees, ASTs omit certain syntactic details, such as parentheses or semicolons, focusing only on the essential structure of the program. / 与解析树不同，AST省略了某些语法细节，如括号或分号，只关注程序的核心结构。

Key Concepts / 关键概念：

  • Parse Tree represents every detail of the syntax and is closely tied to the grammar. / 解析树表示语法的每个细节，并与文法紧密相关。
  • Abstract Syntax Tree (AST) simplifies the structure, omitting less important syntactic details while preserving the core syntax. / 抽象语法树 (AST)简化了结构，省略了不重要的语法细节，同时保留了核心语法。
  • Ambiguity in a grammar leads to multiple parse trees for the same string. / 文法歧义会导致同一个字符串有多个解析树。

This summary encapsulates the fundamental concepts of syntax analysis, grammar structures, ambiguity, and the role of abstract syntax trees in understanding program syntax. / 该总结概括了语法分析、文法结构、歧义性以及抽象语法树在理解程序语法中的作用。