Re: simple vs. complex parsers

Robert A Duff wrote:
> Hmm. I'm not sure I agree. Do we really want tools that can parse
> ambiguous grammars, if that encourages language designers to create
> ambiguous grammars? Are ambiguous grammars good for human readers?


I was under the impression that ambiguous grammars were a bigger
problem to computers. Human languages use extremely ambiguous grammars
which we solve using an enormous amount of context, be it the topic of
the conversation, usage or whatsoever. Computers on the other hand
have some hard time with nondeterminism. So being able to parse
ambiguous grammars is a quality when facing natural languages (and
that's Tomita's field of research), but it could turn into a drawback
for computer languages.


Joachim Durchholz wrote:
  > The only downside is that the parser generator won't tell you whether
  > your grammar is ambiguous. Nothing that a separate "grammar checker"
  > tool couldn't handle (that checker would need assistance from the
  > grammar writer, since the problem is undecidable in general).


Does anyone know a tool like this?
I've found the DMS Reengineering Toolkit, which automatically attempts
to tell whether the grammar is ambiguous or not
(http://compilers.iecc.com/comparch/article/00-02-029 and
http://www.semdesigns.com/Products/DMS/DMSToolkit.html), but I have no
idea of its efficiency.
Another solution would be to use a parser generator like bison and tweak
and distort the grammar until we're sure it's not ambiguous, but in that
case the risk of actually changing the language it generates is real.


I believe noncanonical methods have still something to offer, being
able to parse wide classes of grammar in a deterministic way (see
http://www.eecg.toronto.edu/~mdhutton/papers/noncan.pdf). I'd like to
gather some opinions on this point.


      Sylvain

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