Great blog. I haven't used PEG and have learned a lot from this post. However, handling left-recursive in PEG seems complex.<p>I've recently written a Java parser by hand (<a href="https://github.com/tanin47/javaparser.rs" rel="nofollow">https://github.com/tanin47/javaparser.rs</a>) and aimed to emulate a bottom-up parsing as much as possible.<p>The hand-written bottom-up parsing approach seems more intuitive because it enables us to construct`left` + `right` immediately before looking further.<p>For the same problem, the hand-written bottom-up parsing approach would look like below:<p><pre><code> def expr1(input):
left, input = expr2(input)
return expr1_tail(left, input)
def expr1_tail(left, input):
if input[0] == '+':
right, input = expr2(s[1..]);
new_expr = BinaryOp(left, input[0], right);
return expr1_tail(new_expr, input);
else:
return left, input
def term(s):
if input[0] == '(':
new_expr, input = expr1(input[1..])
assert input[0] == ')'
return new_expr, input[1..]
else
# parsing numbers here
return number, the_rest_of_input
</code></pre>
(Please excuse my python... I'm a bit rusty)