Elixirで作成するインタプリタ -字句解析編-

January 26, 2020

この記事はGo 言語でつくるインタプリタ(以下書籍と呼びます)を参考に Elixir でインタプリタを実装していきます。

この書籍は Go 言語でインタプリタの作成を進めるとともにどのように処理系を構築していくかということが学べる。かなり評判の良い書籍だそうで。

文中に記載のソースコードをそのまま写経するのは面白みに欠けるというか、その内飽きてしまいそうなので（おい）今回は内容をほぼそのまま Elixir で実装していきます。

Go と Elixir はオブジェクト指向言語か関数型言語かという点で大きく異なります。

書籍の Go のソースコードを読みながら書いているのでどうしてもそっちに寄ってしまいそうですが、出来るだけ関数型らしいプログラミングをしていきたいと思います。

書籍内では C 言語風の構文の monkey という独自の言語のインタプリタの作成を目標としています。

Githubはこちらです。コードの全体像を確認したい方はこちらから確認してください。

開発の流れ

書籍の流れと同様に

字句解析
構文解析
評価
インタプリタの拡張

という流れで進めていきます。今回のこの記事は 1. 字句解析 です

以下のセクションで（）内に書かれているのは Go 言語でつくるインタプリタとの対応ページになります。

トークン定義（p3）

defmodule Token do
  defstruct [:type, :literal]

  def new(type, literal), do: %Token{type: type, literal: literal}

  def token_type() do
    %{
      illegal: "illegal",
      eof: "eof",

      #識別子 + リテラル
      ident: "ident",
      int: "int",

      #演算子
      assign: "=",
      plus: "+",

      #デリミタ
      comma: ",",
      semicolon: ";",

      lparen: "(",
      rparen: ")",
      lbrace: "{",
      rbrace: "}",

      #キーワード
      function: "function",
      let: "let",
    }
  end
end

書籍とは異なり Token を作成する関数も同時に実装しています。書籍では Lexer のパッケージ内に定義していますが、Token モジュールに定義する方が適していると思ったので

字句解析のテストを書く（p4）

ゴールを明確にするために先にテストを書きます。

defmodule LexerTest do
  use ExUnit.Case
  doctest Lexer

  test "test next token" do
    input = '=+(){},;'

    lexer = Lexer.new(input)

    [
      %Token{type: Token.token_type.assign,    literal: "="},
      %Token{type: Token.token_type.plus,      literal: "+"},
      %Token{type: Token.token_type.lparen,    literal: "("},
      %Token{type: Token.token_type.rparen,    literal: ")"},
      %Token{type: Token.token_type.lbrace,    literal: "{"},
      %Token{type: Token.token_type.rbrace,    literal: "}"},
      %Token{type: Token.token_type.comma,     literal: ","},
      %Token{type: Token.token_type.semicolon, literal: ";"},
      %Token{type: Token.token_type.eof,       literal: ""},
    ]
    |> Enum.reduce(lexer, fn %Token{type: type, literal: literal}, acc_lexer ->
      acc_lexer = acc_lexer |> Lexer.read_token()
      assert type == Enum.at(acc_lexer.result, -1).type
      assert literal == Enum.at(acc_lexer.result, -1).literal
      acc_lexer
    end)
  end
end

書籍のものと流れは似ていますが、細かい部分で異なります。それは次に作成する Lexer モジュールの実装の違いによります。

Lexer の作成

