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


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.

  • $\begingroup$ 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)? $\endgroup$ – Martin Berger Mar 14 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Hermann Gruber Mar 14 at 23:39
  • $\begingroup$ One could study this problem for even simpler grammars, e.g. regular expressions. $\endgroup$ – Martin Berger Mar 15 at 8:46
  • $\begingroup$ 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. $\endgroup$ – Martin Berger Mar 15 at 9:45

Your Answer

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

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