Digging Deeper into Ruby Templating: The Parser
Tags: ruby, programming, beginners
Published: 2019-07-30 09:29:52

---
title: "Digging Deeper into Ruby Templating: The Parser"
layout: layout_ruby_magic
description: "With the lexer in place, let’s move on to the next step: The parser."
cover_image: https://blog.appsignal.com/images/blog/2019-07/template-parser.jpg
tags: ruby, programming, beginners
published: true
canonical_url: https://blog.appsignal.com/2019/07/30/ruby-magic-ruby-templating-the-parser.html
---

Today, we continue our journey into Ruby Templating. With the lexer in place, let’s move on to the next step: The parser. 

[Last time](https://blog.appsignal.com/2019/07/02/ruby-magic-brewing-our-own-template-lexer-in-ruby.html), we looked at string interpolation and subsequently, dived into creating our own templating language. We started by implementing a lexer that reads a template and converts it into a stream of tokens. Today, we’ll implement the accompanying parser. We will also dip our toes into a bit of language theory.

Here we go!

## Abstract Syntax Trees

Let’s look back to our simple example template for `Welcome to {{name}}`. After using the lexer to tokenize the string, we get a list of tokens like this.

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

Ultimately, we want to evaluate the template and replace the expression with real values. To make things a bit more challenging, we also want to evaluate complex block expressions, allowing for repetition and conditionals.

To do this, we have to generate an abstract syntax tree (AST) that describes the logical structure of the template. The tree consists of nodes that may reference other nodes or store additional data from the tokens.

For our simple example, the desired abstract syntax tree looks like this:

![](https://blog.appsignal.com/images/blog/2019-07/simple-ast.svg)

## Defining a Grammar

To define the grammar, let's start with the theoretical basis of a language. Like other programming languages, our templating language is a [context-free language](https://en.wikipedia.org/wiki/Context-free_language) and therefore can be described by a [context-free grammar](https://en.wikipedia.org/wiki/Context-free_grammar). _(Don’t let the mathematical notations in the detailed Wikipedia descriptions scare you away. The concept is pretty straight forward, and there are more developer-friendly ways to notate a grammar.)_

A context-free grammar is a set of rules that describe how all possible strings of a language are constructed. Let’s look at the grammar for our templating language in [EBNF notation](https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form):

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

Each assignment defines a rule. The rule’s name is on the left and a bunch of other rules (lower case) or tokens (upper case) from our lexer are on the right. Rules and tokens can be concatenated using commas `,` or alternated using the pipe `|` symbol. Rules and tokens inside of curly braces `{ ... }` might be repeated several times. When they are inside of brackets `[ ... ]`, they are considered optional.

The above grammar is a concise way to describe that a template consists of statements. A statement is either a `CONTENT` token, an expression, or a block expression. An expression is an `OPEN_EXPRESSION` token, followed by an `IDENTIFIER` token, followed by arguments, followed by a `CLOSE` token. And a block expression is the perfect example of why it’s better to use a notation like the one above instead of trying to describe it with a natural language.

There are tools that [automatically generate parsers](https://en.wikipedia.org/wiki/Comparison_of_parser_generators) from grammar definitions like the one above. But in true Ruby Magic tradition, let's have some fun and build the parser ourselves, hopefully learning a thing or two in the process.

## Building the Parser

With the language theory aside, let’s jump into actually building the parser. Let’s start with an even more minimal, but still valid, template: `Welcome to Ruby Magic`. This template doesn’t have any expressions and the list of tokens consists of just one element. Here’s what it looks like:

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

First, we set up our parser class. It looks like this:

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

The class takes an array of tokens and stores it. It only has one public method called `parse` that converts the tokens into an AST.

Looking back at our grammar, the top-most rule is `template`. That implies that `parse`, at the start of the parsing process, will return a `Template` node.

Nodes are simple classes with no behavior of their own. They just connect other nodes or store some values from the tokens. Here’s what the `Template` node looks like:

```ruby
module Magicbars
  module Nodes
    class Template
      attr_reader :statements

      def initialize(statements)
        @statements = statements
      end
    end
  end
end
```

To make our example work, we also need a `Content` node. It just stores the text content (`"Welcome to Ruby Magic"`) from the token.

```ruby
module Magicbars
  module Nodes
    class Content
      attr_reader :content

      def initialize(content)
        @content = content
      end
    end
  end
end
```

Next, let’s implement the parse method to create an instance of `Template` and an instance of `Content` and connect them up correctly.

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

When we run the parser, we get the correct result:

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

Admittedly, this only works for our simple example that only has one content node. Let’s switch to a more complex example that actually includes an expression: `Welcome to {{name}}`.

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

For this, we need an `Expression` node and an `Identifier` node. The `Expression`  node stores the identifier as well as any arguments (which, according to the grammar, are an array of zero or more `Identifier` nodes). As with the other nodes, there’s not much to see here.

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

With the new nodes in place, let’s modify the `parse` method to handle both regular content as well as expressions. We do that by introducing a `parse_statements` method that just keeps on calling `parse_statement` as long as it returns a value.

```ruby
def parse
  Magicbars::Nodes::Template.new(parse_statements)
end

def parse_statements
  results = []

  while result = parse_statement
    results << result
  end

  results
end
```

`parse_statement` itself first calls `parse_content` and if that doesn’t return any value, it calls `parse_expression`.

```ruby
def parse_statement
  parse_content || parse_expression
end
```

Have you noticed that the `parse_statement` method is starting to look very similar to the `statement` rule in the grammar? This is where taking the time to explicitly write up the grammar beforehand helps a lot to ensure that we’re on the right path.

Next, let’s modify the `parse_content` method so that it doesn’t only look at the first token. We do this by introducing an additional `@position` instance variable in the initializer and use it to fetch the current token.

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

The `parse_content` method now looks at the current token and checks its type. If it’s a `CONTENT` token, it increments the position (because the current token was successfully parsed) and uses the token’s content to create the `Content` node. If there is no current token (because we’re at the end of the tokens) or the type doesn’t match, the method exits early and returns `nil`.

With the improved `parse_content` method in place, let’s tackle the new `parse_expression` method.

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

First, we check that there is a current token and that its type is `OPEN_EXPRESSION`. If that’s the case, we advance to the next token and parse the identifier as well as the arguments by calling `parse_identifier` and `parse_arguments`, respectively. Both methods will return the respective nodes and advance the current token. When that’s done, we ensure that the current token exists and is a `:CLOSE` token. If it is not, we raise an error. Otherwise, we advance the position one last time, before returning the newly created `Expression` node.

At this point, we see some patterns emerge. We’re advancing to the next token several times and we’re also checking that there is a current token and its type. Because the code for that is a bit cumbersome, let’s introduce two helper methods.

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

The `expect` method takes a variable number of token types and checks them against the next tokens in the token stream. If they all match, it advances past the matching tokens and returns them. The `advance` method just increments the `@position` instance variable by the given offset.

For cases where there's no flexibility regarding the next expected token, we also introduce a method that raises a nice error message when the token doesn’t match.

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

By using these helper methods, `parse_content` and `parse_expression` are now cleaner and more readable.

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

Finally, let’s also look at `parse_identifier` and `parse_arguments`. Thanks to the helper methods, the `parse_identifier` method is as simple as the `parse_content` method. The only difference is that it returns another node type.

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

When implementing the `parse_arguments` method, we noticed that it’s almost identical to the `parse_statements` method. The only difference is that it calls `parse_identifier` instead of `parse_statement`. We can get rid of the duplicated logic by introducing another helper method.

```ruby
def repeat(method)
  results = []

  while result = send(method)
    results << result
  end

  results
end
```

The `repeat` method uses `send` to call the given method name until it no longer returns a node. Once that happens, the collected results (or just an empty array) are returned. With this helper in place, both `parse_statements` and `parse_arguments` become one-line methods.

```ruby
def parse_statements
  repeat(:parse_statement)
end

def parse_arguments
  repeat(:parse_identifier)
end
```

With all these changes in place, let’s try and parse the token stream:

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

It’s a bit hard to read but it’s, in fact, the correct abstract syntax tree. The `Template` node has a `Content` and an `Expression` statement. The `Content` node’s value is `"Welcome to "` and the `Expression` node’s identifier is the `Identifier` node with `:name` as its value.

## Parsing Block Expressions

To complete our parser implementation, we still have to implement parsing of block expressions. As a reminder, here’s the template we want to parse:

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

To do this, let’s first introduce a `BlockExpression` node. While this node stores a bit more data, it doesn’t do anything else and therefore isn’t very exciting.

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

Like the `Expression` node, it stores the identifier as well as any arguments. Additionally, it also stores the statements of the block and of the inverse block.

Looking back at the grammar, we notice that to parse block expressions, we have to amend the `parse_statements` method with a call to `parse_block_expression`. It now looks just like the rule in the grammar.

```ruby
def parse_statement
  parse_content || parse_expression || parse_block_expression
end
```

The `parse_block_expression` method itself is a bit more complex. But thanks to our helper methods, it’s still quite readable.

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

The first part is very similar to the `parse_expression` method. It parses the opening block expression with the identifier and the arguments. Afterward, it calls `parse_statements` to parse the inside of the block.

Once that’s done, we check for an `{{else}}` expression, identified by an `OPEN_INVERSE` token followed by a `CLOSE` token. If both tokens are found, we call `parse_statements` again to parse the inverse block. Otherwise, we just skip that part entirely.

As a final thing, we ensure that there is an end block expression using the same identifier as the open block expression. If the identifiers don’t match, we raise an error. Otherwise, we create a new `BlockExpression` node and return it.

Calling the parser with the tokens of the advanced block expression template will return the AST for the template. I’ll not include the example output here, as it’s barely readable. Instead, here’s a visual representation of the generated AST.

![](https://blog.appsignal.com/images/blog/2019-07/complex-ast.svg)

Because we’re calling `parse_statements` inside of `parse_block_expression`, both the block and the inverse block may include more expressions, block expressions, as well as regular content.

## The Journey Continues…

We made decent progress with our journey towards implementing our own templating language. After a short dip into language theory, we defined a grammar for our templating language and used it to implement a parser for it from scratch.

With both the lexer and the parser in place, we’re only missing an interpreter to generate the interpolated string from our template. We’ll cover this part in an upcoming edition of RubyMagic. Subscribe to [the Ruby Magic mailinglist](https://blog.appsignal.com/ruby-magic/), to get alerted when it comes out.

_Guest writer [Benedikt Deicke](http://benediktdeicke.com/) is a software engineer and co-founder of [Userlist.io](http://userlist.io/). On the side, he’s writing a book about building [SaaS applications in Ruby on Rails](http://saasguidebook.com/). You can reach out to Benedikt via [Twitter](http://twitter.com/benediktdeicke)._