Compressing grammars by introducing ambiguity and left-recursion

Question

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).

Answer 1

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. Logical Methods in Computer Science 15(1), 2019.