Member Avatar for alkeshtech

Hey guys,
is it possible to always remove ambiguity? May be by changing precedence?

Can you always do it? Or no?

  • 2 Contributors
  • 2 Replies
  • 88 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by alkeshtech

Dani AI

Generated

As clarified, the question is about grammars (not C++ overload/name-resolution). 's C++ example concerns a different kind of "ambiguity" (overload resolution at compile time), so it is worth keeping those ideas separate.

Short answer: no — you cannot always remove ambiguity for context-free grammars. Some context-free languages are inherently ambiguous (every grammar for the language is ambiguous), and the general decision problem "is this CFG ambiguous?" is undecidable. For formal statements and a standard example see Ambiguous grammar and Inherently_ambiguous_language.

In practice most ambiguities you hit when designing a programming-language grammar are about operator precedence and associativity. Those are usually fixed either by rewriting the grammar (introduce nonterminals for precedence levels) or by using parser-generator features that encode precedence and associativity. That solves many real-world cases but does not remove inherent ambiguity for arbitrary CFLs.

Practical workflow:

  • Try to produce a concrete witness string that has two different parse trees; a single witness proves the grammar is ambiguous.

  • If you find one, rewrite the grammar to force the intended structure (or use your parser tool's precedence/associativity declarations).

  • If you cannot find a witness, remember undecidability: absence of a witness is not a proof of unambiguity.

  • To accept an ambiguous specification but still parse deterministically, use a general parser that yields a parse forest and then disambiguate semantically (see Generalized LR parser and Earley parser).

Recommended Answers

All 2 Replies

Member Avatar for Ancient Dragon

I don't know about other languages, but in c++ I think it is always possible to remove it, because there is such a thing as namespaces and function overloading. Often an "ambiguous" error message means there is a programming error in the parameters (such as mis-matched data types) and the compiler doesn't know which of several overloaded functions/methods to call.

Edited by Ancient Dragon because: n/a
Member Avatar for alkeshtech

I meant not in a particular language, in a grammar is it possible?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.