LR(1) grammar that can not be transformed an LL(1) grammar

Question

Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.

Answer 1

$\def\NT#1{{\langle\it #1\rangle}}\def\T#1{{\tt#1}}$

The canonical example of an $LR(1)$ language which is not $LL(k)$ for any $k$ is $L_{\ge} = \{a^i b^j\mid i\ge j\}$. It's easy to show that the language is $LR(1)$ since it has an $LR(1)$ grammar (in fact, an $SLR(1)$ grammar): $$\begin{align}L_{\ge}&\to M\\L_{\ge}&\to a M\\M&\to\epsilon\\M&\to aMb\\ \end{align}$$ Intuitively, that works for bottom-up parsing because the parser doesn't have to chose between $L_{\ge}\to aM$ and $M\to a M b$ until it actually sees the $b$, or reaches the end of input. $LL$ parsers don't have that luxury; they must decide which production to predict based on the lookahead from the start of the production, which can't be done. (A more formal proof can be found in the Rosencrantz & Stearn paper cited at the top of this extremely useful summary.)

The dual to this problem, if you like, is the fact that no $LR$ parser exists for the language of palindromes, $P=\{\omega \omega^R\mid \omega\in\Sigma^*\}$. That language is context-free and unambiguous, but it cannot be made deterministic because the parser needs to decide to stop shifting and start reducing precisely at the middle of the input, but it can't know where the middle is until it reaches the end, which is far too late to make a decision.

Of course $P$ is not $LL(k)$ either because $\forall k: LL(k)\subset LR(1)$. But it's a dual in the sense that the problem lies in the impossibility of making a prediction based on the input up to the point of prediction. In $LL$, that point is the beginning of a production and in $LR$, it's at the end. But duality is not identity, and beginning and end, while duals, are still quite different. Simply put, more information is available at the end than the beginning (where beginning and end are relative to the direction of the parse.)

That might be evident from the observation that the language $L_\le = \{a^i b^j\mid i\ge j\}$, which is very similar to $L_\ge$, is $LL(1)$: $$\begin{align}L_\le&\to M B\\ M&\to\epsilon\\ M&\to a M b\\ B&\to\epsilon\\ B&\to b B\\ \end{align}$$ Another way to look at that is that $L_\ge$ is $LL$ if parsed right-to-left, while $L_\le$ is $LL$ if parsed left-to-right. Both languages are $LR$ regardless of the direction of the parse.

All of this is of practical importance because of the common need to write parsers for undelimited $\T{if}$ statements with optional $\T{else}$ clauses. (By "undelimited" we mean that there is no explicit punctuation at the end of the $\T{if}$ statement.) The obvious grammar for this construct would be: [Note 1]

$$\begin{align} \NT{statement}&\to\NT{if\;statement}\mid\; ...\\ \NT{if\;statement}&\to\T{if}\;\NT{expression}\;\T{then}\;\NT{statement}\\ \NT{if\;statement}&\to\T{if}\;\NT{expression}\;\T{then}\;\NT{statement}\;\T{else}\NT{statement}\\ \end{align}$$ But that grammar is ambiguous because it doesn't specify which $\T{if}$ should be matched by an $\T{else}$, if there's more than one open $\T{if}$. In other words, when the programmer writes:

    if x > 0 then if y > 0 then do_xy_positive else do_something_else

the above grammar would allow two interpretations: do_something_else executes if $x>0$ and $y<=0$, or do_something_else executes if $x<=0$. For this reason, the syntax is often described as the "dangling-else ambiguity", although it's not really ambiguous at all. The simplistic grammar is ambiguous, but almost every programming language uses the same rule: the $\T{else}$ matches the innermost (or first preceding) unmatched $\T{if}$, so the statement would always be interpreted in such a way that do_something_else executes if $x>0$ and $y<=0$ (and nothing at all happens if $x<=0$).

