Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false:

there are non-deterministic unambiguous CFGs

What is the difference between ambiguity and determinism in grammars? What is an example of a grammar that is non-deterministic but unambiguous?

share|improve this question
4  
First, there is no such thing as a ''deterministic grammar''; however, a context-free language $L$ is deterministic if there exists a deterministic pushdown automaton that recognizes it. The even length palindromes over a binary alphabet form a non-deterministic language $\{ww^R\mid w\in\{a,b\}^\ast\}$ (where $w^R$ denotes the reversal of word $w$), which is unambiguous: there exists an unambiguous grammar for it, e.g. $S\to a\,S\,a\mid b\,S\,b\mid\varepsilon$. –  Sylvain May 24 at 14:27
    
@Sylvain just to make sure I understand you -- the Wikipedia article is wrong when it says that "In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars"? In that case, maybe I should just delete the OP? –  Matt Fenwick May 24 at 21:53
    
I think it's an improper use: languages or automata can be deterministic, not grammars. The correct statement would be "In formal grammar theory, the deterministic context-free languages (DCFL) are a proper subset of the context-free languages (CFL)". –  Sylvain May 25 at 8:33
    
I hadn't looked at the wikipedia page. They define deterministic CFGs as those for which there exists a DPDA with the same language. It's a dangerous definition, because it doesn't tell you how to construct this DPDA. A paragraph later they write nonsense: "DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator", altough it is undecidable, given a CFG, whether its language is a DCFL. –  Sylvain May 25 at 8:38
    
@Sylvain I know the ambiguity problem is undecidable but I thought it was decidable whether a given CFG is deterministic. There is a description of a "DK-test" in Sipser's introductory book (3rd edition) that a CFG passes iff it is deterministic. –  sjmc May 25 at 13:53

1 Answer 1

See this related Wikipedia link:

http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars

The efficiency of context-free grammar parsing is determined by the automaton that accepts it. Deterministic context-free grammars are accepted by deterministic pushdown automata and can be parsed in linear time, for example by the LR parser.[3] This is a subset of the context-free grammars which are accepted by the pushdown automaton and can be parsed in polynomial time, for example by the CYK algorithm. Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.[4] Nevertheless, removing grammar ambiguity may produce a deterministic context-free grammar and thus allow for more efficient parsing. Compiler generators such as YACC include features for resolving some kinds of ambiguity, such as by using the precedence and associativity constraints.

An ambiguous grammar may be defined as a grammar for which there exists more than one parse tree for some string belonging to the language it generates.

A deterministic grammar may be defined as a grammar for which there exists a deterministic machine model which is capable of recognizing the language it generates.

Assume Grammar 1 generates the same language as Grammar 2. Assume Grammar 1 is unambiguous and Grammar 2 is ambiguous. If a deterministic machine model is capable of recognizing the language generated by Grammar 1, then it is also capable of recognizing the language generated by Grammar 2 (by the assumption that they both generate the same language). Clearly, both are deterministic grammars and yet they differ on the question of ambiguity.

The definition of grammar ambiguity addresses the actual syntactical structure of the grammar and its relation to parsing, NOT whether an ambiguous grammar could be structured differently so as to generate the same language and yet remove ambiguity.

The definition of grammar determinism, however, is not related to the structure of a grammar but rather to the properties of the language it generates regarding recognition by an appropriate deterministic machine model.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.