Assume that an LR(0)-grammar is given. Prove that each string has at most one rightmost derivation. Give an algorithm that checks whether the input string is derivable.

Step-by-Step

Learn more on how do we answer questions.

Assume that an arbitrary input string is given. We construct an LR process on that string stepwise. Assume that the current stack of the LR-process is S. We have to decide whether a shift or reduce action is needed (and which rule should be used in the reduction case). The definition of LR(0) grammar guarantees that only one action is possible, and all the information needed to make the decision is contained in State(S). Therefore, we can find the (only possible) next step of the LR-process.

Question: 14.4.7

Assume that a grammar is fixed. The string S of te...

Question: 14.4.6

As before, at each stage of the LR-process we can ...

Question: 14.4.5

Assume that a grammar is fixed. Let S be an arbitr...

Question: 14.4.4

(1) If a string S is coherent with a situation [K ...

Question: 14.4.3

The string S (of terminals and nonterminals) is co...

Question: 14.4.2

Now a situation is defined as a pair
[situation in...

Question: 14.3.3

Yes; both conflicts that prevent it from being a L...

Question: 14.4.1

Nonterminals are symbols (LeftK t) for any nonterm...

Question: 14.2.3

Yes, see the corresponding tables (a) and (b) (no ...

Question: 14.3.2

We repeat the argument used for LR(0)-grammars. Th...