defmodule Lexer do
  defstruct [:input, :ch, position: 0, read_position: 1, result: []]

  def new(input) do
    ch = Enum.at(input, 0)
    %Lexer{input: input, ch: [ch]}
  end

  def read_token(lexer) do
    new_token =
      case lexer.ch do
        '=' -> Token.new(Token.token_type.assign,    to_string(lexer.ch))
        ';' -> Token.new(Token.token_type.semicolon, to_string(lexer.ch))
        '(' -> Token.new(Token.token_type.lparen,    to_string(lexer.ch))
        ')' -> Token.new(Token.token_type.rparen,    to_string(lexer.ch))
        ',' -> Token.new(Token.token_type.comma,     to_string(lexer.ch))
        '+' -> Token.new(Token.token_type.plus,      to_string(lexer.ch))
        '{' -> Token.new(Token.token_type.lbrace,    to_string(lexer.ch))
        '}' -> Token.new(Token.token_type.rbrace,    to_string(lexer.ch))
        nil -> Token.new(Token.token_type.eof,       "")
      end

    lexer
    |> Map.update!(:result, fn result -> result ++ [new_token] end)
    |> update_lexer()
  end

  defp update_lexer(lexer) do
    if lexer.read_position >= String.length(to_string(lexer.input)) do
      lexer
      |> Map.update!(:ch, fn _ch -> nil end)
    else
      lexer
      |> Map.update!(:ch, fn _l -> [Enum.at(lexer.input, lexer.read_position)]  end)
      |> Map.update!(:position, &(&1 + 1))
      |> Map.update!(:read_position, &(&1 + 1))
    end
  end

end

割とシンプルかと思います。

細かい部分ですが、Map.replace!を使えばよくね？と思われるかもしれません。 Map.update!と Map.replace! はどちらも Map の指定した key に対応する value を更新する関数です。使い分けによって違う処理をしてるとパッと見たときに感じるのは嫌だったので、Map.replace!で事足りる部分も Map.update! を使用しています。

テストケース拡張（p9）

実際に input を渡す test を追加します。

  test "test lexer" do
    input =
     'let five = 5;
      let ten = 10;

      let add = fn(x, y) {
        x + y;
      };

      let result = add(five, ten);'

    lexer = Lexer.new(input)

    [
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.function,   literal: "fn"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.plus,       literal: "+"},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "result"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.eof,        literal: ""},
    ]
    |> Enum.reduce(lexer, fn %Token{type: type, literal: literal}, acc_lexer ->
      acc_lexer = acc_lexer |> Lexer.read_token()
      assert type == Enum.at(acc_lexer.result, -1).type
      assert literal == Enum.at(acc_lexer.result, -1).literal
      acc_lexer
    end)
  end
end

関数の切り出し

ここで気づきます。「あっ、このままの設計じゃこの先に対応できない」

理由は後述で、先ほどの read_token/2 ないの case の部分を別の関数として切り出します。

  defp create_new_token(ch) do
    case ch do
      '=' -> {:ok, Token.new(Token.token_type.assign,    to_string(lexer.ch))}
      ';' -> {:ok, Token.new(Token.token_type.semicolon, to_string(lexer.ch))}
      '(' -> {:ok, Token.new(Token.token_type.lparen,    to_string(lexer.ch))}
      ')' -> {:ok, Token.new(Token.token_type.rparen,    to_string(lexer.ch))}
      ',' -> {:ok, Token.new(Token.token_type.comma,     to_string(lexer.ch))}
      '+' -> {:ok, Token.new(Token.token_type.plus,      to_string(lexer.ch))}
      '{' -> {:ok, Token.new(Token.token_type.lbrace,    to_string(lexer.ch))}
      '}' -> {:ok, Token.new(Token.token_type.rbrace,    to_string(lexer.ch))}
      nil -> {:ok, Token.new(Token.token_type.eof,       "")}
      ch  ->
        if is_letter?(ch) do
          {:not_found, :identifier}
        else
          {:not_found, :illegal}
        end
    end
  end

  defp is_letter?(ch) when is_integer(ch) do
    ch = [ch]
    (('a'<= ch) and (ch <= 'z')) or (('A'<= ch) and (ch <= 'Z')) or (ch == '_')
  end

  defp is_letter?(ch) do
    (('a'<= ch) and (ch <= 'z')) or (('A'<= ch) and (ch <= 'Z')) or (ch == '_')
  end

