Làm chủ Templating Ruby: Xây dựng Parser để Xử lý Template Hiệu quả

Hôm nay, tiếp tục journey vào Ruby Templating. Với lexer in place, move on to next step: The parser.

Lần trước, xem string interpolation và sau đó, dive vào tạo templating language riêng. Bắt đầu implement lexer đọc template và convert thành stream of tokens. Hôm nay, implement accompanying parser. Cũng dip toes vào language theory.

Let's go!

Abstract Syntax Trees

Nhìn lại simple example template Welcome to {{name}}. Sau khi dùng lexer tokenize string, get list tokens như sau.

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

Muốn evaluate template và replace expression với real values. Để challenging hơn, cũng muốn evaluate complex block expressions, cho phép repetition và conditionals.

Để làm vậy, generate abstract syntax tree (AST) mô tả logical structure của template. Tree consist of nodes reference other nodes hoặc store additional data từ tokens.

Cho simple example, desired AST như sau:

Defining a Grammar

Để define grammar, bắt đầu với theoretical basis của language. Giống programming languages khác, templating language là context-free language, do đó described by context-free grammar. (Đừng để mathematical notations trong Wikipedia descriptions chi tiết scare you away. Concept straight forward, có developer-friendly ways notate grammar.)

Context-free grammar là set of rules mô tả how all possible strings của language constructed. Xem grammar cho templating language trong EBNF notation:

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

Mỗi assignment define rule. Rule name bên trái, bunch other rules (lower case) hoặc tokens (upper case) từ lexer bên phải. Rules và tokens concatenated dùng commas , hoặc alternated dùng pipe |. Rules và tokens trong curly braces { ... } có thể repeat several times. Khi trong brackets [ ... ], considered optional.

Grammar trên concise mô tả: template consist of statements. Statement là CONTENT token, expression, hoặc block expression. Expression là OPEN_EXPRESSION token, theo sau IDENTIFIER token, arguments, CLOSE token. Block expression là perfect example tại sao better dùng notation như trên thay vì describe bằng natural language.

Có tools auto-generate parsers từ grammar definitions như trên. But in true Ruby Magic tradition, let's have fun và build parser ourselves, hopefully learn a thing or two.

Building the Parser

Với language theory aside, jump vào actually building parser. Bắt đầu với even more minimal, nhưng still valid, template: Welcome to Ruby Magic. Template này không có expressions, token list chỉ one element:

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

Setup parser class. Nó trông như sau:

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

Class nhận array tokens và store. Chỉ có one public method parse convert tokens thành AST.

Nhìn lại grammar, top-most rule là template. Ý nghĩa parse, tại start of parsing process, return Template node.

Nodes là simple classes no behavior của riêng chúng. Chỉ connect other nodes hoặc store values từ tokens. Template node trông như sau:

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

Để make example work, cũng cần Content node. Nó chỉ store text content ("Welcome to Ruby Magic") từ token.

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

Tiếp, implement parse method tạo instance Template và Content connect correctly.

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

Run parser, get correct result:

Magicbars::Parser.parse(tokens)
# => #>

Thừa nhận, chỉ work cho simple example chỉ có one content node. Switch sang complex example include expression: Welcome to {{name}}.

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

Cần Expression node và Identifier node. Expression node store identifier và arguments (theo grammar, array zero hoặc more Identifier nodes). Giống nodes khác, không nhiều gì.

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

Với nodes mới, modify parse method handle cả regular content và expressions. Introduce parse_statements method keep calling parse_statement miễn nó return value.

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

parse_statement gọi parse_content trước, nếu không return value, gọi parse_expression.

def parse_statement
  parse_content || parse_expression
end

Nhận ra parse_statement bắt đầu look very similar rule statement trong grammar. Đây là nơi taking time explicitly write grammar trước giúp ensure on right path.

Tiếp, modify parse_content không chỉ look at first token. Introduce additional @position instance variable trong initializer, dùng fetch current token.

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 giờ look at current token check type. Nếu CONTENT token, increment position (vì current token successfully parsed) và dùng token content tạo Content node. Nếu không current token (vì end of tokens) hoặc type không match, exit early return nil.

Với improved parse_content, tackle new 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

Check current token exists và type OPEN_EXPRESSION. Nếu vậy, advance next token, parse identifier và arguments bằng parse_identifier và parse_arguments. Cả hai return respective nodes và advance current token. Done, ensure current token exists và là :CLOSE token. Nếu không, raise error. Otherwise, advance position lần cuối, return new Expression node.

Patterns emerge. Advance next token several times, check current token exists và type. Code hơi cumbersome, introduce two helper methods.

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 nhận variable number token types, check against next tokens trong token stream. Nếu all match, advance past matching tokens và return chúng. advance chỉ increment @position by given offset.

Cho cases no flexibility về next expected token, introduce method raise nice error message khi token không match.

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

Dùng helper methods, parse_content và parse_expression cleaner, readable hơn.

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

Cuối, xem parse_identifier và parse_arguments. Nhờ helpers, parse_identifier simple như parse_content. Chỉ khác return another node type.

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

Implement parse_arguments, nhận thấy almost identical parse_statements. Chỉ khác gọi parse_identifier thay parse_statement. Eliminate duplicated logic bằng helper method khác.

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

repeat dùng send call given method name cho đến khi không return node. Khi đó, return collected results (hoặc empty array). Với helper này, cả parse_statements và parse_arguments thành one-line methods.

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

Với changes, try parse token stream:

Magicbars::Parser.parse(tokens)
# => #,
# # >]

Hơi khó đọc nhưng correct AST. Template node có Content và Expression statement. Content node value "Welcome to ", Expression node identifier là Identifier node với :name value.

Parsing Block Expressions

Hoàn thành parser implementation, vẫn cần implement parsing block expressions. Nhắc lại template muốn parse:

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

Introduce BlockExpression node. Node store bit more data, nhưng không làm gì khác, không exciting.

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

Giống Expression node, store identifier và arguments. Thêm store statements của block và inverse block.

Nhìn lại grammar, để parse block expressions, amend parse_statements với call parse_block_expression. Giờ look just like rule in grammar.

def parse_statement
  parse_content || parse_expression || parse_block_expression
end

parse_block_expression method hơi complex. Nhưng nhờ helper methods, vẫn readable.

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

Phần đầu similar parse_expression. Parse opening block expression với identifier và arguments. Sau đó gọi parse_statements parse inside block.

Done, check cho {{else}} expression, identified by OPEN_INVERSE token theo sau CLOSE token. Nếu both tokens found, gọi parse_statements again parse inverse block. Otherwise skip entirely.

Final thing, ensure end block expression dùng same identifier as open block expression. Nếu identifiers không match, raise error. Otherwise, tạo new BlockExpression node return.

Gọi parser với tokens của advanced block expression template return AST. Không include example output, barely readable. Thay vào đó, visual representation của generated AST.

Vì gọi parse_statements trong parse_block_expression, cả block và inverse block có thể include more expressions, block expressions, regular content.

The Journey Continues…

Decent progress journey implement own templating language. Sau short dip vào language theory, defined grammar cho templating language và dùng implement parser from scratch.

Với cả lexer và parser in place, chỉ missing interpreter generate interpolated string từ template. Cover part này trong upcoming edition RubyMagic. Subscribe Ruby Magic mailinglist, get alerted khi ra.