<p>Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here: </p>

<p>Erik Meineche Schmidt, Thomas G. Szymanski:
Succinctness of Descriptions of Unambiguous Context-Free Languages. SIAM J. Comput. 6(3): 547-553 (1977) </p>

<p><strong>EDIT (16/3/2019):</strong> answering to the comment, by introducing ambiguity, the resulting grammar will be nondeterministic, i.e. a general CFG. Imposing further restrictions on the given grammar, e.g. that the given CFG is LR(1), is of course not a suitable way to tame the tradeoff. Historically the first nonrecursive tradeoff to be shown was between finite automata and CFGs (Albert R. Meyer and Michael J. Fischer: Economy of Description by Automata, Grammars, and Formal Systems. SWAT 1971: 188-191). Completing the picture, there is also a nonrecursive tradeoff when moving from unambiguous CFGs to LR(1) grammars: Leslie G. Valiant:
A Note on the Succinctness of Descriptions of Deterministic Languages. Information and Control 32(2): 139-145 (1976)</p>

<p><strong>EDIT (24/03/2019):</strong> answering to the other comment, if we restrict our attention to unambiguous finite automata, the gain in succinctness by introducing ambiguity will be at most exponential. In fact, a recent paper discusses a novel NFA minimization heuristics which merges equivalent states. A preprocessing step in the algorithm introduces additional transitions to the given automaton, which do not alter the accepted language ("saturation step"). The saturation step makes the automaton bigger, at least with respect to the number of transitions. And this step may introduce ambiguity. But the algorithm then contains a "quotienting step", which can allow for merging more states that are equivalent than without the saturation step. (The heuristics works for automata over infinite words and those over finite words.)</p>

<p>Clemente, Lorenzo and Mayr, Richard: <a href="https://lmcs.episciences.org/5189" rel="nofollow noreferrer">Efficient reduction of nondeterministic automata with application to language inclusion testing</a>. Logical Methods in Computer Science 15(1), 2019.</p>

CC BY-SA 4.0
2019-03-14T22:16:33.967Z
Thanks. Can this result be inverted, by going from unambiguous CFGs to ambigous CFGs that might be left recursive? What if the unambiguous grammar is 'nice', e.g. LL(k) or LR(k)?
Martin Berger
CC BY-SA 4.0
2019-03-14T23:39:27.557Z
You can read the nonrecursive tradeoff result also in the other direction: the gain in succinctness offered by ambiguous cfgs is not bounded by a recursive function, ie there are large minimal unambiguous cfgs for which can be compressed very very much by describing them as a cfg. I'll have a look regarding nice grammars, there are similar results I think.
Hermann Gruber
CC BY-SA 4.0
2019-03-15T08:46:17.057Z
One could study this problem for even simpler grammars, e.g. regular expressions.
Martin Berger
CC BY-SA 4.0
2019-03-15T09:45:48.563Z
As an aside, what I'm really interested in is the blowup/reduction we get with the kinds of grammars we use in programming languages. They are probably not super-recursive.
Martin Berger
CC BY-SA 4.0
2019-03-14T19:40:23.960Z
2019-03-24T20:54:39.560Z
2019-03-24T20:54:39.560Z
Hermann Gruber
<p>This is a reference request. What is known about the following questions?</p>

<p><strong>Problem:</strong> Given a grammar <span class="math-container">$G$</span> (for example context-free) with language <span class="math-container">$L$</span> we can introduce a
new grammar <span class="math-container">$G'$</span> which also accepts <span class="math-container">$L$</span>, but may <em>introduce</em> left
recursion and ambiguity. </p>

<ul>
<li><p>Which algorithms have been investigated that produce such <span class="math-container">$G'$</span> from <span class="math-container">$G$</span>?</p></li>
<li><p>By how    much can <span class="math-container">$G'$</span> be more succinct than
<span class="math-container">$G$</span> (for any reasonable notion of succinctness)?</p></li>
</ul>

