Rubyテンプレートエンジンを深掘り：パーサーの実装

前回はRubyテンプレートエンジンの旅の第一歩として、字句解析器（レキサー）を実装しました。今回は次のステップである構文解析器（パーサー）の実装に取り組みます。また、言語理論の基礎にも少し触れていきます。

抽象構文木（AST）とは

簡単なテンプレート Welcome to {{name}} を例に考えてみましょう。レキサーでトークン化すると、以下のようなトークン列が得られます。

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

最終的にはこのテンプレートを評価し、式の部分を実際の値で置き換えたいと考えています。さらに、繰り返しや条件分岐といった複雑なブロック式も評価できるようにしたいところです。

そのためには、テンプレートの論理構造を表現する抽象構文木（Abstract Syntax Tree：AST）を生成する必要があります。ASTは、他のノードを参照したり、トークンから得られるデータを保持したりするノードで構成されます。

先ほどの簡単な例で期待されるASTは以下のようになります：

文法の定義

文法を定義するために、まず言語の理論的基盤を見てみましょう。他のプログラミング言語と同様、私たちのテンプレート言語は文脈自由言語であり、文脈自由文法で記述できます。（Wikipediaの詳細な数学的表記に怯む必要はありません。概念は単純で、開発者にとってより親しみやすい記法もあります。）

文脈自由文法とは、その言語に属するすべての文字列がどのように構築されるかを記述するルールの集合です。EBNF記法でテンプレート言語の文法を定義すると以下のようになります：

template = statements;
statements = { statement };
statement = CONTENT | expression | block_expression;
expression = OPEN_EXPRESSION, IDENTIFIER, arguments, CLOSE;
block_expression = OPEN_BLOCK, IDENTIFIER, arguments, CLOSE, statements, [ OPEN_INVERSE, CLOSE, statements ], OPEN_END_BLOCK, IDENTIFIER, CLOSE;
arguments = { IDENTIFIER };

各代入はルールを定義します。左辺がルール名、右辺が他のルール（小文字）やレキサーからのトークン（大文字）で構成されます。ルールやトークンはカンマ , で連結し、パイプ | で選択を表します。中括弧 { ... } 内は繰り返し、角括弧 [ ... ] 内は省略可能を意味します。

この文法は、テンプレートが文の列で構成され、文が CONTENT トークン、式、またはブロック式のいずれかであることを簡潔に表現しています。式は OPEN_EXPRESSION、IDENTIFIER、引数、CLOSE の順で並び、ブロック式は自然言語で説明するよりも、このような記法で表現する方がいかに適しているかを示す好例です。

このような文法定義から自動的にパーサーを生成するツールも存在しますが、Ruby Magicの伝統に則り、自前でパーサーを構築して学びを深めましょう。

パーサーの構築

理論はひとまず置いて、実際にパーサーを作っていきます。まずは式を含まない、より最小限のテンプレート Welcome to Ruby Magic から始めます。トークン列は要素1つだけです：

[[:CONTENT, "Welcome to Ruby Magic"]]

パーサークラスの雛形は以下の通りです：

module Magicbars
  class Parser
    def self.parse(tokens)
      new(tokens).parse
    end
 
    attr_reader :tokens
 
    def initialize(tokens)
      @tokens = tokens
    end
 
    def parse
      # パース処理はここから開始
    end
  end
end

このクラスはトークン配列を受け取り、公開メソッド parse でASTに変換します。

文法の最上位ルールは template なので、parse メソッドは最初に Template ノードを返すことになります。

ノードは振る舞いを持たないシンプルなクラスで、他のノードを接続したり、トークンからの値を保持したりするだけです。Template ノードは以下のようになります：

module Magicbars
  module Nodes
    class Template
      attr_reader :statements
 
      def initialize(statements)
        @statements = statements
      end
    end
  end
end

例を動かすには Content ノードも必要です。これはトークンからテキストコンテンツ（"Welcome to Ruby Magic"）を保持します：

module Magicbars
  module Nodes
    class Content
      attr_reader :content
 
      def initialize(content)
        @content = content
      end
    end
  end
end

次に parse メソッドを実装し、Template と Content のインスタンスを生成して正しく接続します：

def parse
  Magicbars::Nodes::Template.new(parse_content)
end
 