case 文に 1 つ追加されています。これにより Identifier に対応します。

先ほどの理由というのは is_letter? 部で true だった場合に result 以外の部分も更新する必要があるためです。（→lexerを更新する範囲が異なる）

identifier に対応する（p10）

変更前の実装では case の結果によって lexer を更新する範囲が異なっていたために先ほどの関数に切り出した関数を使って、以下で説明するようにパターンマッチングを利用して条件分岐させます。

 def read_token(lexer) do
    lexer = skip_space(lexer) #後述
    case create_if_const_token_type(lexer.ch) do
      {:ok, new_token} ->
          lexer
          |> Map.update!(:result, fn result -> result ++ [new_token] end)
          |> update_lexer()

      {:error, :identifier} ->
          literal = read_identifier(lexer)
          literal_length = String.length(literal)
          case Token.get_keyword_token_type_if_exist(literal) do
            {:ok, keyword_token_type} ->
              new_token = Token.new(keyword_token_type, literal)
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer(literal_length)
            {:error, _} ->
              new_token = Token.new(Token.token_type.ident, literal)
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer(literal_length)
          end
      {:error, :illegal} ->
          new_token = Token.new(Token.token_type.illegal, lexer.ch)
          lexer
          |> Map.update!(:result, fn result -> result ++ [new_token] end)
          |> update_lexer()
    end
  end

identifier の対応のために新たに関数を定義しています。

  defp read_identifier(lexer) do
    lexer.input
    |> Enum.drop(lexer.position)
    |> Enum.take_while(&(is_letter?(&1)))
    |> to_string()
  end

read_identifierは現在の位置から続く単語を丸っと取得します。例えば

lexer.input = 'hoge foo bar'
lexer.ch = 'h' #一文字目

の時 hoge を取得します。

また、以下のように先ほどの update_lexer を指定の回数分 lexer の位置をずらすように変更します。

  #指定の回数lexerを進める
  defp update_lexer(lexer, count \\ 1) do
    IO.puts(lexer.read_position)
    IO.puts(lexer.ch)
    updated_lexer =
      if lexer.read_position >= String.length(to_string(lexer.input)) do
        lexer
        |> Map.update!(:ch, fn _ch -> nil end)
      else
        lexer
        |> Map.update!(:ch, fn _l -> [Enum.at(lexer.input, lexer.read_position)]  end)
        |> Map.update!(:position, &(&1 + 1))
        |> Map.update!(:read_position, &(&1 + 1))
      end

    case count do
      1 -> updated_lexer
      c -> update_lexer(updated_lexer, c-1)
    end
  end

キーワードに対応（p11）

  def keywords() do
    %{
      "fn"  => "function",
      "let" => "let"
    }
  end

  def get_keyword_token_type_if_exist(literal) do
    keywords = keywords()
    keyword = Enum.filter(keywords, fn {key, _value} -> key == literal end)
    if keyword != [] do
      {_, keyword_token_type} = Enum.at(keyword, 0)
      {:ok, keyword_token_type}
    else
      {:error, :not_found}
    end
  end

空白などの不要な文字を飛ばす（p13）

  defp skip_space(lexer) do
    if lexer.ch == ' ' or lexer.ch == '\n' or lexer.ch == '\t' or lexer.ch == '\r' do
      update_lexer(lexer)
      |> skip_space()
    else
      lexer
    end
  end

整数に対応 (p13)

identifierとほぼ同様の方法で対応します。