<p><strong>Context.</strong> There has been a great deal of work on making grammars
parsable in practise. This involved removing ambiguity and (relevant
only for some form of parsing) left-recursion. Many notions of normal
form have been invented form this purpose, with parsers that can
handle these NFs. However, making grammars digestible by parsers also
makes them  less readable by humans. I'm    interested in going the other
way: How to make machine-parsable grammars more readable by giving up
on machine parsability (or at least making parsing harder).</p>

<reference-request><context-free><grammars><parsing><ambiguity>
Compressing grammars by introducing ambiguity and left-recursion
Martin Berger
# Compressing grammars by introducing ambiguity and left-recursion

(Asked by: username_0 on 2019-03-14)

This is a reference request. What is known about the following questions?

**Problem:** Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also accepts $L$, but may *introduce* left
recursion and ambiguity.

* Which algorithms have been investigated that produce such $G'$ from $G$?
* By how much can $G'$ be more succinct than
  $G$ (for any reasonable notion of succinctness)?

**Context.** There has been a great deal of work on making grammars
parsable in practise. This involved removing ambiguity and (relevant
only for some form of parsing) left-recursion. Many notions of normal
form have been invented form this purpose, with parsers that can
handle these NFs. However, making grammars digestible by parsers also
makes them less readable by humans. I'm interested in going the other
way: How to make machine-parsable grammars more readable by giving up
on machine parsability (or at least making parsing harder).

**Tags:** reference-request, context-free, grammars, parsing, ambiguity


---

## 1 answers

### Answer by username_1 on 2019-03-14. Score: 1 | Accepted answer

Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here:

Erik Meineche Schmidt, Thomas G. Szymanski:
Succinctness of Descriptions of Unambiguous Context-Free Languages. SIAM J. Comput. 6(3): 547-553 (1977)

**EDIT (16/3/2019):** answering to the comment, by introducing ambiguity, the resulting grammar will be nondeterministic, i.e. a general CFG. Imposing further restrictions on the given grammar, e.g. that the given CFG is LR(1), is of course not a suitable way to tame the tradeoff. Historically the first nonrecursive tradeoff to be shown was between finite automata and CFGs (Albert R. Meyer and Michael J. Fischer: Economy of Description by Automata, Grammars, and Formal Systems. SWAT 1971: 188-191). Completing the picture, there is also a nonrecursive tradeoff when moving from unambiguous CFGs to LR(1) grammars: Leslie G. Valiant:
A Note on the Succinctness of Descriptions of Deterministic Languages. Information and Control 32(2): 139-145 (1976)

**EDIT (24/03/2019):** answering to the other comment, if we restrict our attention to unambiguous finite automata, the gain in succinctness by introducing ambiguity will be at most exponential. In fact, a recent paper discusses a novel NFA minimization heuristics which merges equivalent states. A preprocessing step in the algorithm introduces additional transitions to the given automaton, which do not alter the accepted language ("saturation step"). The saturation step makes the automaton bigger, at least with respect to the number of transitions. And this step may introduce ambiguity. But the algorithm then contains a "quotienting step", which can allow for merging more states that are equivalent than without the saturation step. (The heuristics works for automata over infinite words and those over finite words.)

Clemente, Lorenzo and Mayr, Richard: [Efficient reduction of nondeterministic automata with application to language inclusion testing](https://lmcs.episciences.org/5189). Logical Methods in Computer Science 15(1), 2019.

> **Comments:**
> **username_0**: Thanks. Can this result be inverted, by going from unambiguous CFGs to ambigous CFGs that might be left recursive? What if the unambiguous grammar is 'nice', e.g. LL(k) or LR(k)?  
> **username_1**: You can read the nonrecursive tradeoff result also in the other direction: the gain in succinctness offered by ambiguous cfgs is not bounded by a recursive function, ie there are large minimal unambiguous cfgs for which can be compressed very very much by describing them as a cfg. I'll have a look regarding nice grammars, there are similar results I think.  
> **username_0**: One could study this problem for even simpler grammars, e.g. regular expressions.  
> **username_0**: As an aside, what I'm really interested in is the blowup/reduction we get with the kinds of grammars we use in programming languages. They are probably not super-recursive.  

---

