Re: regular expression operators in CF grammars

> 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

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