The natural grammar for dangling "else" is ambiguous. But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement. Is this version also deterministic? Is this language deterministic?

Natural grammar (ambiguous): $$ S \rightarrow if~expr~S | if~expr~S~else~S | cmd $$

Unambiguous grammar: $$\begin{align*} S &\rightarrow U~|~F\\ U &\rightarrow if~expr~S~|~if~expr~F~else~U\\ F &\rightarrow if~expr~F~else~F~|~cmd \end{align*}$$

  • 1
    $\begingroup$ This is a good question, because not all unambiguous context-free languages are deterministic, and it may not be immediately clear if this is the case here. However, there's a simple test: A context-free language is deterministic if and only if it has a grammar which is $LR(k)$ for some $k$. So why not see if your favourite unambiguous grammar is $LR$? $\endgroup$ – Pseudonym Nov 19 '15 at 0:45
  • $\begingroup$ Where do these grammars come from? Note how the issue is easily fixed by using some kind of parenthesisation. $\endgroup$ – Raphael Nov 19 '15 at 11:46
  • 2
    $\begingroup$ @Raphael This grammars are in every other formal languages course, that tries to explain ambiguity. Parenthesisation would change generated language. Point is if this language is deterministic. $\endgroup$ – user978734 Nov 19 '15 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.