12
$\begingroup$

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which are productions annotated with a position and a lookahead character.

It's known that given a state in an LR(1) automaton, the configurating set formed by dropping the lookahead tokens from each LR(1) item yields a configurating set corresponding to some state in the LR(0) automaton. In that sense, the main difference between an LR(1) automaton and an LR(0) automaton is that the LR(1) automaton has more copies of the states in the LR(0) automaton, each of which is annotated with lookahead information. For this reason, LR(1) automata for a given CFG are typically larger than the corresponding LR(0) parser for that CFG.

My question is how much larger the LR(1) automaton can be. If there are $n$ distinct terminal symbols in the alphabet of the grammar, then in principle we might need to replicate each state in the LR(0) automaton at least once per subset of those $n$ distinct terminal symbols, potentially leading to an LR(1) automaton that's $2^n$ times larger than the original LR(0) automaton. Given that each individual item in the LR(0) automaton consists of a set of different LR(0) items, we may get an even larger blowup.

That said, I can't seem to find a way to construct a family of grammars for which the LR(1) automaton is significantly larger than the corresponding LR(0) automaton. Everything I've tried has led to a modest increase in size (usually around 2-4x), but I can't seem to find a pattern that leads to a large blowup.

Are there known families of context-free grammars whose LR(1) automata are exponentially larger than the corresponding LR(0) automata? Or is it known that in the worst case, you can't actually get an exponential blowup?

Thanks!

Improve this question
$\endgroup$
5
  • $\begingroup$ problems such as these are sometimes amenable to empirical testing. what would you think of individual instances generated randomly that (are selected to) exhibit blowup? there is a pattern in these types of questions that "random-looking" constructions exhibit the most "complexity"... $\endgroup$
    – vzn
    Jul 8, 2015 at 3:26
  • 2
    $\begingroup$ Worst-case instances are usually hard to find by random sampling, at least if the average case is significantly better. $\endgroup$
    – Raphael ♦
    Jul 8, 2015 at 11:39
  • $\begingroup$ ps it would be helpful if you incl examples of the 2x-4x blowup cases somewhere, not nec in the post... $\endgroup$
    – vzn
    Jul 9, 2015 at 0:40
  • $\begingroup$ idea/ lead: LR parsing permutations (cstheory.se) $\endgroup$
    – vzn
    Jul 9, 2015 at 0:46
  • $\begingroup$ LALR(1) is commonly presented as a way to get sufficiently near to LR(1) power to be useful with many fewer states (to use the words of the Dragon book). I wonder if a mere factor of 2 to 4 would have been enough to have dismissed LR(1) as prohibitive until the invention of LALR(1). If I think about it when they are accessible, I'll have a look in Aho&Ullman The theory of parsing, translation, and compiling and in Grune Parsing Techniques if they have something about the numbers. $\endgroup$
    – AProgrammer
    Dec 7, 2015 at 21:21

2 Answers 2

Reset to default
4
$\begingroup$

The grammar

$$\begin{array}{l} S \rightarrow T_0 \\ T_n \rightarrow a \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \; t_n \\ T_N \rightarrow t_N \end{array} $$

has the LR(0) state $$T_N \rightarrow t_N \dot \\$$ expanded to $2^N$ variants in the LR(1) automata as all the partitions of $\{t_0 \dots t_{N-1}\}$ are possible look-head which appear in different contexts. The number of states in the LR(0) automaton on the other hand is linear in term of $N$. Thus an expansion factor of the order of $2^N/N$ is possible.

Edit: I'll have to check later when I've more time, I think adding $T_N \rightarrow T_0$ would give the exponential factor on nearly all the LR(0) states. That result in a shift-reduce conflict.

Improve this answer
$\endgroup$
0
$\begingroup$

Such lower bounds are sometimes tricky to construct and may evoke deeper CS theory (eg in cases, complexity class separations). This paper seems to give a theoretical construction/ lower bounds you seek eg in Theorem 5 which puts a lower bound on total symbols and therefore also states. The references also include other similar constructions/ lower bounds.

Theorem 5. Let $f(n,k) = 2^{\frac{1}{4}(n - k)} / n^2$. For any LR(k)-grammar with $k = 0,1;...,n−1$ generating $L_n$; where $n \geq 3$; the number of nonterminal symbols must be at least $f(n,k)$ or there exists a nonterminal symbol A such that the number of different productions with A on the left hand side must be at least $f(n,k)$.

On the size of parsers and LR(k)-grammars / Leunga, Wotschkeb

Improve this answer
$\endgroup$
3
  • $\begingroup$ This doesn't tell us how much larger the LR(1) automaton is than the LR(0) automaton. It gives a $2^{(n-1)/4}/n^2$ lower bound on the size of the LR(1) automaton, and a $2^{n/4}/n^2$ lower bound on the size of the LR(0) automaton, but what we want is a lower bound on the ratio of the size of the LR(1) automaton divided by the LR(0) automaton. This result implies nothing whatsoever about that ratio. To learn something about the ratio, we'd need an upper bound on the size of the LR(0) automaton for that language. So this answer doesn't answer the question that was asked. $\endgroup$
    – D.W. ♦
    Jul 9, 2015 at 17:44
  • $\begingroup$ Not to mention that the gap between the two lower bounds is only a factor of $1.1892$, and the original post says that the author already knows how to achieve a ratio of 2-4x but wants to know whether a really large blowup is possible. $\endgroup$
    – D.W. ♦
    Jul 9, 2015 at 17:46
  • $\begingroup$ DW think your objection is both legitimate & approaches hairsplitting. thx so much for the clarification/ detail. its a relevant/ nearly direct scientific answer to/ systematic study of his question which is essentially about worst case language construction(s)/ blowup in LR(n). it is possible these are (nearly?) "best known results" in the area. a legitimate answer to the question might be negative, aka NO, there are not better results known than either found by the questioner (he hasnt yet actually exhibited any) or in the literature. eagerly awaiting any more definitive answers myself! $\endgroup$
    – vzn
    Jul 9, 2015 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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