Path: csiph.com!usenet.pasdenom.info!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Alexander Morou Newsgroups: comp.compilers Subject: Re: First vs Predict and LL(*) Date: Fri, 23 Jan 2015 01:16:51 -0600 Organization: Compilers Central Lines: 69 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-01-041@comp.compilers> References: <15-01-040@comp.compilers> <15-01-003@comp.compilers> <15-01-039@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: miucha.iecc.com 1422065243 54026 2001:470:1f07:1126:0:676f:7373:6970 (24 Jan 2015 02:07:23 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 24 Jan 2015 02:07:23 +0000 (UTC) Keywords: parse Posted-Date: 23 Jan 2015 21:07:23 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com X-Received-Bytes: 4264 X-Received-Body-CRC: 4057501076 Xref: csiph.com comp.compilers:1498 On Thursday, January 22, 2015 at 10:14:19 PM UTC-6, Hans-Peter Diettrich wrote: > Alexander Morou schrieb: > > > This brings me to my next point: what if the point of ambiguity > > leads to a situation where the calling rule's tie for that symbol > > is a requirement for the parse, but the edge state is optional? > > I'd consider that an language error. As you already found out > yourself, your language is not easy to parse, so that I'd expect > that will be equally hard to write valid sentences, which then also > are parsed in the *intended* way. So a typical reaction to such an ambiguity would be to simplify the grammar? I originally followed the C# specification for the language to construct the basic flow of the document. In writing the code to isolate ambiguities, I found a few I did not know about. On such was the description of Object/Collection Initializers: when the set between the curly braces ({ and }) is empty, it yielded an ambiguity because both transitions yielded the same token sets. Fixing that (allowing one path to be empty, the other not) it found that there was another ambiguity between array initialization and the same object initializer when the set is empty. Those 'different rule same input stream' acceptance are a type of ambiguity I'm not interested in allowing. I'm not sure what you'd classify this kind of overlap. I think once I've constructed the means to work around the 'required dangling ambiguity' (the predictive method mentioned earlier) I'll need to flesh out the parser in full before I can say that the automations properly represent the language. There's a known ambiguity within the base C# language that it's not detecting, which either means: 1. The algorithm predicting follow deadlock is incorrect 2. The algorithm predicting the transition paths is incorrect, either because: a. I'm over agressively reducing the transition paths when a point of commonality is found that leads to parse the same sub-rule. b. I'm way off target in how to do this :-| c. Both a and b. :-( 3. I made an error in translating the grammar into the my self-created grammar description language. 4. Other changes to the grammar that deviated from the root resolved the ambiguity by providing further context. This is the least likely candidtate. 5. I'm over simplifying the problem and the complex parse path necessary to isolate the ambiguity isn't attainable because all paths aren't considered. This goes with 2.b. Would there be any advantage to allowing the parser generator to be able to resolve these types of 'required dangling ambiguities'? While I agree that you could view the construction of such an ambiguity to be a language description error, the means to which such a thing would be resolved would ultimately be up to either: a rewrite/simplification of the grammar, or allowing the tool to specify a consistent means to resolving the issue itself. Assuming a valid path is decidable. Though I wonder if the effort of doing this is worth it...? Insight more than welcome.