解析器
我们要构建的解析器称为递归下降解析器， 它是沿着语法向下并构建 AST 的手工过程。
解析器开始很简单，它持有源代码、词法分析器和从词法分析器消费的当前词法单元。
rust
pub struct Parser<'a> {
/// 源代码
source: &'a str,
lexer: Lexer<'a>,
/// 从词法分析器消费的当前词法单元
cur_token: Token,
/// 前一个词法单元的结束范围
prev_token_end: usize,
}
impl<'a> Parser<'a> {
pub fn new(source: &'a str) -> Self {
Self {
source,
lexer: Lexer::new(source),
cur_token: Token::default(),
}
}
pub fn parse(&mut self) -> Program<'a> {
Ok(Program {
node: Node {
start: 0,
end: self.source.len(),
}
body: vec![]
})
}
}辅助函数
当前词法单元 cur_token: Token 保存从词法分析器返回的当前词法单元。 我们将通过添加一些辅助函数来导航和检查这个词法单元，使解析器代码更清晰。
rust
impl<'a> Parser<'a> {
fn start_node(&self) -> Node {
let token = self.cur_token();
Node::new(token.start, 0)
}
fn finish_node(&self, node: Node) -> Node {
Node::new(node.start, self.prev_token_end)
}
fn cur_token(&self) -> &Token {
&self.cur_token
}
fn cur_kind(&self) -> Kind {
self.cur_token.kind
}
/// 检查当前索引是否有词法单元 `Kind`
fn at(&self, kind: Kind) -> bool {
self.cur_kind() == kind
}
/// 如果我们在 `Kind` 处则前进
fn bump(&mut self, kind: Kind) {
if self.at(kind) {
self.advance();
}
}
/// 前进任何词法单元
fn bump_any(&mut self) {
self.advance();
}
/// 如果我们在 `Kind` 处则前进并返回 true，否则返回 false
fn eat(&mut self, kind: Kind) -> bool {
if self.at(kind) {
self.advance();
return true;
}
false
}
/// 移动到下一个词法单元
fn advance(&mut self) {
let token = self.lexer.next_token();
self.prev_token_end = self.cur_token.end;
self.cur_token = token;
}
}解析函数
DebuggerStatement 是最简单的语句解析，所以让我们尝试解析它并返回一个有效的程序
rust
impl<'a> Parser<'a> {
pub fn parse(&mut self) -> Program {
let stmt = self.parse_debugger_statement();
let body = vec![stmt];
Program {
node: Node {
start: 0,
end: self.source.len(),
}
body,
}
}
fn parse_debugger_statement(&mut self) -> Statement {
let node = self.start_node();
// 注意：从词法分析器返回的词法单元是 `Kind::Debugger`，我们稍后会修复这个。
self.bump_any();
Statement::DebuggerStatement {
node: self.finish_node(node),
}
}
}所有其他解析函数都建立在这些基本辅助函数之上， 例如在 swc 中解析 while 语句：
rust
// https://github.com/swc-project/swc/blob/554b459e26b24202f66c3c58a110b3f26bbd13cd/crates/swc_ecma_parser/src/parser/stmt.rs#L952-L970
fn parse_while_stmt(&mut self) -> PResult<Stmt> {
let start = cur_pos!(self);
assert_and_bump!(self, "while");
expect!(self, '(');
let test = self.include_in_expr(true).parse_expr()?;
expect!(self, ')');
let ctx = Context {
is_break_allowed: true,
is_continue_allowed: true,
..self.ctx()
};
let body = self.with_ctx(ctx).parse_stmt(false).map(Box::new)?;
let span = span!(self, start);
Ok(Stmt::While(WhileStmt { span, test, body }))
}解析表达式
表达式的语法深度嵌套且递归， 这可能导致长表达式上的栈溢出（例如在这个 TypeScript 测试中），
为了避免递归，我们可以使用一种称为"Pratt 解析"的技术。更深入的教程可以在这里找到，由 Rust-Analyzer 的作者编写。 Rome 中也有一个 Rust 版本。
列表
有很多地方我们需要解析由标点符号分隔的列表，例如 [a, b, c] 或 {a, b, c}。
解析列表的代码都很相似，我们可以使用模板方法模式 通过使用 trait 来避免重复。
rust
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/parser/parse_lists.rs#L131-L157
fn parse_list(&mut self, p: &mut Parser) -> CompletedMarker {
let elements = self.start_list(p);
let mut progress = ParserProgress::default();
let mut first = true;
while !p.at(JsSyntaxKind::EOF) && !self.is_at_list_end(p) {
if first {
first = false;
} else {
self.expect_separator(p);
if self.allow_trailing_separating_element() && self.is_at_list_end(p) {
break;
}
}
progress.assert_progressing(p);
let parsed_element = self.parse_element(p);
if parsed_element.is_absent() && p.at(self.separating_element_kind()) {
// 一个缺失的元素
continue;
} else if self.recover(p, parsed_element).is_err() {
break;
}
}
self.finish_list(p, elements)
}这种模式还可以防止我们陷入无限循环，特别是 progress.assert_progressing(p);。
然后可以为不同的列表提供实现细节，例如：
rust
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/syntax/expr.rs#L1543-L1580
struct ArrayElementsList;
impl ParseSeparatedList for ArrayElementsList {
fn parse_element(&mut self, p: &mut Parser) -> ParsedSyntax {
match p.cur() {
T![...] => parse_spread_element(p, ExpressionContext::default()),
T![,] => Present(p.start().complete(p, JS_ARRAY_HOLE)),
_ => parse_assignment_expression_or_higher(p, ExpressionContext::default()),
}
}
fn is_at_list_end(&self, p: &mut Parser) -> bool {
p.at(T![']'])
}
fn recover(&mut self, p: &mut Parser, parsed_element: ParsedSyntax) -> RecoveryResult {
parsed_element.or_recover(
p,
&ParseRecovery::new(
JS_UNKNOWN_EXPRESSION,
EXPR_RECOVERY_SET.union(token_set!(T![']'])),
),
js_parse_error::expected_array_element,
)
}
fn list_kind() -> JsSyntaxKind {
JS_ARRAY_ELEMENT_LIST
}
fn separating_element_kind(&mut self) -> JsSyntaxKind {
T![,]
}
fn allow_trailing_separating_element(&self) -> bool {
true
}
}覆盖语法
在覆盖语法中详细介绍，有时我们需要将 Expression 转换为 BindingIdentifier。像 JavaScript 这样的动态语言可以简单地重写节点类型：
javascript
https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/lval.js#L11-L26但在 Rust 中，我们需要进行结构体到结构体的转换。一个简洁的方法是使用 trait。
rust
pub trait CoverGrammar<'a, T>: Sized {
fn cover(value: T, p: &mut Parser<'a>) -> Result<Self>;
}该 trait 接受 T 作为输入类型，Self 作为输出类型，所以我们可以定义以下内容：
rust
impl<'a> CoverGrammar<'a, Expression<'a>> for BindingPattern<'a> {
fn cover(expr: Expression<'a>, p: &mut Parser<'a>) -> Result<Self> {
match expr {
Expression::Identifier(ident) => Self::cover(ident.unbox(), p),
Expression::ObjectExpression(expr) => Self::cover(expr.unbox(), p),
Expression::ArrayExpression(expr) => Self::cover(expr.unbox(), p),
_ => Err(()),
}
}
}
impl<'a> CoverGrammar<'a, ObjectExpression<'a>> for BindingPattern<'a> {
fn cover(obj_expr: ObjectExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
...
BindingIdentifier::ObjectPattern(ObjectPattern { .. })
}
}
impl<'a> CoverGrammar<'a, ArrayExpression<'a>> for BindingPattern<'a> {
fn cover(expr: ArrayExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
...
BindingIdentifier::ArrayPattern(ArrayPattern { .. })
}
}然后对于任何需要将 Expression 转换为 BindingPattern 的地方， 调用 BindingPattern::cover(expression)。
TypeScript
所以你已经完成了 JavaScript，想要挑战解析 TypeScript？ 坏消息是没有规范， 但好消息是 TypeScript 解析器在一个单独的文件中 🙃。
JSX vs TSX
对于以下代码，
javascript
let foo = <string> bar;如果这是 tsx，这是一个语法错误（未终止的 JSX）， 但它是带有 TSTypeAssertion 的正确 VariableDeclaration。
向前看
在某些地方，解析器需要向前看并 peek 超过一个词法单元以确定正确的语法。
TSIndexSignature
例如，要解析 TSIndexSignature，考虑以下两种情况：
typescript
type A = { readonly [a: number]: string }
^__________________________^ TSIndexSignature
type B = { [a]: string }
^_________^ TSPropertySignature对于 type A，在第一个 { 处，我们需要 peek 5 个词法单元（readonly、[、a、: 和 number）才能确定 它是 TSIndexSignature 而不是 TSPropertySignature。
为了使这成为可能且高效，词法分析器需要一个缓冲区来存储多个词法单元。
箭头表达式
在覆盖语法中讨论过， 当在 SequenceExpression 后面找到 => 词法单元时，我们需要从 Expression 转换为 BindingPattern。
但这种方法对 TypeScript 不起作用，因为 () 中的每一项都可能有 TypeScript 语法，有太多情况需要覆盖，例如：
typescript
(<x>a, b as c, d!);
(a?: b = {} as c!) => {};建议研究 TypeScript 源代码来处理这个特定情况。相关代码是：
typescript
function tryParseParenthesizedArrowFunctionExpression(
allowReturnTypeInArrowFunction: boolean,
): Expression | undefined {
const triState = isParenthesizedArrowFunctionExpression();
if (triState === Tristate.False) {
// It's definitely not a parenthesized arrow function expression.
return undefined;
}
// If we definitely have an arrow function, then we can just parse one, not requiring a
// following => or { token. Otherwise, we *might* have an arrow function. Try to parse
// it out, but don't allow any ambiguity, and return 'undefined' if this could be an
// expression instead.
return triState === Tristate.True
? parseParenthesizedArrowFunctionExpression(
/*allowAmbiguity*/ true,
/*allowReturnTypeInArrowFunction*/ true,
)
: tryParse(() =>
parsePossibleParenthesizedArrowFunctionExpression(allowReturnTypeInArrowFunction),
);
}
// True -> We definitely expect a parenthesized arrow function here.
// False -> There *cannot* be a parenthesized arrow function here.
// Unknown -> There *might* be a parenthesized arrow function here.
// Speculatively look ahead to be sure, and rollback if not.
function isParenthesizedArrowFunctionExpression(): Tristate {
if (
token() === SyntaxKind.OpenParenToken ||
token() === SyntaxKind.LessThanToken ||
token() === SyntaxKind.AsyncKeyword
) {
return lookAhead(isParenthesizedArrowFunctionExpressionWorker);
}
if (token() === SyntaxKind.EqualsGreaterThanToken) {
// ERROR RECOVERY TWEAK:
// If we see a standalone => try to parse it as an arrow function expression as that's
// likely what the user intended to write.
return Tristate.True;
}
// Definitely not a parenthesized arrow function.
return Tristate.False;
}总之，TypeScript 解析器使用向前看（快速路径）和回溯的组合来解析箭头函数。