Show how to compute inductively the set State(S) of all situations coherent with a given string S.

Step-by-Step

Learn more on how do we answer questions.

(1) If a string S is coherent with a situation [K → U_V, t] and the first character in V is J, that is, V = JW, then SJ is coherent with the situation [K → UJ_W, t].

This rule determines completely which situations that do not start with underscore are coherent with SJ. It remains to find out for which nonterminals K and terminals t the string SJ belongs to Left(K, t). This is done according to the following two rules:

(2) If the situation [L → U_V, g] is coherent with SJ (according to (1)) and V starts with a nonterminal K, then SJ belongs to Left(K, s) for any terminal s that may appear as a first symbol in a string derivable from V \ K (the string V without the first symbol K), as well as for s = t, if the empty string is derivable from V \ K.

(3) If SJ is in Left(L, t) for some L and g, and L → V is a production rule, and V starts with a nonterminal K, then SJ belongs to Left(K, s) for any nonterminal s that may appear as a first symbol in a string derivable from V \ K, as well as for s = t, if the empty string is derivable from V \ K.

Question: 14.2.4

Assume that an arbitrary input string is given. We...

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.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...