Re: regular expression operators in CF grammars

"=?Windows-1252?Q?S=F6nke_Kannapinn?=" <soenke.kannapinn@wincor-nixdorf.com>
4 Jul 2002 23:07:01 -0400

          From comp.compilers

Related articles
[8 earlier articles]
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-06-28)
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-06-28)
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)
[5 later articles]
| List of all articles for this month |

From: "=?Windows-1252?Q?S=F6nke_Kannapinn?=" <soenke.kannapinn@wincor-nixdorf.com>
Newsgroups: comp.compilers
Date: 4 Jul 2002 23:07:01 -0400
Organization: Siemens Inc.
References: 02-05-142 02-05-151 02-06-024 02-06-056 02-06-090 02-07-010
Keywords: parse, theory
Posted-Date: 04 Jul 2002 23:07:01 EDT

"Chris F Clark" writes:
> Yes, in other words, a (a*) = a+ = (a*) a = (a a?) a* = ....
> Unfortunately, this is consistent with the standard treatment of
> regular expressions.


What do you mean by "standard treatment of regular expressions"?


There *is*, today, a well understood concept of regular expression
ambiguity. I highly recommend the beautiful article entitled "Regular
Expressions into Finite Automata" by Anne Brüggemann-Klein (TCS 120,
1993) to anyone interested in that field. It defines "weak
unambiguity" and "strong unambiguity" of a regular expression E by
referring to the unambiguity of the corresponding (e-free) Glushkov
NFA or, respectively, to the unambiguity of a corresponding naturally
constructed e-NFA (an NFA with epsilon moves) for E.


> > For ambiguous rhs regular expressions or finite automata this
> > requires some sort of subset construction to remove ambiguity.
>
> And, I believe one could argue that the LR item construction algorithm
> does this subset construction if one *properly* ignores the ambiguity.


Yes.


> I will agree that there are some subtle points in doing this
> correctly.


That's exactly what literature mostly fails to do right.


> Thus, a structure preserving ELR parser generator is no more
> powerful than a LR parser generator where the regular expressions
> have been turned into hidden non-terminals, because it must do
> reductions at the same points.


You only gain in power if you allow *ambiguous* rhs regular
expressions (non-stronly-unambiguous, to be precise), or ambiguous
rhs NFA's. Are you able to write down a compiler-related example
where you really make wise use of this freedom?


After all, we attach semantics to the detailed grammar structure
of an EBNF when targeting compiler construction, don't we? If,
for example, I write down a simple EBNF rule


                S := 'if' E 'then' S ['else' S 'end']


I want to attach semantic code depending on whether the optional part
has actually been seen by the parser or not. In other words: I'm not
only interested in *whether* this rule has been applied but *how* it
has been applied. And *I* don't want to re-match the rhs regular
expression to the actual handle; the parser's handle reduction
machinery should have done so before! And it should have invoked the
appropriate pieces of semantic action code associated with the regular
operators actually applied.


Best regards,
Sönke Kannapinn


Post a followup to this message

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