21 Jul 2002 02:04:35 -0400

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

[3 later articles] |

From: | "Torben Ægidius Mogensen" <torbenm@diku.dk> |

Newsgroups: | comp.compilers |

Date: | 21 Jul 2002 02:04:35 -0400 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 02-07-057 |

Keywords: | parse |

Posted-Date: | 21 Jul 2002 02:04:35 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.