# How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules:

Consider a robot arm that accepts two commands: $$\triangledown$$ puts an apple in the bag and $$\triangle$$ takes an apple out of the bag. Assume the robot arm starts with an empty bag. A valid command sequence for the robot arm should have no prefix that contains more $$\triangle$$ commands than $$\triangledown$$ commands. As examples, $$\triangledown\triangledown\triangle\triangle$$ and $$\triangledown\triangle\triangledown$$ are valid command sequences, but $$\triangledown\triangle\triangle\triangledown$$ and $$\triangledown\triangle\triangledown\triangle\triangle$$ are not.

My first attempt considered the net number of motions of the robot arm. ZeroMotion is a sequence of steps that produce an equal number of $$\triangle$$ and $$\triangledown$$ steps, while DownMotion represents a sequence with more $$\triangledown$$ than $$\triangle$$. I'm almost certain that it's ambiguous.

Goal ----------> DownMotion $$\triangledown$$
ZeroMotion ----> ZeroMotion DownMotion $$\triangle$$ | DownMotion ZeroMotion $$\triangle$$ | $$\triangledown$$ $$\triangle$$
DownMotion ----> $$\triangledown$$ ZeroMotion | $$\triangledown$$ DownMotion
where {$$\triangledown$$, $$\triangle$$} $$\epsilon$$ T, and {Goal, ZeroMotion, DownMotion} $$\epsilon$$ NT

I started anew, and came up with the new grammar below, which is closer, but also incorrect as it does not "keep track" of the number of surplus $$\triangle$$'s:

Goal ----------> Goal DownMotion | DownMotion
ZeroMotion ----> DownMotion $$\triangle$$ | $$\epsilon$$
DownMotion ----> ZeroMotion DownMotion ZeroMotion | $$\triangledown$$
where {$$\triangle$$, $$\triangledown$$} $$\epsilon$$ T, and {Goal, ZeroMotion, DownMotion} $$\epsilon$$ NT

Can someone provide me with the correct answer?

*** This problem is taken from Engineering a Compiler (Keith Cooper, Linda Torczon), 2nd edition, Chapter 3, exercise 11. ***

** Yes, I posted a question about the same problem last night. But errors in my description made my problem unsolvable.

• Why didn't you just edit the previous question? Someone did try to answer it...
– rici
Feb 5 at 22:26
• @rici I'll do that in the future. Since my edits were fairly extensive, I figured that no one would bother answering my original Q. Feb 5 at 22:31
• @rici fixed. Please excuse my beginner mistakes Feb 5 at 23:01

An earlier exercise in the same textbook asks you (in effect) to create a grammar for the balanced parenthesis language (disguised as a question about elevator motions) and then prove that your grammar is LL(1). The answer to that exercise is an important prerequisite for this one, so if you haven't done it yet, go back and try it now before you read this answer.

A language of balanced parentheses is called a Dyck language (named for the German mathematician Walther von Dyck, 1856-1934), and Dyck languages (which include the elevator language) are an important abstraction in almost every useful context-free grammar, since nesting sublanguages inside balanced delimiters is what context-free grammars excel at. (For a less informal description of why Dyck languages are fundamental, see the Chomsky-Schützenberger representation theorem.)

An obvious context-free grammar for it is: \begin{align}S\to\;&\varepsilon\\ |\;&(\;S\;)\\ |\;&S\;S \end{align} But that grammar is ambigous (as is any CFG with a production of the form $$N\to N...N$$). Fortunately, it's easy to do better: \begin{align}S\to\;&\varepsilon\\ |\;&(\;S\;)\;S \end{align} That's the answer to the earlier question, leaving out the proof of unambiguity of the grammar. (Or, equivalently in this case, the proof that it's LL(1).)

Now, let's go to the exercise you are currently working on. An important insight is that the robotic apple language is nothing other than the language of prefixes of a Dyck language. In other words, you can turn it into a perfect Dyck language simply by emptying the bag at the end. (Or returning the elevator to the ground floor.) There are other ways to insert closing parentheses (or $$\triangle$$s), but adding them all at the end is the canonical solution. That corresponds to the idea that when we parse β the prefix of a Dyck language, we will match each close parenthesis with the most recent as-yet-unmatched open parenthesis, which is canonical in the sense that it is the way that the parentheses would be matched in any Dyck expression for which β is a prefix.

That might make you think about the classic "dangling-else" parsing problem, which is about how else keywords are matched with if keywords in a language in which else is optional and there is no end-marker for an if statement. (For example, C, although the issue goes back much further in the history of programming languages.)

(This particular ambiguity, along with the resolution shown below, is described in your textbook, in Chapter 3, so you should already be familiar with it. But I typed the following paragraph before checking the textbook.)

Now, there is a classic solution to the dangling-else problem, which has precisely to do with enforcing the matching rule described above: each else is matched with the most recent as-yet-unmatched if. The way this is enforced in a grammar is to insist that what comes between the if and the else in an if-statement cannot itself contain an unmatched if. If you have if condition then if condition ... else, the else can only match the first if in the case that the ... includes an else so that the second if is matched. Otherwise, the else would have to match the second if because that one is more recent, and has not yet been matched.

Grammatically, that is written (in part): \begin{align} \textit{Statement}\to\;&\textit{Matched-Statement}\\ |\;&\textit{Unmatched-Statement}\\ \textit{Matched-Statement}\to\;&\textbf{if}\;\textit{Expression}\;\textbf{then}\;\textit{Matched-Stmt}\;\textbf{else}\;\textit{Matched-Statement}\\ |\;&\textit{Other-Statement}\\ \textit{Unmatched-Statement}\to\;&\textbf{if}\;\textit{Expression}\;\textbf{then}\;\textit{Matched-Stmt}\;\textbf{else}\;\textit{Unmatched-Statement}\\ |\;&\textbf{if}\;\textit{Expression}\;\textbf{then}\;\textit{Statement}\\ \end{align}

The Dyck prefix language is not exactly the same. But it is similar enough that the solution should be evident from the above. So I suggest, again, that you try it yourself. But here is the slightly obscured solution:

\begin{align}S\to\;&B \mid I\\B\to\;&\varepsilon\\|\;&\bigtriangledown\;B\;\bigtriangleup\;B\\I\to\;&\bigtriangledown\;S\end{align} (B = Balanced; I = Imbalanced (i.e. proper prefix)

• thank you!!! You are a gentleman and a scholar!!! I got a lesson in history, computer science, and formal language theory. And you tied it all in with an earlier example in the chapter. Feb 6 at 1:42