Rubyテンプレートを深く掘り下げる：パーサー

今日、私たちはRubyテンプレートへの旅を続けています。レクサーを配置したら、次のステップであるパー​​サーに進みましょう。

前回は文字列の補間を検討し、その後、独自のテンプレート言語の作成に取り組みました。テンプレートを読み取り、それをトークンのストリームに変換するレクサーを実装することから始めました。今日は、付随するパーサーを実装します。また、少し言語理論に足を踏み入れます。

どうぞ！

抽象構文木

Welcome to {{name}}の簡単なサンプルテンプレートを振り返ってみましょう。 。レクサーを使用して文字列をトークン化した後、次のようなトークンのリストを取得します。

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

最終的には、テンプレートを評価し、式を実際の値に置き換えます。物事をもう少し難しくするために、複雑なブロック式を評価して、繰り返しと条件を考慮に入れたいと思います。

これを行うには、テンプレートの論理構造を記述する抽象構文木（AST）を生成する必要があります。ツリーは、他のノードを参照したり、トークンからの追加データを保存したりできるノードで構成されています。

簡単な例では、目的の抽象構文木は次のようになります。

文法の定義

文法を定義するために、言語の理論的基礎から始めましょう。他のプログラミング言語と同様に、私たちのテンプレート言語は文脈自由言語であるため、文脈自由文法で記述できます。 （ウィキペディアの詳細な説明にある数学表記を怖がらせないでください。概念は非常に単純で、文法を表記するための開発者にとってより使いやすい方法があります。）

文脈自由文法は、言語のすべての可能な文字列がどのように構築されるかを説明する一連の規則です。 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の真の伝統では、楽しんでパーサーを自分で構築し、その過程で1つか2つのことを学んでいきましょう。

パーサーの構築

言語理論はさておき、実際にパーサーを構築することに取り掛かりましょう。さらに最小限の、しかしまだ有効なテンプレートから始めましょう：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
      # Parsing starts here
    end
  end
end

クラスはトークンの配列を受け取り、それを格納します。 parseと呼ばれるパブリックメソッドが1つだけあります トークンを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

次に、解析メソッドを実装して、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">>

確かに、これは、コンテンツノードが1つしかない単純な例でのみ機能します。実際に式を含むより複雑な例に切り替えましょう：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

parse_content メソッドは現在のトークンを調べ、そのタイプをチェックします。 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であることを確認します。 。その場合は、次のトークンに進み、parse_identifierを呼び出して、識別子と引数を解析します。 およびparse_arguments 、 それぞれ。どちらのメソッドもそれぞれのノードを返し、現在のトークンを進めます。それが完了すると、現在のトークンが存在し、:CLOSEであることを確認します トークン。そうでない場合は、エラーが発生します。それ以外の場合は、新しく作成されたExpressionを返す前に、最後にもう一度位置を進めます。 ノード。

この時点で、いくつかのパターンが出現していることがわかります。次のトークンに数回進み、現在のトークンとそのタイプがあることも確認しています。そのためのコードは少し面倒なので、2つのヘルパーメソッドを紹介しましょう。

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 メソッドは@positionをインクリメントするだけです 指定されたオフセットによるインスタンス変数。

次に予想されるトークンに関して柔軟性がない場合のために、トークンが一致しない場合に適切なエラーメッセージを表示するメソッドも導入します。

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_identifierを呼び出すことです。 parse_statementの代わりに 。別のヘルパーメソッドを導入することで、重複したロジックを取り除くことができます。

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

repeat メソッドはsendを使用します ノードを返さなくなるまで、指定されたメソッド名を呼び出します。それが発生すると、収集された結果（または単に空の配列）が返されます。このヘルパーを配置すると、両方のparse_statements およびparse_arguments 1行のメソッドになります。

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>  >

読むのは少し難しいですが、実際には、正しい抽象構文木です。 Template ノードにはContentがあります およびExpression 声明。 Content ノードの値は"Welcome to " およびExpression ノードの識別子はIdentifierです :nameのノード その値として。

ブロック式の解析

パーサーの実装を完了するには、ブロック式の解析を実装する必要があります。念のため、解析するテンプレートは次のとおりです。

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のように ノードには、識別子と引数が格納されます。さらに、ブロックと逆ブロックのステートメントも格納されます。

文法を振り返ると、ブロック式を解析するには、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 トークン。両方のトークンが見つかった場合、parse_statementsを呼び出します 再び逆ブロックを解析します。それ以外の場合は、その部分を完全にスキップします。

最後に、オープンブロック式と同じ識別子を使用するエンドブロック式があることを確認します。識別子が一致しない場合、エラーが発生します。それ以外の場合は、新しいBlockExpressionを作成します ノードとそれを返します。

高度なブロック式テンプレートのトークンを使用してパーサーを呼び出すと、テンプレートのASTが返されます。読みにくいので、ここでは出力例を含めません。代わりに、生成されたASTを視覚的に表現したものです。

parse_statementsを呼び出しているため parse_block_expressionの内部 、ブロックと逆ブロックの両方に、通常のコンテンツだけでなく、より多くの式、ブロック式が含まれる場合があります。

旅は続く…

私たちは、独自のテンプレート言語の実装に向けた旅でまともな進歩を遂げました。言語理論を少し理解した後、テンプレート言語の文法を定義し、それを使用してパーサーを最初から実装しました。

レクサーとパーサーの両方が配置されているため、テンプレートから補間された文字列を生成するためのインタープリターが不足しているだけです。この部分については、RubyMagicの次のエディションで説明します。 Ruby Magicメーリングリストに登録して、リリースされたときにアラートを受け取ります。