Re: regular expression operators in CF grammars

"Sönke Kannapinn" <nospam@snafu.de>
10 Aug 2002 02:27:32 -0400

          From comp.compilers

Related articles
[14 earlier articles]
Re: regular expression operators in CF grammars soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2002-07-04)
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-07-04)
Re: regular expression operators in CF grammars rboland@unb.ca (Ralph Boland) (2002-07-04)
Re: regular expression operators in CF grammars cfc@world.std.com (Chris F Clark) (2002-07-15)
Re: regular expression operators in CF grammars kgw-news@stiscan.com (2002-07-21)
Re: regular expression operators in CF grammars nospam@snafu.de (Sönke Kannapinn) (2002-08-10)
Re: regular expression operators in CF grammars nospam@snafu.de (Sönke Kannapinn) (2002-08-10)
Re: regular expression operators in CF grammars cfc@shell01.TheWorld.com (Chris F Clark) (2002-08-23)
Re: regular expression operators in CF grammars tbandrow@unitedsoftworks.com (tj bandrowsky) (2002-09-03)
Re: regular expression operators in CF grammars cfc@shell01.TheWorld.com (Chris F Clark) (2002-09-12)
Re: regular expression operators in CF grammars cfc@TheWorld.com (Chris F Clark) (2002-09-14)
| List of all articles for this month |

From: "Sönke Kannapinn" <nospam@snafu.de>
Newsgroups: comp.compilers
Date: 10 Aug 2002 02:27:32 -0400
Organization: [Posted via] Inter.net Germany GmbH
References: 02-05-142 02-05-151 02-06-024 02-06-056 02-06-090 02-07-033
Keywords: parse
Posted-Date: 10 Aug 2002 02:27:32 EDT

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


Post a followup to this message

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