def parse_content
  return unless tokens[0][0] == :CONTENT
 
  Magicbars::Nodes::Content.new(tokens[0][1])
end

実行すると正しい結果が得られます：

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007fe90e939410 @statements=#<Magicbars::Nodes::Content:0x00007fe90e939578 @content="Welcome to Ruby Magic">>

ただし、これは単一のコンテンツノードしかない例でしか動きません。実際に式を含む Welcome to {{name}} というテンプレートで試してみましょう：

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

これには Expression ノードと Identifier ノードが必要です。Expression ノードは識別子と引数（文法では0個以上の Identifier ノードの配列）を保持します：

module Magicbars
  module Nodes
    class Expression
      attr_reader :identifier, :arguments
 
      def initialize(identifier, arguments)
        @identifier = identifier
        @arguments = arguments
      end
    end
  end
end

module Magicbars
  module Nodes
    class Identifier
      attr_reader :value
 
      def initialize(value)
        @value = value.to_sym
      end
    end
  end
end

新しいノードを用意したら、parse メソッドを修正して通常のコンテンツと式の両方を扱えるようにします。parse_statements メソッドを導入し、parse_statement が値を返す限り呼び出し続けるようにします：

def parse
  Magicbars::Nodes::Template.new(parse_statements)
end
 
def parse_statements
  results = []
 
  while result = parse_statement
    results << result
  end
 
  results
end

parse_statement はまず parse_content を呼び、値が返らなければ parse_expression を呼びます：

def parse_statement
  parse_content || parse_expression
end

parse_statement が文法の statement ルールと非常に似ていることに気づいたでしょうか。事前に文法を明文化しておくことで、実装が正しい道を進んでいるか確認しやすくなります。

次に parse_content を改良し、最初のトークンだけでなく現在位置のトークンを見るようにします。初期化時に @position インスタンス変数を追加し、現在のトークンを取得するようにします：

attr_reader :tokens, :position
 
def initialize(tokens)
  @tokens = tokens
  @position = 0
end
 
# ...
 
def parse_content
  return unless token = tokens[position]
  return unless token[0] == :CONTENT
 
  @position += 1
 
  Magicbars::Nodes::Content.new(token[1])
end

現在のトークンをチェックし、CONTENT タイプなら位置を進めて Content ノードを生成します。トークンがない（末尾に達した）かタイプが合わなければ nil を返します。

改良された parse_content ができたら、parse_expression を実装します：

def parse_expression
  return unless token = tokens[position]
  return unless token[0] == :OPEN_EXPRESSION
 
  @position += 1
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  if !tokens[position] || tokens[position][0] != :CLOSE
    raise "Unexpected token #{tokens[position][0]}. Expected :CLOSE."
  end
 
  @position += 1
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

現在のトークンが OPEN_EXPRESSION か確認し、次のトークンへ進んで識別子と引数をパースします。その後 :CLOSE トークンが来ることを確認し、最後に位置を進めて Expression ノードを返します。

ここでパターンが見えてきます。トークンを進める処理や、現在のトークンの存在とタイプをチェックする処理が繰り返されています。これをヘルパーメソッドで整理しましょう：

def expect(*expected_tokens)
  upcoming = tokens[position, expected_tokens.size]
 
  if upcoming.map(&:first) == expected_tokens
    advance(expected_tokens.size)
    upcoming
  end
end
 
def advance(offset = 1)
  @position += offset
end

expect は可変長引数でトークンタイプを受け取り、次のトークン列と照合します。すべて一致すれば該当トークンをスキップして返します。advance は単純に位置を進めます。

次のトークンが必須の場合にエラーを出すメソッドも用意します：

def need(*required_tokens)
  upcoming = tokens[position, required_tokens.size]
  expect(*required_tokens) or raise "Unexpected tokens. Expected #{required_tokens.inspect} but got #{upcoming.inspect}"
end

これらを使って parse_content と parse_expression を簡潔に書き換えます：

def parse_content
  if content = expect(:CONTENT)
    Magicbars::Nodes::Content.new(content[0][1])
  end
end
 
def parse_expression
  return unless expect(:OPEN_EXPRESSION)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

parse_identifier と parse_arguments も見てみましょう。parse_identifier は parse_content とほぼ同じで、返すノードタイプが違うだけです：

