Re: regular expression operators in CF grammars

Ralph Boland wrote:
> I assume then that you are
> saying that Lalonde's algorithm will fail to detect to the right or
> left hand side of a production in circumstances other than described
> in his papers. (Note that Lalonde has implemented his algorithms and
> to my knowledge they work as described.)


The problem I have with LaLonde's work is its lack of theory. He
presents definitions, an algorithm telling how to construct what
he calls an "LR(m,k) parser", and some examples. There is no proof
at all whether his algorithm works correctly. (And it hasn't been
presented up to the present day as far as I know.)


What I know is that an LR(m+1,k) parser (according to LaLonde) is
no more powerful than an LR(m,k) parser for m>0, so there is no
true hierarchy in the look-back parameter m.


And also, as I had pointed out, I believe that abstracting from
the structure of rhs expansions upon reduction (as LaLonde and
some other authors suggest) is indequate for the purposes of
compiler-related syntax analysis. See my latest answer to the
posting of Chris F Clark in this thread for some reasoning.


Regards,
Sönke Kannapinn

Return to the comp.compilers page.
Search the comp.compilers archives again.