先ほどの is_letter の部分の条件分岐を cond do で複数の条件で分岐するようにしています。

  defp create_if_const_token_type(ch) do
    case ch do
      '=' -> {:ok, Token.new(Token.token_type.assign,    to_string(ch))}
      ';' -> {:ok, Token.new(Token.token_type.semicolon, to_string(ch))}
      '(' -> {:ok, Token.new(Token.token_type.lparen,    to_string(ch))}
      ')' -> {:ok, Token.new(Token.token_type.rparen,    to_string(ch))}
      ',' -> {:ok, Token.new(Token.token_type.comma,     to_string(ch))}
      '+' -> {:ok, Token.new(Token.token_type.plus,      to_string(ch))}
      '{' -> {:ok, Token.new(Token.token_type.lbrace,    to_string(ch))}
      '}' -> {:ok, Token.new(Token.token_type.rbrace,    to_string(ch))}
      nil -> {:ok, Token.new(Token.token_type.eof,       "")}
      ch  ->
        cond do
            defp create_if_const_token_type(ch) do
    case ch do
      '=' -> {:ok, Token.new(Token.token_type.assign,    to_string(ch))}
      ';' -> {:ok, Token.new(Token.token_type.semicolon, to_string(ch))}
      '(' -> {:ok, Token.new(Token.token_type.lparen,    to_string(ch))}
      ')' -> {:ok, Token.new(Token.token_type.rparen,    to_string(ch))}
      ',' -> {:ok, Token.new(Token.token_type.comma,     to_string(ch))}
      '+' -> {:ok, Token.new(Token.token_type.plus,      to_string(ch))}
      '{' -> {:ok, Token.new(Token.token_type.lbrace,    to_string(ch))}
      '}' -> {:ok, Token.new(Token.token_type.rbrace,    to_string(ch))}
      nil -> {:ok, Token.new(Token.token_type.eof,       "")}
      ch  ->
        cond do
          is_letter?(ch) -> {:error, :identifier}
          is_digit?(ch)  -> {:error, :digit}
          true           -> {:error, :illegal}
        end
    end
  end(ch) -> {:error, :identifier}
          is_digit?(ch)  -> {:error, :digit}
          true           -> {:error, :illegal}
        end
    end
  end

  defp is_digit?(ch) when is_integer(ch) do
    ch = [ch]
    (('0'<= ch) and (ch <= '9'))
  end

  defp is_digit?(ch) do
    (('0'<= ch) and (ch <= '9'))
  end

以下の関数は

lexer.input = '19 foo bar'
lexer.ch = '1' #一文字目

の時 18 を取得します。

  defp read_number(lexer) do
    lexer.input
    |> Enum.drop(lexer.position)
    |> Enum.take_while(&(is_digit?(&1)))
    |> to_string()
  end

  def read_token(lexer) do
#     （省略）
       {:error, :digit} ->
          literal = read_number(lexer)
          literal_length = String.length(literal)
          new_token = Token.new(Token.token_type.int, literal)
          lexer
          |> Map.update!(:result, fn result -> result ++ [new_token] end)
          |> update_lexer(literal_length)

    end
  end

これで僕の説明漏れがなければ先ほどの新テストが通るはずです！

演算子(-, !, *, /, <, >)の追加 (p15)

