Re: simple vs. complex parsers

Joachim Durchholz <joachim_d@gmx.de>
5 May 2003 23:38:03 -0400

          From comp.compilers

Related articles
[4 earlier articles]
Re: .NET Compiler for Interactive Fiction tbandrow@unitedsoftworks.com (2003-03-16)
Re: .NET Compiler for Interactive Fiction JeffKenton@attbi.com (Jeff Kenton) (2003-04-05)
Re: .NET Compiler for Interactive Fiction joachim_d@gmx.de (Joachim Durchholz) (2003-04-13)
Re: parsing, was .NET Compiler for Interactive Fiction rpboland@math.uwaterloo.ca (Ralph P. Boland) (2003-04-15)
Re: parsing, was .NET Compiler for Interactive Fiction bobduff@shell01.TheWorld.com (Robert A Duff) (2003-04-20)
Re: simple vs. complex parsers cfc@world.std.com (Chris F Clark) (2003-04-27)
Re: simple vs. complex parsers joachim_d@gmx.de (Joachim Durchholz) (2003-05-05)
Re: simple vs. complex parsers bobduff@shell01.TheWorld.com (Robert A Duff) (2003-05-15)
Re: simple vs. complex parsers cfc@shell01.TheWorld.com (Chris F Clark) (2003-05-18)
Re: simple vs. complex parsers schmitz@essi.fr (Sylvain Schmitz) (2003-05-18)
Re: simple vs. complex parsers mal@wyrd.be (Lieven Marchand) (2003-05-18)
Re: simple vs. complex parsers bs@research.att.com (2003-05-18)
Re: simple vs. complex parsers nmm1@cus.cam.ac.uk (2003-05-23)
[2 later articles]
| List of all articles for this month |

From: Joachim Durchholz <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 5 May 2003 23:38:03 -0400
Organization: Compilers Central
References: 03-02-125 03-02-147 03-03-043 03-03-061 03-03-103 03-04-006 03-04-028 03-04-046 03-04-066 03-04-116
Keywords: parse
Posted-Date: 05 May 2003 23:38:03 EDT

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.


Post a followup to this message

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