pacc logo

Rethinking feeding

I thought I'd cracked it. Following Bryan Ford, I have always written my spacing at the end of “lexical” rules, with an additional call at the beginning of the start rule. For example, picking up again a slightly improved version of our trivial digit adder, and again ignoring feeding for the moment I would have written:

Sum ← _ a:Digit Plus b:Digit → { a + b }
Digit ← [0-9] _  → { *ref_ptr(ref()) - '0' }
Plus :: void ← "+" _
_ ← [ \t\n] *

As previously discussed, to turn this into a feeder, we have to do more than declare _ as our feed rule. But consider this equivalent grammar:

Sum ← a:Digit Plus b:Digit _ → { a + b }
Digit ← _ d:[0-9] → { *ref_ptr(d) - '0' }
Plus :: void ← _ "+"
_ ← [ \t\n] *

All that has happened is that the lexical elements pick up space before their element. Of course, that means the start rule doesn't need to match initial space, but it does need to pick up final space instead. Now with this grammar, if we simply declare _ to be the feed rule, it all works! Well, apart from the call at the end of the start rule, but we can easily make an exception for the first rule.

So I implemented all that, and it worked fine. I even got as far as changing the default name for the feed rule to a single underscore. Then I tried it on a slighlty more realistic example. Specifically this one:

Sum :: int ← a:Additive _ → a
Additive ← m:Multitive Plus a:Additive { m + a } / m:Multitive -> m
Multitive ← p:Primary Times m:Multitive { p * m } / p:Primary -> p
Primary ← Left a:Additive Right -> a / d:Decimal -> d
Decimal ← _ [0-9]+ { atoi(ref_ptr(ref())) }
Left :: void ← _ "("
Right ← _ ")"
Plus ← _ "+"
Times ← _ "*"
_ ← [ \t\n] *

The critical difference here is that the rules form a loop. If we declare _ as the feed rule (recall that cooking replaces ... _ foo with ... _ (foo / !.)) then we end up with left recursions. In the grammar above, the recursion is in Additive, since we end up at Primary, the cooked alternative in Left doesn't consume anything, and we're back to Additive.

That's not quite true. When I first tried it, the grammar actually compiled, and then went into an infinite loop. It turns out that cooked grammars aren't subject to preening. And then even when I fixed that, I hadn't implemented the left recursion test properly for predicates. So if nothing else this little excursion has improved the code base a little.

At first I thought that I could get away with it by removing the _ call from Left (and hoping I could fix that up somewhere else later). But no, that just shifts the left recursion to Multitive (exercise for the reader).

So this idea won't fly. I'm slightly glad, because I really like the idea of using $ to mark feed points, even though it will be more work.

Last updated: 2015-05-24 19:45:23 UTC

News

Porting and packaging

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...

Release relief

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...

See more news articles

feed