Re: Have I discovered something new?

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.

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