Re: parsing with small memory or on a large parallel machine

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=92d 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