4 Jul 2002 23:20:20 -0400

Related articles |
---|

[10 earlier articles] |

Re: regular expression operators in CF grammars soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2002-06-28) |

Re: regular expression operators in CF grammars cfc@world.std.com (Chris F Clark) (2002-07-02) |

Re: regular expression operators in CF grammars cfc@world.std.com (Chris F Clark) (2002-07-02) |

Re: regular expression operators in CF grammars joachim_d@gmx.de (Joachim Durchholz) (2002-07-02) |

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

[2 later articles] |

From: | "Ralph Boland" <rboland@unb.ca> |

Newsgroups: | comp.compilers |

Date: | 4 Jul 2002 23:20:20 -0400 |

Organization: | University of New Brunswick |

References: | 02-05-142 02-05-151 02-06-024 02-06-056 02-06-090 |

Keywords: | parse, theory |

Posted-Date: | 04 Jul 2002 23:20:19 EDT |

*> Unfortunately, closer analysis of the publications that deal with*

*> extended context-free grammars (ecfgs) or regular right part grammars*

*> (rrpgs) reveals some severe errors, and in my humble opinion, most of*

*> these publications are more or less disappointing. m ...*

*>*

*> Nearly all contributions to ELR parser construction -- namely LaLonde*

*> (1977, 1979), ...*

*> have a concept of ELR(k)-derivation step in which a lhs*

*> nonterminal is replaced by some expansion of the corresponding rhs*

*> (i.e., a sentence described by the rhs finite automaton or regular*

*> expression) IGNORING how that rhs expansion had been achieved. In*

*> other words: all these authors abstract from the structure of rhs*

*> expansions.*

*>*

*> Not only do I personally believe that this abstraction is inadequate*

*> for the purpose of compiler construction. The above mentioned authors*

*> also do not treat that abstraction correctly in their parser*

*> constructions in the light of the results of Heilbrunner (1979).*

I cannot speak for all the authors you speak of but I am (somewhat)

familiar with Lalonde's work and I don't understand the difficuly.

Lalonde papers is concerned with the recognition of the left and right

hand side of each production (handle) during parsing. These papers do

not in any way attempt to include the parsing of the regular

expressions on the right hand side of productions as part of parsing a

sentence. This is perhaps (and I think so) a weakness in that this is

quite useful but it is not an error. 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.) I also have a partial

implementation of his algorithm but since it is not complete I cannot

personnally attest to its correctness.

As I have said before, your thesis sounds like interesting and useful

reading and I hope you find the time to translate it into English or

at least write some papers in English based on your thesis results. I

for one am anxious to read it/them.

In any case, thanks for the references. I shall check them out.

Ralph Boland

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.