http://lists.canonical.org/pipermail/kragen-tol/2010-July/000921.html
Can an approach like this be extended to parsing more general context-free languages? I feel sure that it can, but the way my mind works, I’d have to work out the details on a specific language.
Seems likely, given that the reverse of a CFL is also a CFL, and we have the following general argument:
Jeremy Gibbons, "The Third Homomorphism Theorem" http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/thirdht.ps.gz
The *Third Homomorphism Theorem* is a folk theorem of the constructive algorithmics community. It states that a function on lists that can be computed both fro left to right and from right to left is necessarily a *list homomorphism* -- it can be computed according to *any* parenthesization of the list.
In other words, if it works as either a fold or a foldr (eg. operator precedence), it will (can be made to) work as a parallel prefix.
Note that, even if it is possible, often languages are more convenient to parse forwards than backwards (and then there's APL, which I believe is more simply processed backwards than forwards). I wonder if the enclosed clauses of Algol-68 (if...fi, do...od, etc.) were explicitly meant to be just as easily parsed in reverse, or if it was simply a side effect of eschewing arbitrary choices?
-Dave -- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
