Open5

Rustでインタプリタ

Rust
keiya sasakikeiya sasaki

Lexerを作る

Lexerとは

Lexerとは、入力されたソースコードから構文を読み取り、意味のある形式に変換するための機能。
例えば、

let x = 5 + 5;

というソースコードが入力された時に、以下のようなデータを出力する。

Token::LET
Token::IDENT("x")
Token::ASSIGN
Token::INT(5)
Token::PLUS
Token::INT(5)

このようなデータを出力するようにしておくことで、Parserを作る時にASTを構築しやすくなる。
つまり下準備のようなものがLexer。

LexerをRustで作るときはenumとmatchを組み合わせることでスマートに実装できる。
以下のようなenumを定義しておくことで、

enum Token<'a> {
  LET, // let
  IDENT(&'a str), // 識別子
  INT(i64), // 数値
  ASSIGN, // =
  PLUS, // +
}

matchを使った時に簡単に条件分岐を行うことができる。

match lexer.ch {
  b'=' => Token::ASSIGN,
  b'+' => Token::PLUS,
  b'a'..b'z' | b'A'..b'Z' | b'_' => {
    // 識別子を受け取る処理
    // ...
    Token::IDENT(ident)
  },
  // ...etc
}
keiya sasakikeiya sasaki

Parserを作る(その1)

Parserとは

ParserとはLexerによって取得したTokenを使って、それぞれのTokenを仕分けしつつ、ASTを作成するもの。

Tokenを仕分けする間には、正しい順序で構文が入力されているかを確認しながら仕分けしていく。

例えば、

let x = 5;

が与えられると、以下のようなASTを出力する。

{
  Program: {
    Statements: [
      LetStatement {
          token: LET,
          name: Identifier { token: IDENT("x"), value: "x" },
      },
    ],
  },
}

このようにすることで、実際に入力されたコードを評価しやすくなる。

Let Statement

簡単にLet Statementとその識別子(変数名)をどのようにパースするのかをみてみる。

処理はそこまで複雑ではなく、以下のような順序で処理していく。

  1. Parser構造体にcurrent_token(現在読んでいるToken)とpeek_token(次に読み込むToken)をセットする
  2. 順番にTokenを読んでいく
  3. 読み込んだTokenがStatementかどうかを判断する
  4. StatementでかつLet Statementであれば、構文を解析しつつ、ASTを作っていく

AST作成の流れは以下のようになる。

  1. Let Statementの次の値がIdentifierになることを確認する(peek_tokenを確認する)
  2. Identifierかつstatementでなければ、expressionとして値を取得し、ASTに格納する
  3. そうでなければエラーをセットする

この処理により以下のようなASTが出来上がる。

{
  Program: {
    Statements: [
      LetStatement {
          token: LET,
          name: Identifier { token: IDENT("x"), value: "x" },
          value: LiteralExpresion { value: 5 } // IfExpression や InfixExpressionなどが入る
      },
    ],
  },
}

SWCの実装

Denoで使われているSWCのコンパイラをみるとenumで実装されているのが分かります。enumの利点としては、Goのinterfaceのような処理をより簡単にかけるとともに、強力なmatch式を使うことができるというのがあるのかなと思います。

https://github.com/swc-project/swc/blob/b2aec35eb6e482cf88f7b58531573ec8cd04bf12/ecmascript/ast/src/stmt.rs#L24-L95

keiya sasakikeiya sasaki

Parserを作る(その2)

前回までは、

let x = 5;

という構文を解析したが、次はIf式や演算などを表現していく。
仕組みは基本的には同じなので簡単に書いていく。

prefixとinfix

Pratt Parser (下向き演算子順位解析) という方法で実装していきます。これはTokenに優先順位をつけて、正しい順序でASTが構築できるようにするものです。例えば、*は +優先度が高いので、*は+よりも深いNodeに保存されます。

この解析方法の肝となるのがprefixとinfixです。

  • prefixは-5のようにリテラルの前に置く値です。
  • infixは5 + 10のようにリテラルの間に置かれる値です。

これらは以下のような形の構造体で表現されます。

