4 ms·
The trick is to pass down previous syntax nodes so that you can continue consuming input (via top down recursive descent) but build the syntax tree bottom up st
by norswap 4y ago
The trick is to pass down previous syntax nodes so that you can continue consuming input (via top down recursive descent) but build the syntax tree bottom up still.
This is exemplified in the two definitions of `parse_add_addexpr_cont` in the article.
- amir734jj 4y agoWhy? what was wrong with regular LR parser?
- norswap 4y agoIt's fairly easy to teach the behaviour of LR parsers (though which grammars end up being LR and which end up conflicting is very inintuitive). It's much harder to teach the inner working / implementation of such parsers. Table generation adds an extra layer of indirection. I skip this in my class, because I doubt it will be very valuable to students to be able to implement an LR parser compared to other things we cover in the class. Doing the OP's approach, you can get some intuition for how a LR parser behaves / is implemented without going to the full complexity.
- Joker_vD 4y agoRecursive-descent would usually (there are several options) write `parse_addexpr` somewhat like this: Expr parse_addexpr() { Expr result = parse_mulexpr(); while (peek_token() == TokenType.PLUS) { expect_token(TokenType.PLUS); Expr rhs = parse_mulexpr(); result = new AddExpr(result, rhs); } return result; } which corresponds to "addexpr: <mulexpr> (+ <mulexpr>)*" but with left-associative tree-composing.