3

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.

hippietrail
  • 15,848
  • 18
  • 99
  • 158
Alex
  • 61
  • 4
  • 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: stackoverflow.com/a/69581887/14298586 – Nikolay Handzhiyski Oct 16 '21 at 04:18

3 Answers3

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

user541686
  • 205,094
  • 128
  • 528
  • 886
  • thanks, it's crazy how some people can explain things either so simply or with such complexity. – Alex May 17 '11 at 18:37
  • @Alex: Haha thanks. Btw, might want to take a look at [D's lexical features](http://digitalmars.com/d/2.0/lex.html) ("Phases of Compilation"). -- it explains some things about ambiguity and grammar. Also see [this page on templates](http://www.digitalmars.com/d/2.0/templates-revisited.html). – user541686 May 17 '11 at 18:40
  • @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. – user541686 May 17 '11 at 18:44
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
MRAB
  • 20,356
  • 6
  • 40
  • 33
  • 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*. – user541686 May 17 '11 at 18:41
0

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.

PeterN
  • 29
  • 2