パーサー

構築するパーサーは再帰下り構文解析と呼ばれます。これは、文法を下って進み、抽象構文木（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();
        // NOTE: レキサから返されるトークンは `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 Parsing（プレット・パーシング）」という手法を使用できます。より詳しいチュートリアルはこちらにあり、Rust-Analyzer の作者によるものです。そして、Rust 版は Rome にあります。

// 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 では、構造体同士の変換が必要です。これをきれいかつ簡潔に行う方法として、トレイトを使用するのが良いでしょう。

rust

pub trait CoverGrammar<'a, T>: Sized {
    fn cover(value: T, p: &mut Parser<'a>) -> Result<Self>;
}

このトレイトは入力タイプ 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 と TSX

次のコードについて考えてみましょう。

javascript

let foo = <string> bar;

このコードが tsx であれば構文エラー（未終了のJSX）になりますが、VariableDeclaration として正しく解釈され、TSTypeAssertion となります。

ライフアヘッド

特定の場面では、正しい文法を判断するために、一つ以上のトークンを先読み（ラフアヘッド）する必要があります。

TSIndexSignature

たとえば TSIndexSignature をパースする場合、以下の二つのケースを考慮してください：

typescript

type A = { readonly [a: number]: string }
           ^__________________________^ TSIndexSignature

type B = { [a]: string }
           ^_________^ TSPropertySignature

type A の最初の { では、readonly, [, a, :, number の5つのトークンを先読みする必要があります。そうしないと、TSIndexSignature か TSPropertySignature か判断できません。

これを可能かつ効率的に実現するため、レキサには複数のトークンを保存するバッファが必要です。

アロー式

カバー文法でも議論されているように、シーケンス式の後に => トークンが見つかったとき、Expression を BindingPattern に変換する必要があります。

しかし、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) {
    // これは確実に括弧付きアローファンクション式ではありません。
    return undefined;
  }

  // すでにアローファンクションであることが確定している場合、続く `=>` や `{` トークンは必要ありません。一方、アローファンクションの可能性がある場合、一時的にパースしてみますが、あいまいさを許さず、式として解釈できる可能性があれば `undefined` を返します。
  return triState === Tristate.True
    ? parseParenthesizedArrowFunctionExpression(
        /*allowAmbiguity*/ true,
        /*allowReturnTypeInArrowFunction*/ true,
      )
    : tryParse(() =>
        parsePossibleParenthesizedArrowFunctionExpression(allowReturnTypeInArrowFunction),
      );
}

//  True        -> ここでは確実に括弧付きアローファンクション式を期待している。
//  False       -> ここでは括弧付きアローファンクション式は *ありえない*。
//  Unknown     -> ここでは括弧付きアローファンクション式 *あり得る*。推測的に先読みし、該当しなければロールバックする。
function isParenthesizedArrowFunctionExpression(): Tristate {
  if (
    token() === SyntaxKind.OpenParenToken ||
    token() === SyntaxKind.LessThanToken ||
    token() === SyntaxKind.AsyncKeyword
  ) {
    return lookAhead(isParenthesizedArrowFunctionExpressionWorker);
  }

  if (token() === SyntaxKind.EqualsGreaterThanToken) {
    // エラー回復の調整：
    // 単独の `=>` が見つかった場合、ユーザーが意図したのはアローファンクション式だと仮定し、それをパースしようとする。
    return Tristate.True;
  }
  // 確実に括弧付きアローファンクションではない。
  return Tristate.False;
}

要するに、TypeScript パーサーは先読み（高速パス）とバックトラッキングを組み合わせて、アローファンクションをパースしています。

パーサー ​

ヘルパー関数 ​

パース関数 ​

式のパース ​

リスト ​

カバー文法 ​

TypeScript ​

JSX と TSX ​

ライフアヘッド ​

TSIndexSignature ​

アロー式 ​

パーサー

ヘルパー関数

パース関数

式のパース

リスト

カバー文法

TypeScript

JSX と TSX

ライフアヘッド

TSIndexSignature

アロー式