Next: Interactive inputs, Previous: Handling whitespace, Up: Top [Contents][Index]
13 Left recursion
An obvious next step for our calculator would be to add subtraction. Unfortunately, this is not as simple as you’d hope. Let’s rewind to a simpler grammar, our first adder, which looks like this:
Sum <- d:Decimal "+" s:Sum -> { d + s }
/ Decimal
Decimal <- [0-9]+ -> { atoi(ref_str()) }
Implementing subtraction looks simple; add another alternative to the ‘Sum’ rule, like this.
Sum <- d:Decimal "+" s:Sum -> { d + s }
/ d:Decimal "-" s:Sum -> { d - s }
/ Decimal
This correctly evaluates ‘3-2’ giving the answer 1. Unfortunately, if we ask it to evaluate ‘3-2-1’, it gives the answer 2, where we were expecting 0. It has made subtraction right associative, so ‘3-2-1’ is evaluated as ‘3-(2-1)’. In everyday life, subtraction is considered left associative, and ‘3-2-1’ should mean the same as ‘(3-2)-1’.
In a CFG, we could solve the problem by rearranging the rule to look for a Sum first, something like this. (Since addition is commutative, it doesn’t matter whether or not we rearrange the first branch of the rule.)
Sum <- d:Decimal "+" s:Sum -> { d + s }
/ s:Sum "-" d:Decimal -> { s - d }
/ Decimal
But this won’t work in a PEG. When we try to compile it, pacc tells us:
pacc: fatal: left recursion in rule `Sum'
The second alternative in this rule effectively says: “To match a Sum, first try to match a Sum...”. That’s an infinite loop, and pacc won’t accept it. The exact rule is that each alternative of each rule must make some progress—consume at least one character from the input—before calling itself, whether that call is made directly, or through another rule.
Getting back to subtraction, I’m afraid the sad news is that implementing a left associative operator in the current version of pacc is very difficult. Left recursion is, without doubt, the Achilles’ heel of PEG parsing, and there are many ideas about how to handle it better. I have my own thoughts, which may see the light of day in a future release.
One option that works with current versions of pacc is to build a list, then reverse it. Here’s a self-contained example that does just that, and can correctly subtract three integers. Whether this could sanely be extended to a more complete expression parser, such as those found in typical programming languages, I do not know.
{
#include <stdio.h>
/* A future version will avoid needing this predeclaration. */
int pacc_wrap(const char *, char *, size_t, int *);
struct action { char op; int val; };
struct action *stack = 0, *sp = 0, *alloc = 0;
void push(char op, int x) {
if (sp == alloc) {
int s = alloc - stack;
int n = 2 * s + 1;
stack = realloc(stack, n * sizeof *stack);
if (!stack) pacc_nomem();
alloc = stack + n;
sp = stack + s;
}
sp->op = op; sp->val = x;
++sp;
}
int eval(void) {
int a;
while (--sp >= stack) {
switch (sp->op) {
case ' ': a = sp->val; break;
case '+': a += sp->val; break;
case '-': a -= sp->val; break;
}
}
return a;
}
int main(int argc, char **argv) {
int result;
if (argc != 2) {
fprintf(stderr, "one argument please\n");
return 1;
}
if (pacc_wrap("arg", argv[1], strlen(argv[1]), &result))
printf("parsed with value %d\n", result);
else
return 1;
return 0;
}
}
Expr <- d:Decimal ExprTail { push(' ', d), eval() }
ExprTail <- "+" d:Decimal ExprTail { push('+', d), 0 }
/ "-" d:Decimal ExprTail { push('-', d), 0 }
/ % { 0 }
Decimal <- "-"? [0-9]+ { atoi(ref_str()) }
Next: Interactive inputs, Previous: Handling whitespace, Up: Top [Contents][Index]
Last updated: 2016-08-03 21:39:50 UTC
News
One thing pacc needs is more users. And, perhaps, one way to get more users is to reduce the friction in getting started with pacc. An obvious lubricant is packaging. Read More...
Looking at _pacc_coords(), I noticed that it seemed to have the same realloc() bug that I'd just fixed in _pacc_result(). However, the "list of arrays" trick really wasn't going to work here. Read More...