def parse_identifier
  if identifier = expect(:IDENTIFIER)
    Magicbars::Nodes::Identifier.new(identifier[0][1])
  end
end

parse_arguments を実装すると、parse_statements とほぼ同じロジックであることに気づきます。違いは parse_statement の代わりに parse_identifier を呼ぶ点だけです。重複を排除するため、汎用的なヘルパーを作ります：

def repeat(method)
  results = []
 
  while result = send(method)
    results << result
  end
 
  results
end

repeat は指定されたメソッド名を send で呼び出し、ノードが返らなくなるまで繰り返します。これで両メソッドがワンライナーになります：

def parse_statements
  repeat(:parse_statement)
end
 
def parse_arguments
  repeat(:parse_identifier)
end

ここまでの変更を適用してトークン列をパースしてみます：

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007f91a602f910
#     @statements=
#      [#<Magicbars::Nodes::Content:0x00007f91a58802c8 @content="Welcome to ">,
#       #<Magicbars::Nodes::Expression:0x00007f91a602fcd0
#        @arguments=[],
#        @identifier=
#         #<Magicbars::Nodes::Identifier:0x00007f91a5880138 @value=:name>  >

少し読みにくいですが、正しいASTが生成されています。Template ノードが Content と Expression の文を持ち、Content は "Welcome to "、Expression の識別子は値 :name を持つ Identifier ノードです。

ブロック式のパース

パーサー実装を完成させるには、ブロック式のパースが残っています。対象とするテンプレートは以下の通りです：

Welcome to {{name}}!

{{#if subscribed}}
  Thank you for subscribing to our mailing list.
{{else}}
  Please sign up for our mailing list to be notified about new articles!
{{/if}}

Your friends at {{company_name}}

まず BlockExpression ノードを定義します。データを多く保持しますが、振る舞いはありません：

module Magicbars
  module Nodes
    class BlockExpression
      attr_reader :identifier, :arguments, :statements, :inverse_statements
 
      def initialize(identifier, arguments, statements, inverse_statements)
        @identifier = identifier
        @arguments = arguments
        @statements = statements
        @inverse_statements = inverse_statements
      end
    end
  end
end

Expression と同様に識別子と引数を持ち、さらにブロック内の文（statements）と逆ブロック（else 節）の文（inverse_statements）を保持します。

文法に立ち返ると、ブロック式をパースするには parse_statements に parse_block_expression の呼び出しを追加すればよく、文法ルールそのままの形になります：

def parse_statement
  parse_content || parse_expression || parse_block_expression
end

parse_block_expression は少し複雑ですが、ヘルパーメソッドのおかげで読みやすくなっています：

def parse_block_expression
  return unless expect(:OPEN_BLOCK)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  statements = parse_statements
 
  if expect(:OPEN_INVERSE, :CLOSE)
    inverse_statements = parse_statements
  end
 
  need(:OPEN_END_BLOCK)
 
  if identifier.value != parse_identifier.value
    raise("Error. Identifier in closing expression does not match identifier in opening expression")
  end
 
  need(:CLOSE)
 
  Magicbars::Nodes::BlockExpression.new(identifier, arguments, statements, inverse_statements)
end

前半は parse_expression と似ています。開始ブロックの識別子と引数をパースし、parse_statements でブロック内部をパースします。

その後、{{else}} に相当する OPEN_INVERSE と CLOSE の組み合わせをチェックし、あれば逆ブロックをパースします。なければスキップします。

最後に終了ブロック {{/if}} があり、開始ブロックと同じ識別子であることを確認します。一致しなければエラー、一致すれば BlockExpression ノードを生成して返します。

高度なブロック式テンプレートのトークン列をパースすると、テンプレートのASTが得られます。出力は読みにくいので割愛し、生成されるASTの構造を図示すると以下のようになります。

parse_block_expression 内で parse_statements を呼んでいるため、ブロック内にも式、ブロック式、通常のコンテンツをネストして含められます。

旅は続く…

自前のテンプレート言語実装に向けて、着実に前進しています。言語理論に触れ、文法を定義し、それを基にパーサーをスクラッチから実装しました。

レキサーとパーサーが揃った今、残るはASTから補完済みの文字列を生成するインタープリターのみです。この部分は次回のRuby Magicで扱います。Ruby Magicメーリングリストに登録すれば、公開時に通知を受け取れます。