Re: Have I discovered something new?

kgw-news@stiscan.com
21 Jul 2002 02:10:54 -0400

          From comp.compilers

Related articles
Have I discovered something new? steve.horne@iris.co.uk (Stephen Horne) (2002-07-15)
Re: Have I discovered something new? torbenm@diku.dk (Torben Ægidius Mogensen) (2002-07-21)
Re: Have I discovered something new? joachim_d@gmx.de (Joachim Durchholz) (2002-07-21)
Have I discovered something new? cfc@world.std.com (Chris F Clark) (2002-07-21)
Re: Have I discovered something new? kgw-news@stiscan.com (2002-07-21)
Re: Have I discovered something new? whopkins@alpha2.csd.uwm.edu (Mark) (2002-07-24)
Re: Have I discovered something new? steve@lurking.demon.co.uk (Steve Horne) (2002-07-25)
Re: Have I discovered something new? robert.corbett@sun.com (Robert Corbett) (2002-07-31)
Re: Have I discovered something new? whopkins@alpha2.csd.uwm.edu (Mark) (2002-07-31)
Re: Have I discovered something new? cfc@shell01.TheWorld.com (Chris F Clark) (2002-08-04)
Re: Have I discovered something new? whopkins@alpha2.csd.uwm.edu (Mark) (2002-08-04)
| List of all articles for this month |

From: kgw-news@stiscan.com
Newsgroups: comp.compilers
Date: 21 Jul 2002 02:10:54 -0400
Organization: Solution Technology
References: 02-07-057
Keywords: parse
Posted-Date: 21 Jul 2002 02:10:54 EDT

On Tue, 16 Jul 2002 03:52:07 UTC, "Stephen Horne"
<steve.horne@iris.co.uk> wrote:


> My main question refers to something I read in 'Parsing Techniques, A
> Practical Guide'. This book contained a statement that the possibility
> of an linear-time parsing algorithm for arbitrary context-free
> grammars was still an open question - that there was no proof or
> disproof, that every known context-free grammar can be parsed in
> linear time using specially designed methods, but that no general
> algorithm currently exists which works for all context-free grammars.
>


There are non-linear parsers.
And what do you do with a language that requires infinite lookahead.
For a devious grammer, you may need to
carry all 2 to the N possible parses up to the identifying
token which tells you which one is the correct parse,
You are not going to be linear.




> Is this still the state of play?


But most of the badly designed programming languages we have now are
not context free.




> The reason I ask is that I believe I have found an algorithm to do
> precisely this. It will certainly handle any grammar that a Tomita
> parser will handle, and do so without needing stack duplication. \


> If a sentence is ambiguous it will give all possible parsings.


In linear time?!!!!!!!!!!!!!!!
Non-linear output in linear time! I do not think so.


> If a grammar is ambiguous that can be detected in the precalculated
> tables. It is even possible to give a description of the ambiguity
> using a list of the parts of the distinct parse trees required to
> understand the ambiguity, and to find the context.


You can do that with LRk and LLk but that only tells you why it is not
LRk or LLk. It may still be unambiguous.



Post a followup to this message

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