Hacker News Reader

Comment by mbrubeck | Hacker News Reader

HN formatting messed up your asterisks. The whole rule is:

    multiplicative    : primary "*" multiplicative { return $1 * $3; }
                      / primary

"primary" refers to another rule in the grammar, which is defined as integer or a parenthesized expression. This snippet defines "multiplicative", which is either a primary, or a primary followed by an asterisk followed by another multiplicative. (This recursively expands to allow any number of primaries, separated by asterisks.)

The value of the multiplicative expression is the value of the first term times the value of the third term. (The second term is just the literal string "*".)

View on HN

On the face of it, however, the grammar is problematic. There's a reason it uses "additive", "multiplicative" and "primary" rather than a more traditional expression, term and factor: by using commutative operators like + and multiply, and leaving out - and / it disguises the fact that the grammar is actually evaluating the expression from right to left, rather than the expected order of left to right.

I knew somebody would raise this point :-) You are right that the evaluation order would be wrong for "-" and "/".

I will probably implement support for left recursion in PEG.js - it is possible (see e.g. http://www.vpri.org/pdf/tr2007002_packrat.pdf). After that, the grammar could be rewritten to evaluate in the correct order.

(Another alternative - which works right now - is to change the parsing expressions to something like "additive ([+-] additive)*" and deal with the whole chain of operations with the same priority at once. I didn't use this in the example as I wanted it to be as simple as possible.)

Don't use that paper! I tried to use the parsing technique in that paper while working on a parser for use at the CME, and it caused me weeks of headaches.

First, you'll note the algorithm is extremely complicated--nothing like the simple top-down algorithm that makes PEGs so attractive. Not only is it complicated, it misses basic refactoring issues--some logic is duplicated across functions, and the functions interact in ugly ways.

Second, it doesn't even handle left recursion correctly. Throw a ruleset like this at their parser

A -> B "a"

B -> C "b"

C -> B / A / "c"

and it will explode into a million little pieces, because the authors did not account for any recursive rule having multiple recursion points. Don't even try something like

S -> A / B

A -> A "a" / B / a

B -> B "b" / A / "b"

Interesting, thanks for the warning. I only skimmed through the paper today and noted that the algoritm seems complex, but I didn't attempt to understand it in detail.

What was your final result? Did you implement the left recursion in the way the paper describes, invented/found some other way or abandoned the whole idea?

The approach I'm working on uses the same "growing the seed" idea, but in a different way.

It involves the memo entries being able to remember which left-recursive results they are dependent on. This way, when a left-recursive rule produces a result that is dependent on itself, it knows that this match can possibly be "grown" through repeated iterations. That's a basic sketch of the idea. Performance properties remain the same in the case of left-recursive rules that are not interdependent. I don't really know what they are like for large numbers of interdependent left-recursive rules--but if you have a language like that, better to use an Earley or GLR parser.

I'm still working on it. It passes a battery of test cases, two of which I posted above, but I'm not 100% confident in it just yet. Also, as posted above, I'm trying to get permission from the higher-ups to release the code into the wild.

Neat, I'm onsite at a company right down the block from CME's Clearing devs. Buy you coffee sometime?

Sure--why don't you e-mail me: cynicalkane at gmail dot com

That's not an issue for associative operators, so long as you keep track of precedence. x * (x * x) == (x * x) * x. But it may become an issue for more general grammars that need to handle left-recursion in a non-associative fashion.

The issue is that a top-down grammar cannot handle left-recursion, since it naturally leads to infinite recursion when being parsed from the top down.

I actually had to handle the left-recursion problem for a PEG I wrote in-house--right now I'm trying to convince my boss to let me open-source it :)

The way I would normally handle what would otherwise be left recursion in a top-down parser is to introduce loops.

    term ::= factor ( ('*' | '/') factor )* ;

If you introduce regex-like closure operators to model loops, life gets much easier, and you can build your trees the right way around.

How applicable this is to PEGs is another matter though. I generally write my parsers by hand, and I parse expressions with operator precedence.

This can be done in PEGs, using term rewriting or simple tree rewriting to create a PEG construct like the loop you described. But doing so subverts the elegance of PEG parser, and I'm unaware of a way to make it suffice as a general solution.

The thing is, LL(1) is almost always all you need in practice. Left recursion doesn't buy you a lot more in practice than the loops I describe. But I also don't think PEGs are particularly elegant - I think the translation of LL(1) (including loops) to recursive descent is perfectly straightforward, and I think backtracking combined with memoization is a hack.

And for stuff that LL(1) can't handle, I think GLR is a better approach.

You misunderstand PEGs.

In the simplest version, each rule can be seen as a function that calls other rules, passing along a memo table as it goes. It's entirely stateless and functional, except for the memo table. In addition, each function is only a few lines.

Backtracking isn't a hack--it's the natural result of statelessness. There's no cursor that needs to be backtracked.

I think you don't understand my objection. It's that backtracking is very seldom necessary at all in the first place, whether or not you get rid of the time cost of it. It's like doing something inefficient in the name of source code elegance, then patting yourself on the back when you got rid of the big-O inefficiency. My point is that you needn't have been so inefficient to begin with, and that the more efficient approaches don't suffer unduly from inelegance, and to top it all off, they have a lower constant factor.

The advantage of PEGs is that they are easily understood, easy to code, and easy to code for. In 99% of applications nowdays, these are the only considerations. Performance is a secondary concern or not a concern at all. Given this, the user shouldn't have to worry about backtracking, ambiguity, or lookahead.

Asking the user to have to worry about this stuff, when he doesn't have to, is not good software design. Not all of us are writing high performance parsers for complicated languages.

Thanks, what I don't get from reading the grammar is how, as you say, multiplicative is either a primary or primary followed by a multiplicative. Clearly I understand that it needs to be defined this way, but is that either part just inherit to PEG or this implementation or what, b/c I don't get it form the syntax?

The "/" at the start of the second line is a choice operator. For example, this is how you would define a term a that can match either b or c:

   a: b / c

(The asterisks in my post were escaped because they were in a code block, or because there were not two of them in the same line.)

btw, how did you escape that asterisk in quotes?

Reply on news.ycombinator.com