Re: Have I discovered something new?

"Stephen Horne" <steve.horne@iris.co.uk> writes:




> 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.
>
> Is this still the state of play?
>
> 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
> scentence is ambiguous it will give all possible parsings. 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.


It has ben proven that ambiguity of CFG's is undecidable, so if you
believe your method can find all ambiguity (and have no false
positives), you are wrong. However, like LR parsers, you may be able
to find potential ambiguity and definite non-ambiguity.


> So really, I want to know whether this is worth persuing (ie has it
> already be done). If not, how should I go about releasing the idea
> into the wild - is there a suitable journal, for instance.


It is hard to judge if your method has been tried before without more
details. Your best approach is to first implement the method, try it
out on a number of grammars, write up the method as a paper (making
sure you are very precise about what you do) and send that to a
conference or journal. Also be very precise about the proof of
linearity. A set of test runs aren't enough, but you may use such to
convince yourself that your method is linear-time (or otherwise).


Some grammars to check:


The grammar for the language consisting of even-length strings such
that the two halves are _not_ equal:


S -> AB | BA
A -> a | CAC
B -> b | CBC
C -> a | b


Good test string are strings such that the first half is random and
the second half is a copy of that with one random character changed as
well as negative cases (where the two halves are equal).


The grammar for the set of strings that are a concatenation of 5
nonempty palindromes:


S -> PPPPP
P -> aPa
P -> bPb
P -> a
P -> b


Test cases should be catenations of randomly generated palindromes and
random strings with different ratios of a's and b's (1:1, 1:10, 1:100
etc.)


The grammar for strings with an equal number of a's and b's:


S -> aSbS
S -> bSaS
S ->


Test cases are just random strings with equal probability for a's and
b's.


Torben Mogensen (torbenm@diku.dk)

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