We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is that maybe starting from a simple grammar, which is easy to prove that is not ambigous, then adding some rules for which the new grammar is also not ambiugous, of course there must be some theorems which say what kind of rules can be added. If my guessing is correct I would like to know that theorems.
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by definition, unambiguous; the corresponding language classes are (strict) subsets of DCFL.
You would realize a grammar is ambiguous (or otherwise not in the grammar class at hand) when the algorithm constructing a parser from it fails. Speaking in computability terms, membership for these grammar classes is decidable.
-
$\begingroup$ if we have an algorithm that fails to construct a parser then we have a method to decide if the grammar is ambigous or not and in this case the problem would not be undcidible. Maybe the algorithm is not a "if and only if" and then when writing a grammar are maded the attempts until the algorithm not fails. $\endgroup$– asvCommented Dec 27, 2018 at 15:24
-
1$\begingroup$ @asv No. It would, for instance, decide whether a grammar is LL(1) or not (which is famously decidable even without constructing the full parser). An unambiguous but non-LL(1) grammar would be rejected. Hence there is no contradiction. $\endgroup$– RaphaelCommented Dec 27, 2018 at 18:15