Question 14.2.4: Assume that an LR(0)-grammar is given. Prove that each strin......
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
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.
Related Answered Questions
Question: 14.4.7
Verified Answer:
Assume that a grammar is fixed. The string S of te...
Question: 14.4.6
Verified Answer:
As before, at each stage of the LR-process we can ...
Question: 14.4.5
Verified Answer:
Assume that a grammar is fixed. Let S be an arbitr...
Question: 14.4.4
Verified Answer:
(1) If a string S is coherent with a situation [K ...
Question: 14.4.3
Verified Answer:
The string S (of terminals and nonterminals) is co...
Question: 14.4.2
Verified Answer:
Now a situation is defined as a pair
[situation in...
Question: 14.3.3
Verified Answer:
Yes; both conflicts that prevent it from being a L...
Question: 14.4.1
Verified Answer:
Nonterminals are symbols (LeftK t) for any nonterm...
Question: 14.2.3
Verified Answer:
Yes, see the corresponding tables (a) and (b) (no ...
Question: 14.3.2
Verified Answer:
We repeat the argument used for LR(0)-grammars. Th...