Talk:Ambiguous grammar

Wanted: linguistics content

Would like to see the linguistics side of things as well. - MGM 08:43, May 11, 2004 (UTC)

Wanted: inherently ambiguous example

Perhaps an example in the Inherently Ambiguous Grammars section? The union of the two languages is confusing. —The preceding unsigned comment was added by 24.36.73.177 (talk • contribs) 02:52, 28 May 2007.

Confusing and, what's worse, mistaken; the languages given by the regular expressions ab* (S → aT, T → bT, T → ε) and a*b (S → Tb, T → aT, T → ε) have one string in common: viz, "ab", but their union is the language given by the unambiguous regular expression a|abbb*|a*b (S → a, S → abbT, S → Ub, T → bT, T → ε, U → aU, U → ε). —Ruakh_TALK 18:03, 28 May 2007 (UTC)

Microhunt

Moved from User talk:Svick#Microhunt.

hello Svick, I have read the page Ambiguous_grammar(computer science). Your contribution is worth appreciating! Since this page may be viewed by many computer scientists, I found it necessary to bring to your notice that one of the concept is logically false. I thought that it would be good to consult before committing any changes directly on the page or rather you make the changes by yourself if you accept my proposal, which as follows:-

At the beginning in 2nd paragraph its mentioned - " Some programming languages have ambiguous grammars; in this case, semantic information is needed to select the intended parse tree of an ambiguous construct. For example, in C the following:

x * y ; .......... " The definition of the ambiguous grammar is that: If ONE string in the language can be generated by grammar in TWO WAYS then it is ambiguous. But I think that the grammar(to generate x*y) is not ambiguous because the string x*y can be generated only in ONE way. It is problem of language designers that they have kept ONE string with TWO MEANINGS. So grammar has nothing to do with the semantics of the language. Resolving the meaning of language is not the part of the grammar. So the statement "Some programming languages have ambiguous grammars" may not be false, but the example provided is definitely incorrect(as far as my logic and knowledge is concerned).

---

IMPORTANT MESSAGE

I hope you will not take my proposal in wrong way. Please reply with necessary details. People have general tendency of behaving like a lawyer and defending their statement if someone attacks on their statement! So I hope that you keep yourself neutral and hunt for the truth! May God bless you!!

" GOD IS ONE !" —Preceding unsigned comment added by Microhunt (talk • contribs) 07:01, 13 July 2010 (UTC)

First, I moved the discussion here, because I think it belongs here.

Also, I have made only one minor edit to this article, so I think your appreciation is misplaced.

Finally, about ambiguous grammars: I think the example is correct. Consider this context-free grammar for the subset of C the example uses:

expression → declaration

expression → identifier

expression → expression * expression

declaration → identifier decl_name

decl_name → identifier

decl_name → * identifier

In this grammar, “x * y” can be derived as

expression → expression * expression → x * y

or

expression → declaration → identifier decl_name → x * identifier → x * y

This means the grammar is actually ambiguous.

Svick (talk) 20:19, 14 July 2010 (UTC)

---

''''Microhunt'''' Thanks svick I was not aware that Such ambiguous grammar is used in C language, But then when we can write an unambiguous grammar for expressions evaluation(example given below),why such ambiguous grammar is used? Example: G=(V,T,P,S) where V = {E,T,F}

     T = {+,-,*,/,(,),id}
     P = {
            E -> E + T | E - T | T
            T -> T*F | T/F | F
            F -> ( id ) | id
         }
     S = E
        

(Please read this-->please do not misunderstand me, when I said that "Your contribution is worth appreciating!", with this statement what I meant was; All your contribution are really worth appreciating! You took it wrong way! May be the statement I typed was ambiguous!!!!! wherein the reader may get two different point of views.. My intention was not to suppress you but to get something to know what is the truth.. You are the first person in the wiki with whom I have initiated my talk. I apologize if I have hurt you unintentionally.)

One more thing I would like to share with you that some of the authors of TCS say that the grammar is ambiguous if its leftmost derivation tree and rightmost derivation tree differs. I am 100% sure it is wrong. How shall I convince them.. can you suggest any way to do so.. —Preceding unsigned comment added by Microhunt (talk • contribs) 09:05, 21 July 2010 (UTC)

The ambiguity of the actual C grammar stems from the fact that the character * is used for two different purposes – as a multiplication operator and as pointer indicator. Your grammar is able to express arithmetic expressions, but not variable declarations (like int i). The authors of C could have used different character for pointers (e.g. Pascal uses ^), but I suppose there was no need to do so – both programmers and compilers can handle ambiguous grammars just fine.

About the derivation trees: You have to be careful what exactly do they say. If it's “if the leftmost derivation tree and the rightmost derivation tree differ, then the grammar is ambiguous” (it's an implication), then I think it's correct: if there are two different derivation trees, then the grammar is ambiguous. If they mean “grammar is ambiguous if and only if its leftmost derivation tree and rightmost derivation tree differ”, then it's wrong. See for example Context-free grammar#Derivations and syntax trees. The grammar given there is ambiguous, but there is a leftmost derivation tree that is the same as a rightmost derivation tree.

Oh, and you certainly didn't hurt me. Svick (talk) 12:44, 21 July 2010 (UTC)

Ambiguity

If, according to this article, it's impossible to algorithmically determine whether a grammar is ambiguous or not, how come YACC can detect these ambiguities? SamSim 13:52, 8 February 2011 (UTC)

I don't have any experience with YACC, but my guess is that it can detect some ambiguities, but not all of them. Svick (talk) 04:15, 13 February 2011 (UTC)

Yacc checks to ensure that its input grammar is LALR(1); this question is decidable, and all LALR(1) grammars are unambiguous. But not all unambiguous grammars are LALR(1), so the algorithms used by yacc and other LALR(1) parser generators are not algorithms for determining whether an arbitrary grammar is ambiguous. C.M.Sperberg-McQueen (talk) 00:29, 21 August 2018 (UTC)