例によって先にテストを記述します。

  test "test lexer2" do
    input =
     'let five = 5;
      let ten = 10;

      let add = fn(x, y) {
        x + y;
      };

      let result = add(five, ten);
      !-/*5;
      5 < 10 > 5;'

    lexer = Lexer.new(input)

    [
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.function,   literal: "fn"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.plus,       literal: "+"},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "result"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.bang,       literal: "!"},
      %Token{type: Token.token_type.minus,      literal: "-"},
      %Token{type: Token.token_type.slash,      literal: "/"},
      %Token{type: Token.token_type.asterisk,   literal: "*"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.lt,         literal: "<"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.gt,         literal: ">"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.eof,        literal: ""},
    ]
    |> Enum.reduce(lexer, fn %Token{type: type, literal: literal}, acc_lexer ->
      acc_lexer = acc_lexer |> Lexer.read_token()
      assert type == Enum.at(acc_lexer.result, -1).type
      assert literal == Enum.at(acc_lexer.result, -1).literal
      acc_lexer
    end)
  end
end

token_type に追加します。

  def token_type() do
    %{
      illegal: "illegal",
      eof: "eof",

      #識別子 + リテラル
      ident: "ident",
      int: "int",

      #演算子
      assign: "=",
      plus: "+",

      #デリミタ
      comma: ",",
      semicolon: ";",

      lparen: "(",
      rparen: ")",
      lbrace: "{",
      rbrace: "}",

      #キーワード
      function: "function",
      let: "let",
      minus: "-",
      bang: "!",
      asterisk: "*",
      slash: "/",

      lt: "<",
      gt: ">",
    }
  end

create_if_const_token_typeでも新しい token_type に対応します。

  defp create_if_const_token_type(ch) do
    case ch do
      '=' -> {:ok, Token.new(Token.token_type.assign,    to_string(ch))}
      ';' -> {:ok, Token.new(Token.token_type.semicolon, to_string(ch))}
      '(' -> {:ok, Token.new(Token.token_type.lparen,    to_string(ch))}
      ')' -> {:ok, Token.new(Token.token_type.rparen,    to_string(ch))}
      ',' -> {:ok, Token.new(Token.token_type.comma,     to_string(ch))}
      '+' -> {:ok, Token.new(Token.token_type.plus,      to_string(ch))}
      '{' -> {:ok, Token.new(Token.token_type.lbrace,    to_string(ch))}
      '}' -> {:ok, Token.new(Token.token_type.rbrace,    to_string(ch))}
      '-' -> {:ok, Token.new(Token.token_type.minus,     to_string(ch))}
      '!' -> {:ok, Token.new(Token.token_type.bang,      to_string(ch))}
      '*' -> {:ok, Token.new(Token.token_type.asterisk,  to_string(ch))}
      '/' -> {:ok, Token.new(Token.token_type.slash,     to_string(ch))}
      '<' -> {:ok, Token.new(Token.token_type.lt,        to_string(ch))}
      '>' -> {:ok, Token.new(Token.token_type.gt,        to_string(ch))}
      nil -> {:ok, Token.new(Token.token_type.eof,       "")}
      ch  ->
        cond do
          is_letter?(ch) -> {:error, :identifier}
          is_digit?(ch)  -> {:error, :digit}
          true           -> {:error, :illegal}
        end
    end
  end

トークン、キーワード(return, true, false, if, else)の追加 (p17)

例によって先にテストを記述します。

  test "test lexer2" do
    input =
     'let five = 5;
      let ten = 10;

      let add = fn(x, y) {
        x + y;
      };

      let result = add(five, ten);
      !-/*5;
      5 < 10 > 5;

      if (5 < 10) {
        return true;
      }else{
        return false;
      }'

    lexer = Lexer.new(input)

    [
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.function,   literal: "fn"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.plus,       literal: "+"},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "result"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.bang,       literal: "!"},
      %Token{type: Token.token_type.minus,      literal: "-"},
      %Token{type: Token.token_type.slash,      literal: "/"},
      %Token{type: Token.token_type.asterisk,   literal: "*"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.lt,         literal: "<"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.gt,         literal: ">"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.if,         literal: "if"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.lt,         literal: "<"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.return,     literal: "return"},
      %Token{type: Token.token_type.true,       literal: "true"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.else,       literal: "else"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.return,     literal: "return"},
      %Token{type: Token.token_type.false,      literal: "false"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.eof,        literal: ""},
    ]
    |> Enum.reduce(lexer, fn %Token{type: type, literal: literal}, acc_lexer ->
      acc_lexer = acc_lexer |> Lexer.read_token()
      assert type == Enum.at(acc_lexer.result, -1).type
      assert literal == Enum.at(acc_lexer.result, -1).literal
      acc_lexer
    end)
  end
end

token.exにも対応します。

  def token_type() do
    %{
      illegal: "illegal",
      eof: "eof",

      #識別子 + リテラル
      ident: "ident",
      int: "int",

      #演算子
      assign: "=",
      plus: "+",
      minus: "-",
      bang: "!",
      asterisk: "*",
      slash: "/",

      lt: "<",
      gt: ">",

      #デリミタ
      comma: ",",
      semicolon: ";",

      lparen: "(",
      rparen: ")",
      lbrace: "{",
      rbrace: "}",

      #キーワード
      function: "function",
      let:      "let",
      true:     "true",
      false:    "false",
      if:       "if",
      else:     "else",
      return:   "return",
    }
  end

  def keywords() do
    %{
      "fn"     => "function",
      "let"    => "let",
      "true"   => "true",
      "false"  => "false",
      "if"     => "if",
      "else"   => "else",
      "return" => "return",
    }
  end

演算子(==, !=)の追加 (p17)

例のごとくテストを書きます

  test "test lexer2" do
    input =
     'let five = 5;
      let ten = 10;

      let add = fn(x, y) {
        x + y;
      };

      let result = add(five, ten);
      !-/*5;
      5 < 10 > 5;

      if (5 < 10) {
        return true;
      }else{
        return false;
      }

      10 == 10;
      10 != 9;'

    lexer = Lexer.new(input)

    [
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.function,   literal: "fn"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.ident,      literal: "x"},
      %Token{type: Token.token_type.plus,       literal: "+"},
      %Token{type: Token.token_type.ident,      literal: "y"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.let,        literal: "let"},
      %Token{type: Token.token_type.ident,      literal: "result"},
      %Token{type: Token.token_type.assign,     literal: "="},
      %Token{type: Token.token_type.ident,      literal: "add"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.ident,      literal: "five"},
      %Token{type: Token.token_type.comma,      literal: ","},
      %Token{type: Token.token_type.ident,      literal: "ten"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.bang,       literal: "!"},
      %Token{type: Token.token_type.minus,      literal: "-"},
      %Token{type: Token.token_type.slash,      literal: "/"},
      %Token{type: Token.token_type.asterisk,   literal: "*"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.lt,         literal: "<"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.gt,         literal: ">"},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.if,         literal: "if"},
      %Token{type: Token.token_type.lparen,     literal: "("},
      %Token{type: Token.token_type.int,        literal: "5"},
      %Token{type: Token.token_type.lt,         literal: "<"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.rparen,     literal: ")"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.return,     literal: "return"},
      %Token{type: Token.token_type.true,       literal: "true"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.else,       literal: "else"},
      %Token{type: Token.token_type.lbrace,     literal: "{"},
      %Token{type: Token.token_type.return,     literal: "return"},
      %Token{type: Token.token_type.false,      literal: "false"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.rbrace,     literal: "}"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.eq,         literal: "=="},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.int,        literal: "10"},
      %Token{type: Token.token_type.not_eq,     literal: "!="},
      %Token{type: Token.token_type.int,        literal: "9"},
      %Token{type: Token.token_type.semicolon,  literal: ";"},
      %Token{type: Token.token_type.eof,        literal: ""},
    ]
    |> Enum.reduce(lexer, fn %Token{type: type, literal: literal}, acc_lexer ->
      acc_lexer = acc_lexer |> Lexer.read_token()
      assert type == Enum.at(acc_lexer.result, -1).type
      assert literal == Enum.at(acc_lexer.result, -1).literal
      acc_lexer
    end)
  end
end

以下のように token_type に追加します。

 def token_type() do
    %{
      illegal: "illegal",
      eof: "eof",

      #識別子 + リテラル
      ident: "ident",
      int: "int",

      #演算子
      assign: "=",
      plus: "+",
      minus: "-",
      bang: "!",
      asterisk: "*",
      slash: "/",

      lt: "<",
      gt: ">",

      eq: "==",
      not_eq: "!=",

      #デリミタ
      comma: ",",
      semicolon: ";",

      lparen: "(",
      rparen: ")",
      lbrace: "{",
      rbrace: "}",

      #キーワード
      function: "function",
      let:      "let",
      true:     "true",
      false:    "false",
      if:       "if",
      else:     "else",
      return:   "return",
    }
  end

ここで難しいのは’=‘が来た時に次にくる文字によって == の一部なのか = なのかが変わってくる点です。なので=や!が来た時に次の文字を覗く必要があります。

以下のように createifconsttokentype を変更します。

  defp create_if_const_token_type(ch) do
    case ch do
      '=' -> {:ambiguous, ch}
      ';' -> {:ok,        Token.new(Token.token_type.semicolon, to_string(ch))}
      '(' -> {:ok,        Token.new(Token.token_type.lparen,    to_string(ch))}
      ')' -> {:ok,        Token.new(Token.token_type.rparen,    to_string(ch))}
      ',' -> {:ok,        Token.new(Token.token_type.comma,     to_string(ch))}
      '+' -> {:ok,        Token.new(Token.token_type.plus,      to_string(ch))}
      '{' -> {:ok,        Token.new(Token.token_type.lbrace,    to_string(ch))}
      '}' -> {:ok,        Token.new(Token.token_type.rbrace,    to_string(ch))}
      '-' -> {:ok,        Token.new(Token.token_type.minus,     to_string(ch))}
      '!' -> {:ambiguous, ch}
      '*' -> {:ok,        Token.new(Token.token_type.asterisk,  to_string(ch))}
      '/' -> {:ok,        Token.new(Token.token_type.slash,     to_string(ch))}
      '<' -> {:ok,        Token.new(Token.token_type.lt,        to_string(ch))}
      '>' -> {:ok,        Token.new(Token.token_type.gt,        to_string(ch))}
      nil -> {:ok,        Token.new(Token.token_type.eof,       "")}
      ch  ->
        cond do
          is_letter?(ch) -> {:error, :identifier}
          is_digit?(ch)  -> {:error, :digit}
          true           -> {:error, :illegal}
        end
    end
  end

そして ambiguous が来た時に以下のように次の文字を覗く関数 peek_char を用いて = か == かを判断して Token を生成します。

def read_token(lexer) do
    lexer = skip_space(lexer)
    case create_if_const_token_type(lexer.ch) do
      {:ok, new_token} ->
          lexer
          |> Map.update!(:result, fn result -> result ++ [new_token] end)
          |> update_lexer()

      {:ambiguous, '='} ->
        case peek_char(lexer) do
          {:ok, '='} ->
              new_token = Token.new(Token.token_type.eq, "==")
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer(2)
          _   ->
              new_token = Token.new(Token.token_type.assign, to_string(lexer.ch))
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer()
        end

      {:ambiguous, '!'} ->
        case peek_char(lexer) do
          {:ok, '='} ->
              new_token = Token.new(Token.token_type.not_eq, "!=")
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer(2)
          _   ->
              new_token = Token.new(Token.token_type.bang, to_string(lexer.ch))
              lexer
              |> Map.update!(:result, fn result -> result ++ [new_token] end)
              |> update_lexer()
        end

peek_charの定義内容は以下です

  def peek_char(lexer) do
    if lexer.read_position >= String.length(to_string(lexer.input)) do
      {:error, :last_char}
    else
      next_ch = Enum.at(lexer.input, lexer.read_position)
      {:ok, [next_ch]}
    end
  end

コマンドラインに対応

defmodule MonkeyAlchemist do
  def main(_args) do
    IO.gets("")
    |> String.trim
    |> String.to_charlist()
    |> Lexer.new()
    |> reading()
    |> Map.get(:result)
    |> IO.inspect()
  end

  def reading(lexer) do
    case lexer.ch do
      nil -> lexer
      _   ->
        lexer = Lexer.read_token(lexer)
        reading(lexer)
    end
  end
end

字句解析器完成！

これで以下のようにコマンドラインでコードを入力することで字句解析された結果が返ってきます！