what is an ambiguous context free grammar?

Question

I'm not really very clear on the concept of ambiguity in context free grammars. If anybody could help me out and explain the concept or provide a good resource I'd greatly appreciate it.

Bluebeard

That is a grammar that can generate at least one sequence in more then one way. A parser using this grammar without transformations, can accept at least one sequence in more then one way. I have written and other related terminology in here: https://mcmap.net/q/83018/-how-to-remove-the-ambiguity-from-the-following-grammar – Clumsy

Answer 1

T * U;

Is that a pointer declaration or a multiplication? You can't tell until you know what T and U actually are.

So the syntax of the expression depends on the semantics (meaning) of the expression. That's not context-free -- in a context-free language, that could only be one thing, not two. (This is why they didn't let expressions like that be valid statements in D.)

Another example:

T<U> V;

Is that a template usage or is that a greater-than and less-than operation? (This is why they changed the syntax to T!(U) V in D -- parentheses only have one use, whereas carets have another use.)

Conn

thanks, it's crazy how some people can explain things either so simply or with such complexity. – Bluebeard

@Alex: Haha thanks. Btw, might want to take a look at D's lexical features ("Phases of Compilation"). -- it explains some things about ambiguity and grammar. Also see this page on templates. – Conn

@Alex: Also, notice that both of those ambiguities are taken care of by putting a rule in the grammar like, "An expression without a function call or an assignment is not a valid statement", because then 2 * 3; would not be valid in the grammar. Not all ambiguities can be resolved like this, though. – Conn

Answer 2

How would you parse this:

if condition_1 then if condition_2 then action_1 else action_2

To which "if" does the "else" belong?

In Python, they are:

if condition_1:
    if condition_2:
        action_1
    else:
        action_2

and:

if condition_1:
    if condition_2:
        action_1
else:
    action_2

Unintelligent

I'm pretty sure that's not a context-freeness issue. The if that the else matches doesn't have to do anything with the actual conditions or actions that are happening, it only has to do with the source code formatting, and/or brace matching. It's a little different from where the result would be different based on what condition_1 actually was. – Conn

Answer 3

Consider an input string recognized by context-free grammar. The string is derived ambiguously if it has two or more different leftmost derivations, or parse trees of you wish. A grammar is ambiguous if it generates strings ambiguously. For example, the grammar S -> E + E | E * E is an ambiguous grammar as it derives the string x + x * x ambiguously, in other words there are more than one parse tree to represent the expression (there are two actually). The grammar can be made non-ambiguous by changing the grammar to:

E -> E + T | T

T -> T * F | F

F -> (E) | x

The refactored grammar will always derive the string unambiguously, i.e. the derivation will always produce the same parse tree.

Jaella