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, 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.
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:
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 and therefore can be described by a 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:
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 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:
[[:CONTENT, "Welcome to Ruby Magic"]]
First, we set up our parser class. It looks like this:
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:
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.
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.
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:
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}}.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
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:
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.
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.
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.
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.
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, to get alerted when it comes out.
Guest writer Benedikt Deicke is a software engineer and co-founder of Userlist.io. On the side, he’s writing a book about building SaaS applications in Ruby on Rails. You can reach out to Benedikt via Twitter.
Top comments (0)