It's easy enough to write a grammar which unambiguously implements that syntax: $$\begin{align} \NT{statement}&\to\NT{open\;statement}\;\mid\;\NT{closed\;statement}\\ \NT{closed\;statement}&\to\NT{other\;statements}\\ \NT{closed\;statement}&\to\T{if}\;\NT{expression}\;\T{then}\;\NT{closed\;statement}\;\T{else}\;\NT{closed\;statement}\\ \NT{open\;statement}&\to\T{if}\;\NT{expression}\;\T{then}\;\NT{closed\;statement}\;\T{else}\;\NT{open\;statement}\\ \NT{open\;statement}&\to\T{if}\;\NT{expression}\;\T{then}\;\NT{statement}\\ \end{align}$$ That grammar is unambiguous, and moreover $LR(1)$. But it's not $LL(k)$ for any $k$, for a reason very similar to the language $L_\ge$. Ignoring the $\NT{statement}$ in the $\T{else}$ clause, it's essentially the same language: the number of $\T{if}\;\T{then}$ clauses must be greater than or equal to the number of $\T{else}$ clauses. Unsurprisingly, this means that there is no $LL(k)$ grammar for C-like $\T{if}$ statements. [Note 2]

In practice, it's not that common to see the $LR$ grammar snippet, either, because it's actually much easier for a software engineer to use a feature found in almost all parser generators: precedence declarations. Precedence declarations were designed to simplify the parsing of arithmetic expressions, allowing the use of an ambiguous grammar which doesn't specify how different operators are to be grouped, and then augment the grammar with a list of precedence levels, where each level groups more tightly than the previous ones. In this model, precedence levels are used to resolve shift/reduce conflicts: shift is chosen if the token to be shifted has higher precedence than the production to be reduced, and otherwise reduce is chosen. Although it's slightly perverse, that mechanism can be used to make $\T{else}$ "greedy". If $\T{else}$ has higher precedence than $\NT{if}\to\T{if}\;\NT{expression}\;\T{then}\;\NT{statement}$, then the $\T{else}$ will always be shifted, causing it to be included in the innermost open $\NT{if\;statement}$.

---

Notes

1. C, of course, doesn't use $\T{then}$ to separate the condition expression from the target statement. It prefers to use punctuation; the condition is enclosed in parentheses. But that has no bearing on the dangling-else issue.

2. This doesn't have much impact on recursive descent parsers, but it might affect a table-driven top-down parser. The recursive descent parser only needs to ignore the possible conflict; when $\T{else}$ is encountered by the if_statement parse function, it greedily accepts. Parser generators like Antlr or PEG parsers, which use ordered choice, also have no problem with the greedy $\T{else}$. But it remains the case that the language is not $LL(k)$ for any $k$.

Answer 2

Thanks to rici and D.W. for pointing out a very practical example of a LR(1) grammar that can not be expressed as an LL(1) grammar.

They've provided the example language $\{a^ib^j\mid i\ge j\}$, which shows why "if then optional-else" is not in $LL(k)$ for any $k$. The example language has at the same or more number of $a$s than $b$s, just as you have the same or more number of ifs than elses, when else is optional in a if-then-else statement.

"if then-optional else" has a unambiguous solution in LR(1) where you simply create a separate statement non-terminal which does not contain the if-statement.

E.g.

program
    : statements
statements
    : statement
    | statements statement
statement
    : if_statement
    | statement_no_if
statement_no_if // <-- contains all the statements except for if_statement
    : ...
if_statement
    : "if" expression "then" statement
    | "if" expression "then" statement_no_if "else" statement
expresion
    : ...

Since statement_no_if contains any statement except the if_statement, the else ends up getting associated to the closest if-statement, make it unambiguous.

So $\{a^ib^j\mid i\ge j\}$ can be expressed in $LR(1)$, because of that well known pattern above for handling the dangling else problem in $LR(1)$ grammars.

There is also a simple $LR(1)$ grammar provided by rici for $\{a^ib^j\mid i\ge j\}$ of:

$S\to M \mid a S; M\to\epsilon\mid a M b$

which is $LR(1)$ and definitely can not be written as $LL(1)$