Pedagogically, I think it’s better to talk about recursive descent+Pratt parsing, or just Pratt parsers. Pure recursive descent is indeed quite inadequate, and many CS students (raises hand) indeed don’t realize how to parse arithmetic expressions manually.

I just do not get this. Pratt parsers, shunting, etc. are way more complex thank simple, hand-done recursive descent parsers. I’m lazy, hence I use recursive descent.

The discussions here about + - * / seem overblown to me. Take a language def something like what was found in one of the other posts:

<E> ::= <E> <op> <E>
     | ( <E> )
     | <D>
<op> ::= + | - | * | /
<D> = [0-9]+

Convert it to an LALR(1) form:

Expression
     AdditiveExpression

AdditiveExpression
    MultiplicativeExpression
    AdditiveExpression "+" MultiplicativeExpression
    AdditiveExpression "-" MultiplicativeExpression

MultiplicativeExpression
    PrimaryExpression
    MultiplicativeExpression "*" PrimaryExpression
    MultiplicativeExpression "/" PrimaryExpression

PrimaryExpression
    "(" Expression ")"
    Digit*

And you’re already pretty much done. Now you just need some code, something like:

Expression parseExpression()
    {
    return parseAdditive();
    }
    
Expression parseAdditive()
    {
    Expression expr = parseMultiplicative();
    while (true)
        {
        switch (peek())
            {
            case Add:
            case Sub:
                expr = new RelationalExpression(expr, current(), parseMultiplicative());
                break;

            default:
                return expr;
            }
        }
    return expr;
    }

Expression parseMultiplicative()
    {
    Expression expr = parsePrimary();
    while (true)
        {
        switch (peek())
            {
            case Mul:
            case Div:
                expr = new RelationalExpression(expr, current(), parsePrimary());
                break;

            default:
                return expr;
            }
        }
    }

Expression parsePrimary()
    {
    switch (peek())
        {
        case LParen:
            expect(LParen);
            Expr expr = parseExpression();
            expect(RParen);
            return expr;
            
        case Digit:
        default:
            // this will correctly report an error if there are no digits
            return eatDigitsAsLiteral();
        }
    }

Sorry for so much code, but after you do this a few times, the scary complexity disappears, and it’s just cut & paste. But I admit, the first time was really hard to understand how to transform weird EBNF (etc.) into something simpler to comprehend. It’s the one time that the dragon book came in handy.

Pure recursive descent is indeed quite inadequate, and many CS students (raises hand) indeed don’t realize how to parse arithmetic expressions manually.

Is this a hard problem? if you have a grammar say

<E> ::= <E> <op> <E>
     | ( <E> )
     | <D>
<op> ::= + | - | * | /
<D> = [0-9]+

which produces various parses for 1+2*3 =*> [1+2]*2; 1+[2*3] etc, isn’t it sufficient to extract the first parse, and apply shunting yard in the tree that correctly manages precedence? e.g. in any tree that has a child [], flatten the node post-parse, and apply the shunting yard on the children of the node.

“An unambiguous CFG grammar” is not something we can easily recognize.

Offhand I believe I’ve read that telling whether an arbitrary CFG is ambiguous or not is equivalent to the halting problem.

There’s a point in the design space I don’t think has been well explored: declarative Pratt parsing with some extensions like unary/binary and multifix. Simple implementation, linear time parsing, really good error messages. Probably not quite powerful enough to parse big existing languages but I haven’t tested enough to find out. The parse tree it produces is a bit further away from ASTs than what an CFG parser would produce. I implemented a parser generator in this space:

https://github.com/justinpombrio/panfix

Example grammar: https://github.com/justinpombrio/panfix/blob/master/tests/minilang.rs

@ltratt: “There are various ways of implementing parsers, but for me there are generally only two which we really need to consider: LR parsing and recursive descent parsing. “

Parent: I think what they are really trying to say is that there is “automatically generated parsers” and “hand written parsers”

I think what @ltratt is trying to say here is that for him there are only two sane choices. He is not trying to differentiate between handwritten and LR parsers.

He also clarifies later on:

@ltratt: In practice, a recursive descent parser can be thought of as meaning “a hand-written written parser”: unless you go out of your way to do otherwise, nearly all hand-written parsers are recursive descent parsers.

Of course, ANTLR, GLL, etc exist, but I think that is external from the point he is making, which is having a sort of (sound, but incomplete) ambiguity checker.

and they want to argue in favor of automatically generated parsers.

No, @ltratt wants to argue in favor of LR parsing, specifically because @ltratt believes that they are able to identify and reject some of the bad grammars (here bad grammars are those that contain ambiguity). — The bad grammar here is very subjective;

Fundamentally, recursive descent parsers have no equivalent “type checker”, and we know that we can’t build such an equivalent for the general case.

Personally, I prefer LL(1) grammars, and that also provide us with a type checker like what he claims for LR.

@ltratt: There is an additional, easily over-looked, factor that comes from relying on recursive descent parsers: learners cannot, in any sensible time, understand from the recursive descent parser the language’s syntax.

Here though, I think he is talking about handwritten traditional style that implements PEG.

I would reasonably assume the opposite, that table-based parsers are generally faster than recursive descent parsers, since a small table and a small amount of driver code should all be able to fit in the CPU’s cache.

I think LALRPOP optimizes LR by emitting a recursive ascent parser (essentially compile the table to a bunch of functions). It feels (:)) like that should be faster: you essentially say that interpreter is faster than compiler :)

I agree, the OP is conflating “recursive descent” with “hand-written.”

There’s nothing, as far as I know, stopping anyone from writing a parser generator that outputs a recursive descent parser.

Like ANTLR, one of the most popular parser generators, which produces RD parsers.

IIRC, PEG parser generators also output recursive descent parsers. I may be misremembering this, but I’ve looked at the gnarly C code emitted by one and it consisted of a whole lot of little functions, not the giant tables used by LALR parsers.