Re: regular expression operators in CF grammars

"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

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