深入理解 swc - 第三部分，语法分析
序言
这是深入理解 swc 的第三部分，来探究 swc 的语法分析阶段。语法分析是将源代码转换成抽象语法树（Abstract Syntax Tree，AST）的过程。
上下文无关语法
在开始深入理解 JavaScript 源代码语法分析之前，我们首先需要理解 JavaScript 的语法结构。JavaScript 的语法是由一个名为 "Technical Committee 39"（TC39）的组织定义的，它在 ECMA-262 标准中得到了明确的规定。ECMA-262 是 JavaScript 的官方标准，它采用了一种称为 "上下文无关语法"（Context-Free Grammar，CFG）的形式化语法来明确规定了 JavaScript 的语法规则。
上下文无关语法是一种广泛应用于编程语言的形式化语法，它的基本规则实际上非常直观，而且易于理解。尽管对于所有的细节进行深入的理解可能需要一定的时间，但我们可以通过一个简单的例子来初步感受其工作原理。
我们来看一下 JavaScript 中 if 语句的语法定义：
IfStatement :
if ( Expression ) Statement else Statement
if ( Expression ) Statement [lookahead ≠ else]
在这个例子中，IfStatement，Expression 和 Statement 都是非终结符，它们代表的是可以进一步展开或替换的语法结构。 if，(，) 和 else 这些则是终结符，它们是语法结构中具体的字面符号。
这个规则的含义是，一个 IfStatement 可以由 if ( Expression ) Statement else Statement 这样的结构组成，也可以由 if ( Expression ) Statement 这样的结构组成，但后者的情况下，Statement 后面不能直接跟着 else。
所以，一个包含 else 的完整的 IfStatement 可以是 if (x > 0) y = 1; else y = 0;，而不包含 else 的 IfStatement 可以是 if (x > 0) y = 1;。
这就是上下文无关语法在定义 JavaScript 语法时的基本应用。希望这个简单的例子能帮助你理解上下文无关语法的基本工作原理。
语法分析方法
在开始我们的语法分析之前，我们需要先了解几种主要的语法分析方法。这些方法主要分为两大类：自顶向下分析和自底向上分析。
-
自顶向下分析（Top-down parsing）：自顶向下分析从开始符号出发，按照语法规则逐步扩展产生式，直到派生树的叶子节点与输入符号相匹配。常用的自顶向下分析方法包括：
- 递归下降分析（Recursive Descent Parsing）：递归下降分析通过递归程序实现语法规则。从语法的开始符号出发，根据给定的输入，尝试应用所有可能的匹配规则进行扩展。该方法可能需要回溯，因此在某些情况下可能效率较低。
- 预测分析（Predictive Parsing）：预测分析是一种不需要回溯的递归下降分析。它要求语法为LL(1)文法，即对于每个非终结符和输入符号，只有一个产生式可以应用，这使得分析过程更为高效。
-
自底向上分析（Bottom-up parsing）：自底向上分析从输入符号出发，逐步将其归约为开始符号。常用的自底向上分析方法包括：
- 移位归约分析（Shift-Reduce Parsing）：移位归约分析通过移位（将输入符号推入栈）和归约（用某个产生式将栈顶符号替换为非终结符）操作来构建抽象语法树。其中，最常见的自底向上分析方法是LR分析，它使用预先生成的解析表来指导分析过程。
- LR分析（LR Parsing）：LR分析是一种广泛使用的自底向上分析方法，其中最常见的变体是SLR（Simple LR）、LALR（Look-Ahead LR）和CLR（Canonical LR）分析。这些分析方法根据预先生成的解析表，使用移位和归约操作来构建抽象语法树。
在JavaScript编译器 swc 中，采用的是递归下降分析方法。递归下降分析是一种自顶向下的分析策略，它构建的是源代码的派生树的左深版本。这种分析策略在编译器设计中广受欢迎，理由如下：
- 简单直观：递归下降解析器直观且容易编写和理解。我们只需要为每个非终结符写一个函数，这个函数会尝试各种可能的选择来解析输入。这种方法的直观性使得编译器的开发和维护变得更简单。
- 高度灵活：递归下降解析器可以轻松处理那些不能被其他解析技术（如LL或LR）处理的语法规则。它可以处理左递归、非上下文自由语法和语言的其他复杂性质。
- 预测解析：如果我们处理的语法是LL(1)，即在任何情况下，我们都可以通过查看下一个输入符号来决定采取哪个产生式，那么我们可以创建一个非回溯的递归下降解析器，这是一种高效的解析器。
- 错误处理：递归下降解析器在发现错误时可以提供有用的反馈。由于解析器的控制流与语法结构紧密匹配，因此递归下降解析器可以尝试修复错误，或至少提供有关错误性质和位置的详细信息。
- 扩展性好：递归下降分析方法对于语法规则的扩展非常友好。如果需要引入新的非终结符号，我们只需要添加对应的解析函数即可。
然而，值得一提的是，递归下降解析也有其局限性。例如，它无法直接处理左递归的语法规则，而且在某些情况下可能需要回溯。但是有一些技术可以帮助我们克服这些局限，如消除左递归和使用预测分析等。
总的来说，递归下降分析是一种强大而灵活的工具，它在处理一些复杂的语法规则方面具有明显的优势。这也是为什么许多现代编译器，包括 swc，选择使用它的原因。
Parser 结构体
swc 的语法分析器是通过一个名为 Parser 的结构体来定义的。下面是其定义：
pub struct Parser<I: Tokens> {
state: State,
input: Buffer<I>,
}
Parser 结构体中主要存储着两种数据，state 和 input。state 表示当前解析器的内部状态，而 input 则表示正在处理的由词法分析器得到的单词序列。
State 结构体的定义如下：
struct State {
labels: Vec<JsWord>,
/// 赋值表达式的起始位置。
potential_arrow_start: Option<BytePos>,
found_module_item: bool,
/// AST节点的起始位置及其尾部逗号的跨度。
trailing_commas: AHashMap<BytePos, Span>,
}
State 结构体中包含了一些用于追踪解析过程状态的字段，例如 labels 用于存储标签符号（例如循环的标签），potential_arrow_start 用于记录可能的箭头函数表达式的起始位置，found_module_item 用于标记是否找到模块条目，trailing_commas 用于存储 AST 节点的起始位置及其尾部逗号的跨度。
我们在词法分析部分提到过，swc 中的词法分析器被定义为 Lexer 结构体。在这里，Tokens 类型就是对应的词法分析器，它提供了一个可迭代的 Token 序列。
Buffer 结构体建立在词法分析器之上，用于管理和追踪输入的单词序列。其中 iter 就是传入的词法分析器，prev_span 用于存储上一个 Token 的 Span，cur 和 next 分别用于存储当前和下一个 Token。
struct Buffer<I: Tokens> {
iter: I,
/// 上一个Span of the previous token.
prev_span: Span,
cur: Option<TokenAndSpan>,
/// Peeked token
next: Option<TokenAndSpan>,
}
解析 if-else 语句
在上述内容中，我们已经阐述了 JavaScript 中 if 语句的语法定义。接下来，我们将深入探讨 swc 如何通过 parse_if_stmt 函数实现其解析过程。
fn parse_if_stmt(&mut self) -> PResult<IfStmt> {
let start = cur_pos!(self);
assert_and_bump!(self, "if");
let if_token = self.input.prev_span();
expect!(self, '(');
let ctx = Context {
ignore_else_clause: false,
..self.ctx()
};
let test = self
.with_ctx(ctx)
.include_in_expr(true)
.parse_expr()
.map_err(|err| {
Error::new(
err.span(),
SyntaxError::WithLabel {
inner: Box::new(err),
span: if_token,
note: "Tried to parse the condition for an if statement",
},
)
})?;
expect!(self, ')');
let cons = {
// Prevent stack overflow
crate::maybe_grow(512 * 1024, 2 * 1024 * 1024, || {
// Annex B
if !self.ctx().strict && is!(self, "function") {
// TODO: report error?
}
let ctx = Context {
ignore_else_clause: false,
..self.ctx()
};
self.with_ctx(ctx).parse_stmt(false).map(Box::new)
})?
};
let alt = if self.ctx().ignore_else_clause {
None
} else {
let mut cur = None;
let ctx = Context {
ignore_else_clause: true,
..self.ctx()
};
let last = loop {
if !eat!(self, "else") {
break None;
}
if !is!(self, "if") {
// As we eat `else` above, we need to parse statement once.
let last = crate::maybe_grow(512 * 1024, 2 * 1024 * 1024, || {
let ctx = Context {
ignore_else_clause: false,
..self.ctx()
};
self.with_ctx(ctx).parse_stmt(false)
})?;
break Some(last);
}
// We encountered `else if`
let alt = self.with_ctx(ctx).parse_if_stmt()?;
match &mut cur {
Some(cur) => {
self.adjust_if_else_clause(cur, Box::new(Stmt::If(alt)));
}
_ => {
cur = Some(alt);
}
}
};
match cur {
Some(mut cur) => {
if let Some(last) = last {
self.adjust_if_else_clause(&mut cur, Box::new(last));
}
Some(Stmt::If(cur))
}
_ => last,
}
}
.map(Box::new);
let span = span!(self, start);
Ok(IfStmt {
span,
test,
cons,
alt,
})
}
下面是该函数的主要步骤：
-
获取开始位置：
let start = cur_pos!(self);获取当前位置信息，这将用于后续生成语法树节点的位置信息。 -
解析
if关键字：assert_and_bump!(self, "if");确认当前 token 是if并移动到下一个 token。 -
解析条件表达式：先期待一个
(，然后解析括号里的表达式作为if语句的条件。 -
解析
if语句的主体：期待一个)结束条件表达式，然后解析后面的语句作为if语句的主体。 -
解析
else分支：如果存在else关键字，则继续解析else后面的语句。这部分需要特别注意，因为else可能后接if形成else if，这是一个嵌套的if语句，需要递归处理。 -
生成
IfStmt结构体：最后生成IfStmt结构体，包含了if语句的所有信息，包括位置信息、条件表达式、主体语句和else分支（如果有的话）。
这个函数的实现中，你可以看到 swc 采用的是递归下降分析的方法，对于每个结构，都有一个对应的 parse_* 函数进行处理。对于嵌套的结构，例如 else if，则通过递归调用 parse_if_stmt 来处理。
处理左递归和语法二义性问题
编程语言中的二义性是指某个语句在语法分析时有多种有效的解释。当编程语言中的语法规则没有明确区分某些结构或表达式时，就容易导致二义性。以下是一些编程语言中容易出现二义性的情况：
-
运算符优先级不明确：当编程语言的语法规则未明确指定运算符的优先级时，可能导致二义性。例如，
a + b * c这个表达式在不考虑优先级的情况下可以被解释为(a + b) * c或a + (b * c)。 -
运算符结合性不明确：当编程语言的语法规则未明确指定运算符的结合性时，可能导致二义性。例如，
a - b - c这个表达式在不考虑结合性的情况下可以被解释为(a - b) - c或a - (b - c)。 -
悬挂 else 问题：这是一种常见的二义性问题，涉及到 if-else 语句的嵌套。例如，以下代码片段：
-
语法规则冲突：当编程语言中的一组语法规则彼此冲突时，可能导致二义性。例如，在 JavaScript 中的 return 语句和自动插入分号 (ASI, Automatic Semicolon Insertion) 机制的冲突。
当定义二元运算的上下文无关语法时，我们可能会很自然地想要这样去定义：
AdditiveExpression :
PrimaryExpression + PrimaryExpression
PrimaryExpression - PrimaryExpression
PrimaryExpression * PrimaryExpression
PrimaryExpression / PrimaryExpression
然而，这种定义方式存在两个主要问题：
-
左递归问题：左递归就是在语法规则的定义中，左侧的非终结符直接或间接地出现在右侧的推导式的开始位置，形成递归，如
AdditiveExpression : AdditiveExpression + PrimaryExpression。这在某些解析技术（例如递归下降解析）中会导致无限循环。 -
优先级问题：上述定义会使得所有的操作符都具有相同的优先级，而在实际的编程语言中，不同的操作符具有不同的优先级，如在大多数语言中，乘法和除法操作符的优先级高于加法和减法。
为了解决这些问题，ECMA-262 规范（即 JavaScript 的规范）采用了另一种定义方式，即为每个优先级创建一个新的非终结符，并确定其正确的顺序。例如：
MultiplicativeExpression :
PrimaryExpression
| MultiplicativeExpression * PrimaryExpression
| MultiplicativeExpression / PrimaryExpression
AdditiveExpression :
MultiplicativeExpression
| AdditiveExpression + MultiplicativeExpression
| AdditiveExpression - MultiplicativeExpression
按照这种定义方式，乘法和除法会比加法和减法先进行运算，从而正确地实现了操作符的优先级。此外，通过将每个优先级的表达式定义为一个新的非终结符，这种定义方式避免了左递归的问题。
因此，在解析如 1 + 2 * 3 的表达式时，根据上述的语法定义，解析器会将其解析为 1 + (2 * 3)，而不是 (1 + 2) * 3。这是因为 MultiplicativeExpression 的优先级高于 AdditiveExpression，所以解析器会首先解析乘法表达式 2 * 3，然后再解析加法表达式 1 + (2 * 3)。
二元表达式的解析流程
尽管 ECMA-262 已经通过上下文无关文法定义解决了左递归和优先级问题，但 swc 并没有按照这一定义逐步解析。相反，它选择通过明确设定算术运算符的优先级来实现递归解析。这种方法使得解析过程更加直观，易于理解，并且方便扩展新的运算符。
impl BinaryOp {
pub fn precedence(self) -> u8 {
match self {
BinaryOp::EqEq => 6,
BinaryOp::NotEq => 6,
BinaryOp::EqEqEq => 6,
BinaryOp::NotEqEq => 6,
BinaryOp::Lt => 7,
BinaryOp::LtEq => 7,
BinaryOp::Gt => 7,
BinaryOp::GtEq => 7,
BinaryOp::LShift => 8,
BinaryOp::RShift => 8,
BinaryOp::ZeroFillRShift => 8,
BinaryOp::Add => 9,
BinaryOp::Sub => 9,
BinaryOp::Mul => 10,
BinaryOp::Div => 10,
BinaryOp::Mod => 10,
BinaryOp::BitOr => 3,
BinaryOp::BitXor => 4,
BinaryOp::BitAnd => 5,
BinaryOp::LogicalOr => 1,
BinaryOp::LogicalAnd => 2,
BinaryOp::In => 7,
BinaryOp::InstanceOf => 7,
BinaryOp::Exp => 11,
BinaryOp::NullishCoalescing => 1,
}
}
}
swc 对算术运算符优先级的解析在 swc_ecma_parser/src/parser/expr/ops.rs 文件中实现，其工作原理概述如下：
-
parse_bin_expr函数开始解析二进制表达式。首先尝试解析一个一元表达式（parse_unary_expr）。如果if语句或其他二元操作符（instanceof或BinOp）后面有错误，那么会尝试进行错误恢复。否则，它将开始递归地解析二元操作符。 -
在函数
parse_bin_op_recursively中，一个无限循环开始了。这个函数会一直解析，直到遇到一个操作符的优先级低于当前优先级的操作符为止。在循环中，首先调用parse_bin_op_recursively_inner，该函数判断当前操作符的优先级是否低于最小优先级min_prec。如果是，那么它就会停止解析并返回结果。否则，就会继续解析右边的表达式，并返回新的左表达式next_left和优先级next_prec。 -
在函数
parse_bin_op_recursively_inner中，首先检查当前的操作符。如果它的优先级大于min_prec，那么解析右操作数。然后，用左操作数、当前操作符和右操作数创建一个新的BinExpr并返回。否则，函数返回当前的左操作数和None。 -
最后，
parse_unary_expr函数负责解析一元表达式。根据当前的 token，它能解析出前缀或后缀的增量（++）、减量（--）、一元操作符或await表达式。
整个过程中，如果遇到优先级较低的操作符，解析器就会停止解析当前的表达式，并将剩余的部分留给调用者进行处理。这就是所谓的操作符优先级解析算法，也被称为 "Pratt" 解析器。
抽象语法树
语法解析器的主要任务是将源代码转换为抽象语法树（AST），它是源代码的层次结构表示，为后续的编译或解释阶段提供了结构化的信息。以 JavaScript 的 if 语句为例，swc 在抽象语法树中将其定义为 IfStmt 结构体。
IfStmt 结构体的定义如下：
pub struct IfStmt {
pub span: Span,
pub test: Box<Expr>,
#[cfg_attr(feature = "serde-impl", serde(rename = "consequent"))]
pub cons: Box<Stmt>,
#[cfg_attr(feature = "serde-impl", serde(default, rename = "alternate"))]
pub alt: Option<Box<Stmt>>,
}
每个字段的作用如下：
-
span：这是一个Span类型的字段，它包含了此if语句在源代码中的位置信息。对于编译器错误报告或者代码生成阶段，这个信息是很重要的。 -
test：这是一个Box<Expr>类型的字段，它表示if语句的条件表达式。这个表达式的结果将决定是执行if语句的 "then" 分支（即cons字段），还是 "else" 分支（即alt字段，如果存在的话）。 -
cons：这是一个Box<Stmt>类型的字段，它表示if语句的 "then" 分支，即当test的结果为true时执行的语句。 -
alt：这是一个Option<Box<Stmt>>类型的字段，它表示if语句的 "else" 分支，即当test的结果为false时执行的语句。如果if语句没有 "else" 分支，那么这个字段的值就是None。
通过这样的结构，swc 能够准确地表示 JavaScript 中的 if 语句，并且能够很方便地处理 if 语句在语法树中的转换和操作。