Packrat parsing: a top-down performance improvement

In my introduction to parser combinators, we developed the following module for generating common combinators and used them to construct a simple parser for addition expressions. I give all the code in full here, since in the preceding articles it appears in incremental chunks with various implementations of the same method given, and if we’re going to discuss performance we need to be unambiguous about what code we’re using.

module ParserCombinators
  State = Struct.new(:string, :offset) do
    def peek(n)
      string[offset ... offset + n]
    end

    def read(n)
      State.new(string, offset + n)
    end

    def complete?
      offset == string.size
    end
  end

  def parse(string)
    node, state = root.call(State.new(string, 0))

    if state and state.complete?
      node
    end
  end

  def str(string, &action)
    -> state {
      chunk = state.peek(string.size)

      if chunk == string
        node = [:str, chunk]
        node = action.call(node) if action
        [node, state.read(string.size)]
      end
    }
  end

  def chr(pattern, &action)
    -> state {
      chunk = state.peek(1)

      if chunk =~ %r{[#{pattern}]}
        node = [:chr, chunk]
        node = action.call(node) if action
        [node, state.read(1)]
      end
    }
  end

  def seq(*parsers, &action)
    -> state {
      matches = []

      parsers.each do |parser|
        node, state = state && parser.call(state)
        matches << node if state
      end

      if state
        node = [:seq, *matches]
        node = action.call(node) if action
        [node, state]
      end
    }
  end

  def rep(parser, n, &action)
    -> state {
      matches = []
      last_state = nil

      while state
        last_state = state
        node, state = parser.call(state)
        matches << node if state
      end

      if matches.size >= n
        node = [:rep, *matches]
        node = action.call(action) if action
        [node, last_state]
      end
    }
  end

  def alt(*parsers, &action)
    -> state {
      parsers.each do |parser|
        node, new_state = parser.call(state)
        if new_state
          node = action.call(node) if action
          return [node, new_state]
        end
      end

      nil
    }
  end

  def ref(name)
    -> state {
      __send__(name).call(state)
    }
  end
end

Then we went on to look at precedence and associativity and developed the following richer language for composing addition and multiplication. Although our previous implementation included blocks for transforming the original syntax nodes, I am omitting this for brevity and because it does not have a major impact on performance.

class Arithmetic
  include ParserCombinators

  def root
    expression
  end

  def expression
    alt(ref(:addition), ref(:term))
  end

  def addition
    binary(:term, str("+"))
  end

  def term
    alt(ref(:multiplication), ref(:factor))
  end

  def multiplication
    binary(:factor, str("*"))
  end

  def factor
    alt(ref(:number), ref(:paren_expression))
  end

  def number
    alt(str("0"), seq(chr("1-9"), rep(chr("0-9"), 0)))
  end

  def paren_expression
    seq(str("("), ref(:_), ref(:expression), ref(:_), str(")"))
  end

  def binary(arg, op)
    seq(ref(arg), rep(seq(ref(:_), op, ref(:_), ref(arg)), 1))
  end

  def _
    rep(str(" "), 0)
  end
end

Now, this parser may be correct in that it recognises and parses the strings we give to it into the trees we expect. However, to be practical we generally want parsers to be fast, which usually means the time they take to run is proportional to the length of the input. We say such a parser runs in linear time. A naive recursive descent parser typically won’t do that, for several reasons. The most common are that, every time it has to make a choice it tries every alternative, producing a large tree of possible code paths, or, that it repeatedly tries to match the same rule at the same offset, effectively recomputing a result that’s already known. Both these effects contribute to simple implementations running in exponential time on the length of the input.

Mitigating the first kind of problem, that of spending too long finding out which choice to make, can be done using predictive parsing. The parser compares the next character of input to the first element of each alternative, only pursuing those alternatives it knows to begin with that character. Unfortunately, this works best when each alternative expression begins with a terminal – a string literal, rather than a reference to another rule – and this means our grammar must be restructured into a less natural form. It also restricts the set of languages such parsers are able to recognise.

However, the second kind of problem, that of performing redundant work for already-known results can be verily easily fixed with some simple and localised changes to our implementation. All that is required is for the results of each parsing rule to be cached, so they are not re-computed. This technique is called memoisation.

Fortunately, we can make some very simple and localised changes to our implementation to stop such things happening. Each use of a rule in the grammar is implemented by a called to ref(name), and that call gives us an opportunity to insert a cache based on the name of the rule we’re invoking.

In our implementation, calling a rule is actually a two-stage process. In ref, we use __send__(name) to invoke the method for a rule, and this uses the methods in ParserCombinators to construct a parser, which is essentially a set of nested lambdas. Then, we call call(state) on the result of the first call to have the newly minted parser process the input. Our first memoisation improvement comes from recognising that the result of the first call – the construction of the parsing expression – will always be the same, since the rules don’t change between invocations. Therefore we can keep a cache of these parsing expressions and have ref populate the cache the first time it encounters each rule.

class RefCachedArithmetic
  def ref(name)
    @ref_cache ||= {}

    -> state {
      @ref_cache[name] ||= __send__(name)
      @ref_cache[name].call(state)
    }
  end
end

To test this, we’ll try parsing the following randomly generated expression:

399 + 422 * (778 * (851 * 867 * 454 * 599 + 408 * 300 +
988 * 610 * 164 * 315 + 930 * 14) * (608 + ((849))) *
(81) + 102 * 768 + (50) + 967 * 263 + 251) + (744)

I’m using the benchmark-ips library to measure how many times per second each parser can execute:

Benchmark.ips do |bm|
  bm.report "combinators" do
    Arithmetic.new.parse(expression)
  end

  bm.report "ref cache" do
    RefCachedArithmetic.new.parse(expression)
  end
end

The results show that just caching the generated parsers gives roughly a 50% performance improvement over the original implementation, on this input.

 combinators    213.980  (± 3.3%) i/s -      1.080k in   5.052557s
   ref cache    333.491  (± 4.8%) i/s -      1.664k in   5.001283s

This parser-caching trick is only a partial solution though. The second step in ref is to call the generated parser with our input, and this is where much of the redundant work happens in these parsers. Because of the way we need to structure grammars to express precedence and repetition, we end up trying the same rule at the same position multiple times.

Say we’re given just the input 42 to parse. We begin in the expression rule, which tries to match addition / term. We try addition first, which has the form term (_ "+" _ term)+, so the first thing addition tries to match is a term. A term is multiplication / factor so we try multiplication first, which is factor (_ "*" _ factor)+, so now we try to match factor. factor is number / paren_expression so we try number first, and finally we reach a rule with terminal expressions. To reach this point we have the following rules on the stack:

expression        <-  addition / term

addition          <-  term (_ "+" _ term)+

term              <-  multiplication / factor

multiplication    <-  factor (_ "*" _ factor)+

factor            <-  number / paren_expression

number            <-  "0" / [1-9] [0-9]*

number matches the input 42 at offset 0 and moves the offset to 2, the end of the string. Since number succeeded, we pop it off the stack and also factor which called it, leaving us partway through the multiplication expression:

expression        <-  addition / term

addition          <-  term (_ "+" _ term)+

term              <-  multiplication / factor

multiplication    <-  factor (_ "*" _ factor)+
                             ^

multiplication now wants to see zero or more spaces followed by a * character, but we have reached the end of the input and so no further matching is possible. Therefore multiplication fails and we pop back up to the next alternative in term:

expression        <-  addition / term

addition          <-  term (_ "+" _ term)+

term              <-  multiplication / factor
                                       ^

term began by attempting to match multiplication at offset 0, so it now tries to match factor at the same position. But we’ve already done this work when we tried to match multiplication: we tried factor which in turn tried number which yielded a match and moved the offset to the end of the input. So we know factor succeeds here, and so we can pop term off the stack and return to trying to match addition:

expression        <-  addition / term

addition          <-  term (_ "+" _ term)+
                           ^

Now the same thing happens with addition that we saw in multiplication: the rule expects more characters but we’ve reached the end of the input. So, addition fails and we try the other alternative in expression:

expression        <-  addition / term
                                 ^

We’re left trying to match term at position 0, and again this is work we’ve already done: term tries to match multiplication, which tries factor, which tries number, which matches, and so factor succeeds, then we pop back up into multiplication and find it fails on the next character, so we go back to term‘s next alternative, which is factor, which tries number, which succeeds, and now we can unwind all the way back to the top and discover that expression matched a number.

All in all, we’ve called number four times in order to match the input 42. Each call to term resulted in factor being called twice: once as the first item in multiplication and once as the second alternative in term. Calling expression similarly resulted in calling term twice. We can visualise the above using the following call tree:

                                    expression
                                     /       \
                                   /           \
                                 /               \
                               /                   \
                       addition                     term
                      /                            /    \
                  term                multiplication    factor
                 /    \                         /          \
    multiplication    factor              factor            number
              /          \                  /
        factor            number      number
          /
    number

Rule structures like this, where one alternative is tried, followed by a fallback with the same beginning item, are very common in programming languages and this call pattern results in the parser taking an exponentially longer amount of time as the grammar grows in structure.

Although this seems like a terrible situation, the retrying of the same rule at the same offset provides an excellent opportunity to cache things. We can augment our ref function with a cache based on the rule name and input offset, such that the named parsing function is only invoked if the cache does not already contain an entry for the current rule and offset. Since each parsing function returns both a parse tree and the new state, the cached values will also make the parser continue from the correct offset when they are used.

class NodeCachedArithmetic
  def ref(name)
    @node_cache ||= {}
    @ref_cache  ||= {}

    -> state {
      key = [name, state.offset]

      unless @node_cache.has_key?(key)
        @ref_cache[name] ||= __send__(name)
        @node_cache[key] = @ref_cache[name].call(state)
      end

      @node_cache[key]
    }
  end
end

Now, what happens when we parse 42 is much simpler. As before expression tries addition, which tries term, which tries multiplication, which tries factor, which calls number, and that succeeds. So we store a cache result for (number, 0). factor has succeeded so we also store the same result in the cache for (factor, 0). Then multiplication fails and term tries factor, but now the result for factor can be plucked out of the cache. This in turn makes term succeed so we put the same result in for (term, 0) and so on up the stack. When addition fails and we fall back on term this is again just a cache lookup away. This eliminates most of the function calls in the original implementation, since no function is ever called twice at the same offset:

                              expression
                               /
                       addition
                      /
                  term
                 /
    multiplication
              /
        factor
          /
    number

This modification makes a substantial improvement to performance on our test input:

 combinators    213.625  (± 4.7%) i/s -      1.080k in   5.066901s
   ref cache    343.193  (± 2.9%) i/s -      1.736k in   5.062538s
  node cache    518.276  (± 3.3%) i/s -      2.600k in   5.022265s

In general, this simple caching modification means inputs can be parsed in linear time with arbitrary amounts of lookahead. The technique is known as packrat parsing, and is explained in a brief paper by Bryan Ford, the inventor of parsing expression grammars, and explored more fully in his master’s thesis.

While this makes a big improvement to how the runtime of the parser scales with the input size, the method of implementation itself can still be changed to yield large constant-factor improvements. For example, we can take our grammar and transcribe it using a parser generator, which will generate code for us. I maintain such a tool, called Canopy, in which the grammar would be expressed as follows:

grammar CanopyArithmetic

expression        <-  addition / term
addition          <-  term (_ "+" _ term)+
term              <-  multiplication / factor
multiplication    <-  factor (_ "*" _ factor)+
factor            <-  number / paren_expression
number            <-  "0" / [1-9] [0-9]*
paren_expression  <-  "(" _ expression _ ")"
_                 <-  " "*

Canopy can convert this grammar into a Ruby class, and we can benchmark that against our previous implementations:

 combinators    211.650  (± 4.3%) i/s -      1.064k in   5.036935s
   ref cache    331.979  (± 4.2%) i/s -      1.683k in   5.078639s
  node cache    509.117  (± 3.7%) i/s -      2.550k in   5.015619s
      canopy      1.546k (± 4.7%) i/s -      7.752k in   5.024497s

Canopy makes roughly a 200% improvement over our previous best attempt. Although in an abstract sense it’s doing the exact same computation as our combinator-based implementation, it avoids a lot of the cost the combinators carry in Ruby and some other languages. To run all those nested lambdas means making a lot of function calls, which can be expensive since a stack frame must be allocated and control must jump to the new function and return again. In contrast, Canopy generates all the code for implementing each parsing expression inline within each parsing function. This results in a lot of verbose impenetrable code, but it runs much faster.

Still, despite these improvements, there is still much room for the parser writer to affect things. For example, rather than implementing an if-statement with optional else as:

if_statement  <-  "if" expression "then" expression "else" expression
               /  "if" expression "then" expression

We might want to avoid re-matching the if and then by putting the whole shared section in its own rule, to take advantage of caching:

if_statement  <-  if_then "else" expression
               /  if_then

if_then       <-  "if" expression "then" expression

Or we could use the ? operator to match the else section if present, without having to re-match the first section at all.

if_statement  <-  "if" expression "then" expression ("else" expression)?

There are usually many ways of expressing the same language, and it’s up to the parser writer to make an acceptable trade-off between the clarity of the grammar, the resulting parse tree, and the runtime performance given their chosen parsing strategy. Indeed sometimes, caching does not actually help on common inputs – the cache lookup itself comes with a cost and that can outweigh the benefit if your grammar does not often retry rules at the same offsets. The parser generator PEG.js has an option to turn off caching in its generated parsers for this reason.

Still, despite the performance problems, parser combinators, PEG generators and other top-down techniques remain a great tool for prototyping since a naive but correct parser can be implemented with relatively little machinery. Expressing the grammar using declarative rules makes it easier to switch to a different tool later without having to rewrite too much code.

If you’ve enjoyed this article, you might enjoy my recently published book JavaScript Testing Recipes. It’s full of simple techniques for writing modular, maintainable JavaScript apps in the browser and on the server.