Re: simple vs. complex parsers

Chris F Clark wrote:
> The ideal goal is a parser generator that can take "any" grammar
> infer what language it is intended to describe and create a correct
> parser. That goal is unattainable,


It's not only attainable, it's already attained: Use a GLR (aka
Tomita) parser generator. It will handle any context-free grammar.


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).


Separating ambiguity checking from parsing would have the charm that the
grammar rewrites to do the checking could be separated from parsing.
This, in turn, would have two advantages:
First, errors during the grammar rewrite have less of an impact (a parse
may fail due to ambiguities - usually something that the application
programmer can fix by adding a parenthese or semicolon where needed).
Second, grammar rewrites for an LR parser generator tend to obscure the
true language structure, making the job of the AST decorator much
harder. If the rewrite is just for purposes of establishing unambiguity,
the rewrite is allowed to be as ugly, contorted, and computer-assisted
as desired, it won't make the life of future compiler writers miserable.


Regards,
Jo
--
Currently looking for a new job.

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