4 Jul 2002 23:07:01 -0400

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

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.