struct PrefixExpression {
  operation: Token,
  right: Expression,
}

struct InfixExpression {
  left: Expression,
  operation: Token,
  right: Expression,
}

演算

Prefix

以下の式は、

let x = -5;

LetStatementとIdentifier("x")を解析し、次のtokenがAssign(=)であることを確認すると、-を前置として指定できる値かどうかを確認します。-は許可されたTokenなので、処理を進めます。次のTokenをみると、数値の5であるため、以下のようなASTが構築されます。

LetStatement {
  ...,
  PrefixExpression {
    operator: Minus,
    right: 5,
  },
}

Infix

以下の式は、

let x = 10 + 5;

LetStatementとIdentifier("x")を解析し、次のtokenがAssign(=)であることを確認すると、10を数値として解析する。ここまでは、以前の投稿と同じである。この次からが前回までと違う部分。

10を解析した後、次のtokenはPlusが存在します。その次には、また数値5が現れます。これをASTで表現すると以下のような感じになります。

LetStatement {
  ...,
  InfixExpression {
    left: 10,
    operator: Plus,
    right: 5,
  },
}

もしleftやrightがexpressionであった場合には、さらにExpression構造体がネストして、ASTを構築していきます。

優先順位

少し複雑な例をみていきます。

以下のような構文があった場合には、

let x = 10 * (5 + 10) - (-10);

次のような形の ASTが出来上がります。

LetStatement {
  ...,
  value: InfixExpression {
    left: InfixExpression {
      left: 10,
      operation: Asterisk,
      right: InfixExpression {
        left: 5,
        operator: Plus,
        right: 10,
      }
    },
    operator: Minus,
    right: PrefixExpression {
      operation: Plus,
      right: 10
    },
  },
}

Expressionには優先順位があるので、それを考慮しながら、優先順位の高いExpressionが深い位置に配置されます。

この例だと

10 * (5 + 10) - (-10);

10 < * のため、(5 + 10) を深い位置に配置します。
次に* > -であるため、(-10)は深い位置に配置されず、同じ階層のrightに配置されることになります。

(5 + 10)の部分はgroupとして解析をしています。(が数値の前に現れた時にprefixとして認識され、内部の5 + 10の部分を式として解析します。その後、10の次に)が存在するかを確認して、存在すれば解析完了ということになります。

IfExpression

if式は以下のような構文です。

let a = if (x) {
   x
}

