简单的 CFG 语法分析方法

有些时候吧人就是贱，想写点吃力不讨好的东西。今天就写点上下文无关文法(Context-Free Grammar, CFG)的两个算法吧。

请注意，这部分不是我擅长的领域，我只是因为好奇这方面的事情而自学过。如有纰漏，还请海涵。

本篇内容偏多偏杂，请善用右侧的 ToC 来快速导航 :)

文法（Grammar）

首先先明确一下，文法（Grammar）和语法（Syntax）是两个东西。

• 文法是形式化的约定，使用一套符号系统来进行严格定义，为编译器或者解析器所使用的形式化规则
• 语法则为语言设计者所定义的语言规范

我们在这里要做的是讨论解析器/编译器所使用的形式化规则，那么我们的重点则是文法而不是语法。

文法的形式化表达

先放一个例子在这里，免得无聊吧

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

无聊是不无聊了，但是看到符号就食欲不振。让我们更加深入一些：

终结符 Terminal Symbols

如其所述，终结符意味着终结，代表着该符号不可被再分解，例如 * ( ) id 等等等。（这里的 id 代指标识符，例如变量名或者关键字等）

以我们上文所给的例子：

• id：标识符（如变量名、数字等）。
• +, *：运算符。
• (, )：括号。
• $：输入结束符（过程中添加的标记，表示输入的末尾）。

再回去看上文的例子，就感觉清晰不少了不是吗？好，我们继续深入这个例子中各项的意义。

非终结符 Non-Terminal Symbols

非终结符是文法中需要进一步推导的符号，通常使用大写符号来表示：例如例子中的 E T，它们代表语法结构中的抽象概念，如表达式、项、因子等。

继续以我们上文提到的例子：

• E：表达式 Expression 。
• E'：表达式后缀（用于消除左递归）。
• T：项 Term。
• T'：项后缀（用于消除左递归）。
• F：因子 Factor。

其他符号

要是你仔细点的话，会看到这里还有其他符号：

• →
  • 推导关系，左侧是非终结符，右侧是可能产生的表达式
  • 如果不方便编写的话写作 := 也是可以的
• |
  • 表达或关系，意味着该非终结符可以被推导为多个可能的符号序列
  • 例子：E' → + T E' | ε 即 E' 可以被推导为 + T E' 或者 ε
• ε
  • 空推导，意义为可以被推导为什么都不做
  • 还是以刚刚的例子，E' → ε 就可以认为 E' 什么都不做，则 E' 可以直接消失

产生式 Productions

基于上述规则，我们可以组合出更复杂的东西：产生式。

产生式定义了对于非终结符号的定义规则，我们来看一些产生式例子：

• E → T E'
  • 该产生式由一个项 T 和一个后缀构成 E'
    • T 处理项（如乘法、除法等）
    • E' 处理加法或减法的后缀
• F → ( E ) | id
  • 因子 F 可以是括号内的表达式 E 或标识符 id
• E' → + T E' | ε
  • 后缀 E' 可以是 + T E' 也可以是 ε

等等，E, T, F 又是什么东西？！

文法符号 Grammar Symbol

请注意，接下来有些概念可能会产生混淆：接下来的概念基本上都属于数学表达式的分层结构，而不是数字运算的优先级顺序

• 因子，F，Factor
  • 原子单元，他们无法被进一步分解，例如 id，(E)
• 项，T，Term
  • 由 F 乘法除法组成的单元，例如 T → F * F
• 表达式，E，Expression
  • 由 T 通过加法减法组成的单元，例如 E → T + T

特别的，id 是在我们当前的语境下引入的新原子单元，称之为标识符 identifier

等等，好像混进来奇怪的东西？(E) 又是啥玩意儿？

考虑到一个表达式可以被分解成由 F 构造的产生式，我们将分解这个步骤使用 () 进行封装成为一个整体，这样可以减轻各方面的压力

如果再允许 (E) 进行分解，那么很可能导致文法中出现左递归和更复杂的结构

举个例子单独说明 F → (E) 的情况，在这种情况下不能认为包含了 E 所以可以无限推导下去，因为 E 必须被完全推导为具体的符号：

F → ( E ) → ( T E' ) → ( F T' E' ) → ( id * F T' E' ) → ... → ( id * id )

以上的例子最终将 F → ( E ) 分解成为了具体的符号序列作为因子的实例