UpstandingHackers/hammer — pull request #93 by pesco (2014-03-21 21:51:40+00:00)
Title: Fix left-recursion with packrat

This makes the following test case (`leftrec-ne`) work (parse "aaa"):

S -> S 'a' | 'a'

It does *not* work with (`leftrec`):

S -> S 'a' | epsilon

To be specific, it always succeeds with an empty parse (the second choice).
I currently think this is actually a case that Warth doesn't work for. It might be a degenerate form of the ones discussed in

http://tratt.net/laurie/research/pubs/html/tratt__direct_left_recursive_parsing_expression_grammars/ .

In fact, I cross-checked against the Scala implementation and it appears to exhibit the same behaviour with the following test program (compare the results or `lr` vs. `lr1`):

import scala.util.parsing.combinator._
import scala.util.parsing.input._

object P extends RegexParsers with PackratParsers {
def a : PackratParser[Any] = elem('a')
def eps : PackratParser[Any] = success("eps")
lazy val lr : PackratParser[Any] = (lr~a) | eps
lazy val lr1 : PackratParser[Any] = (lr1~a) | a

def input = "aaa"

def test() = parse(lr, new PackratReader(new CharArrayReader(input.toArray)))
}

P.test()