if式もこれまでみてきたものと同じような感じで処理していきます。prefixにifTokenがついていれば、if式であると考えられるので、解析していきます。まずは次のTokenに(があるかどうかを確認します。(があればTokenを次に進めます。次にxの部分を解析していきます。これが終わると次のTokenに)が存在するかを確認します。存在していれば{内の部分を解析していきます。{内はBlockStatementであり、Block文はStatementであるため、Parserを作る(その1)のLetStatementの章で解説したようにStatements配列を順番に解析していく。

解析していくと以下のようなASTが出来上がる。

IfExpression {
  condition: Identifier { value: "x" },
  consequence: BlockStatement { statements: [ Identifier { value: "x" } ] },
  alternative: None, // else文。存在する場合はconsequenceと同じような内容になる
}

Function

Function、および呼び出し(CallExpression)もIfExpressionと同じように解析していく。

Functionについては、fnというリテラルがprefixにあれば、関数とみなし解析していく。

ASTは次のようになる。

let add = fn(x) {
  x
}

LetStatement {
  identifier: Identifier { value: "add" },
  value: FuncLiteral {
    args: [Identifier { value: "x" }],
    body: BlockStatement { statements: [Identifier { value: "x" }] },
  },
}

CallExpressionについては少し工夫が必要で、

add(9);

というCallExpressionがあった時に、まずaddをIdentifierとして解析し、次に(をinfixとして解析します。つまり中置演算子として(を扱い、これが存在するときは関数とみなします。(以降は引数になるので、引数を順番に処理していきます。カッコ内には様々な値が入りうる(add(5 + 5, a)など)ので個別に引数を解析していきます。このときの解析方法は既にみた式の解析方法と同じです。

keiya sasakikeiya sasaki

Parserを作る(その3)

これまでみてきた仕組みを実際にコードとしてみていきます。

Statement

まずstatementの解析は次のようになっています。

impl Parser {
  // ...
  pub(super) fn parse_statement(&mut self) -> Option<Statement> {
    match self.current_token {
      token::Token::LET => self.parse_let_statement(), // let文を解析する関数
      token::Token::RETURN => self.parse_return_statement(), // return文を解析する関数
      _ => self.parse_expression_statement(), // その他の式を解析する関数
    }
  }
  // ...
}

ここで呼び出されているself.parse_*_statement()は内部でself.parse_expression()を呼び出します。これは式をparseするためのエントリーポイントです。これまでみてきたようにそれぞれの文(statement)は必ず式を持つので、self.parse_expression()で解析していきます。

ReturnStatementについてはLetStatementとほぼ同じなので詳しく説明しませんが、

return 5 + 4;

という式があった時に、returnに続く式を解析し、ASTを構築していきます。

Expression

次にself.parse_expression()をみていきます。

impl Parser {
  // ...
  pub(super) fn parse_expression(&mut self, op: BinaryOperator) -> Option<Expression> {
    let mut left = match self.parse_prefix() {
      Some(expr) => expr,
      None => return None,
    };
    
    while !self.peek_token.is(token::Token::SEMICOLON) && op < self.peek_token.to_binary_operator() {
      self.next_token();
      left = match self.parse_infix(left) {
        Some(expr) => expr,
        None => return None,
      };
    }

    Some(left)
  }

  // prefixを解析する関数
  fn parse_prefix(&mut self) -> Option<Expression> {
    match &self.current_token {
      token::Token::IDENT(s) => self.parse_identifier(s.to_string()), // 変数
      token::Token::INT(int) => self.parse_integer_literal(*int), // 数値
      token::Token::TRUE | token::Token::FALSE => self.parse_boolean_literal(), // bool
      token::Token::BANG | token::Token::MINUS => self.parse_prefix_expression(), // `!`と`-`(`!5`や`-5`)を解析する
      token::Token::LPAREN => self.parse_grouped_expression(), // `(5 + 5)`のような式を解析する
      token::Token::IF => self.parse_if_expression(), // if式
      token::Token::FUNCTION => self.parse_func_literal(), // 関数定義
      _ => {
        self.no_prefix_parse_error(); // 未定義の場合はエラー
        return None;
      }
    }
  }

  // infixを解析する関数
  fn parse_infix(&mut self, left: Expression) -> Option<Expression> {
    match &self.current_token {
      token::Token::PLUS |
      token::Token::MINUS |
      token::Token::SLASH |
      token::Token::ASTERISK |
      token::Token::GT |
      token::Token::LT |
      token::Token::EQ |
      token::Token::NotEq => self.parse_infix_expression(left), // 5 + 5 や 5 == 5のような中置演算子を解析する
      token::Token::LPAREN => self.parse_call_expression(left), // CallExpressionを解析する
      _ => return None,
    }
  }
  // ...
}

self.parse_prefix()とself.parse_infix()は見ての通りだが、self.parse_expression()の次の部分は少し複雑。

while !self.peek_token.is(token::Token::SEMICOLON) && op < self.peek_token.to_binary_operator() {
  self.next_token();
  left = match self.parse_infix(left) {
    Some(expr) => expr,
    None => return None,
  };
}

これはpeek_token、つまり次に来るtokenと現在の演算子の優先順位を比較して、次の演算子の優先順位の方が高ければ、より深い位置にその式を配置する式である。

ここの処理によって、以下の式を

let x = 10 * (5 + 10) - (-10);

以下のようなASTに変換することが可能になる。

LetStatement {
  ...,
  value: InfixExpression {
    left: InfixExpression {
      left: 10,
      operation: Asterisk,
      right: InfixExpression {
        left: 5,
        operator: Plus,
        right: 10,
      }
    },
    operator: Minus,
    right: PrefixExpression {
      operation: Plus,
      right: 10
    },
  },
}