Re: First vs Predict and LL(*)

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.

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