I've recently written a Java parser by hand (https://github.com/tanin47/javaparser.rs) and aimed to emulate a bottom-up parsing as much as possible.
The hand-written bottom-up parsing approach seems more intuitive because it enables us to construct`left` + `right` immediately before looking further.
For the same problem, the hand-written bottom-up parsing approach would look like below:
left, input = expr2(input)
return expr1_tail(left, input)
def expr1_tail(left, input):
if input == '+':
right, input = expr2(s[1..]);
new_expr = BinaryOp(left, input, right);
return expr1_tail(new_expr, input);
return left, input
if input == '(':
new_expr, input = expr1(input[1..])
assert input == ')'
return new_expr, input[1..]
# parsing numbers here
return number, the_rest_of_input
Please note that memorization is a simple trick to solve a lot of parsing problems. I developed an intepretting parser, that basically does back-tracking, which is sped-up with memorization. Because the core interpretter is relatively small (fits in primary cache), it performs quite well. You simply give it a very natural looking grammar, with some annotations, and it builds you an abstract parse tree. I also implemented an unparser, which can be used to produce nicely formatted output for each abstract parse tree (just using the same grammar, with some annotations about where to insert line breaks and indentation). For more details see https://github.com/FransFaase/IParse
Then I realized it was an author I knew.
LeftRec <= LeftRec ‘+’ Term
It's nice to be able to handle left-recursive grammars in a PEG parser. It feels liberating. Although I never used it to write my dream programming language :-).
Note that the same thing can be done via a stack of alternate parsers: when the recursive parser is on top of the stack, then the one below it shall be chosen.