9
LR(k) and LL(1) Grammars
 The most widely used topdown parsers are constructed with LL(1) grammars. The most powerful bottomup parsers are constructed with LR(k) grammars. The language defined by LR(k) grammars is DCFL.
In this chapter, we introduce a restricted type of CFG called LR(0) Grammar. We discuss the question what are LL(1), LR(0) and LR(1) grammars. Given a grammar, we discuss how to test whether it is LL(1) or LR(0) or LR(1).
9.1 LL(1) Grammar
A grammar that is suitable for LL(1) parser construction is called LL(1) grammar.
Given a grammar, to check whether it is LL(1) or not, we use two functions called First( ) and Follow( ).
Let us now understand the functions First( ) and Follow( ).
The function First (x) (where x is a grammar symbol) gives set of terminals that may be the first symbol in any string derived from x.
The function First (x) is evaluated as follows.
 If x is a terminal, then First (x) is x itself.
Ex: First(+) = {+}, First(id) = {id}.
 If x is a nonterminal
 & is defined with εrules, that is, X → ε, then First(X) = {ε}.
 & is defined with nonεrules, that is, X → A_{1}A_{2}A_{3} then
First(x) = First(A_{1}A_{2}A_{3}) = First(A_{1}) if A_{1} ε= First(A_{1}) − {ε} ∪ First(A_{2} A_{3}) if A_{1} ε
Find First(·) of each nonterminal in the grammar given:
Solution: First(S) = First(AB) = First(A)
First(A) is {a, ε}
Since there is ε, add a, then continue with First(B).
First(B) is{b, ε}.
Since there is ε, add b, then ε.
Hence, First(S) = {a, b, ε}.
Find First(·) of each nonterminal in the grammar given:
Solution: First(S) = First(ABCDE) = First(A)
First(A) is {a, ε}
Since there is ε, add a, then continue with First(B).
First(B) is{b, ε}.
Since there is ε, add b, then continue with First(C).
First(C) is{c, ε}.
Since there is ε, add c, then continue with First(D).
First(D) is{d, ε}.
Since there is ε, add d, then continue with First(E).
First(E) is{e} i.e terminal only hence evaluation stops here.
Hence, First(S) = {a, b, c, d, e}.
When A is a nonterminal, Follow(A) gives the set of terminals that may follow immediately to the right of A while deriving any string from the grammar.
Follow(A) is evaluated by using following rules:
 If A is a start symbol, then Follow(A) is {$}.
 If S → αAβ is in G, then Follow(A) = First(β) – {ε}
 If S → αA or S → αAβ where β ε, then Follow(A) = Follow(S).
Find Follow(·) of each nonterminal in the grammar
Solution: Follow(S) = {$} as S is start symbol.
Follow (A) = First(Bb)
First(Bb) is First(B) = {d, ε}
Since there is ε, add d, then continue with First(b).
Hence, First(A) = {d, b}.
Follow (B) = First(b) = {b}
Find Follow(·) of each nonterminal in the grammar
Solution: Follow(S) = {$} as S is start symbol.
Follow (A) = First(BCDE) = First(B)
First(B) is {b, ε}.
Since there is ε, add b, then continue with First(C).
First(C) is {c, ε}.
Since there is ε, add c, then continue with First(D).
First(D) is {d, ε}.
Since there is ε, add d, then continue with First(E).
First(E) is {e, ε}.
Since there is ε, add Follow(S), that is, $
Hence, Follow(A) = {b, c, d, e, $}.
Similarly, Follow(B) = {c, d, e, $}
Follow(C) = {d, e, $}
Follow(D) = {e, $}
Follow(E) = {$}
9.2 Rules for Verifying Whether the Given Grammar Is LL(1) or Not
 A grammar without null rules is LL(1) provided for each production of the form A → β_{1}  β_{2}  β_{3}, First(β_{1}), First(β_{2}), First(β_{3}),. must be mutually disjoint, that is,
 First(β_{i}) ∩ First(β_{j}) = Ø
 A grammar with null rules is LL(1) provided for each production of the form
 A → β  ε, First(β) and Follow(A) must be mutually disjoint, that is,
 First(β) ∩ Follow(A) = Ø
 A → β  ε, First(β) and Follow(A) must be mutually disjoint, that is,
 An ambiguous grammar cannot be LL(1).
 Left recursive grammar is not LL(1).
Given any grammar, by using the above rules, we can verify for LL(1).
Check whether the following grammar is LL(1) or not.
Solution: For each production, apply Rule 2.
Hence, the condition is satisfied.
Hence, the condition is satisfied.
Hence, the condition is satisfied.
So, the given grammar is LL(1).
Check whether the following grammar is LL(1) or not.
Solution: This is an ambiguous grammar. The sentence a can be derived in two ways. S → A → a or S → a
So, the grammar is ambiguous. According to Rule 3, it is not LL(1).
Check whether the following grammar is LL(1) or not.
Solution: This is a left recursive grammar. According to Rule 4, it is not LL(1).
Check whether the following grammar is LL(1) or not.
Solution: For each production apply Rule 2.
S → aB  b … First(aB) ∩ First(b) is
Hence, the condition is satisfied.
B → bC  b … First(bC) ∩ First(b) is
Hence, the condition is not satisfied.
So, the given grammar is not LL(1)
9.3 LR(K) Grammars
LR(k) grammars play an important role in the study of programming languages and designing of compilers. It stands for lefttoright scanning of input string producing a rightmost derivation using ksymbol look ahead in the input string.
For any context free grammar defined as G = {V, T, P, S}, there are strings valid in the language defined as L(G) = {w  w ∈ T*}. To find the production applied in the last step to get w, we can represent w through substrings, αβγ, which is obtained by substituting A → β in the last step. If it can be shown that A → β is a production substituted in the last step by looking ahead of k symbols, then G is called an LR(k) grammar.
Let G be S → AB, A → aAb  ε, B → Bb  b.
It is easy to see that L(G) = {a^{m}b^{n}  n > m ≥ 1}. Some sentential forms of G obtained by rightmost derivation are AB, ABb^{k}, a^{m}Ab^{m}b^{k}, a^{m}b^{m+k}, where k ≥ 1. AB appears as the RHS of S→AB. So AB may be a handle for AB or ABb^{k}. If we apply the handle to AB, we get S AB. If we apply the handle to ABb^{k}, we get Sb^{k} ABb^{k}. But Sb^{k} is not a sentential form. So to decide whether AB can be a handle, the input has to be scanned to the right of AB. If ε can be replaced by B, then AB serves as handle. By looking ahead of one symbol, we can decide whether AB is a handle. Similarly we can see that the correct handle can be determined by looking ahead of one symbol for various sentential forms.
Definition 1: Let G = {V, T, P, S} be a CFG in which S S only when n = 0. G is an LR(k) grammar (k ≥ 0) if
 S αA w αβw, where α, β ∈ V*, w ∈ T*.
 S α’A’w’ α’β’w’, where α′ β′ ∈ V*, w’ ∈ T* and
 the first αβ +k symbols of αβw and α′ β′ w′ coincide. Then α = α′, A = A’, β = β′.
9.4 Properties of LR(k) Grammars
Every LR(k) grammar G is unambiguous.
 If G is in LR(k) grammars, there exists a deterministic pushdown automaton A accepting L(G).
 If A is a deterministic pushdown automaton A, there exists an LR(k) grammar G such that L(G) = N(A).
 If G is an LR(k) grammar, where k > 1, then there exists an equivalent grammar G1 which is LR(1). In so far as languages are concerned, it is enough to study the languages generated by LR(0) grammars and LR(1) grammars.
 The class of deterministic languages is a proper subclass of the class of CFL.
 DCFL is closed under complementation, but not under union and intersection.
 A CFL is generated by an LR(0) grammar if and only if it is accepted by a DPDA and has the prefix property.
 There is an algorithm to decide whether a given CFG is LR(k) for given natural number k.
Show that the grammar S → 0A2, A → 1A1  1 is not an LR(0) grammar.
Solution: Consider the string 01112 belonging to the language. To derive the string,
0 1 1 1 2 
Look ahead of 1 symbol is needed to select A. 
0 1 A 1 2 
No look ahead is needed to select A 
0 A 2 
No look ahead is needed to select S. 
S 
Since we need at least one symbol to be looked ahead for proper substitution, it is not LR(0) grammar.
Is the grammar S → C  D, C → aC  b, D → aD  C is LR(0)?
Solution: Consider the string aaaab belonging to the language. To derive the string,
a a a b 
No look ahead is needed to select C. 
a a a C 
No look ahead is needed to select C 
a a C 
No look ahead is needed to select C 
a C 
No look ahead is needed to select C 
S 
No look ahead is needed to select S 
(Or) 

a a a b 
No look ahead is needed to select C. 
a a a C 
No look ahead is needed to select C 
a a a D 
No look ahead is needed to select D 
a a D 
No look ahead is needed to select D 
a D 
No look ahead is needed to select D 
D 
No look ahead is needed to select D 
S 
No look ahead is needed to select S 
Since we do not need any look ahead of symbol for proper substitution, it is LR(0) grammar.
9.5 Construction of LR(0) Items for Context Free Grammars
A context free grammar is a quadruplet G = (V, T, P, S), where V, T and P are finite sets of nonterminal symbols, terminal symbols and production rules, respectively, and S ∈ V is the initial symbol of the grammar. The production rules in P are of the form A → α with A ∈ V, α ∈ (N ∪ T)*. We represent the nonterminal symbols with capital letters and terminal symbols with lowercase letters. For any two strings v and w ∈ (N ∪ T)^{+}, we write V ⇒_{G}w if w can be derived from V by substituting a nonterminal A in V by α applying the rule A → α in G.
The language L(G) generated by the grammar G is the set:
L(G) = {w ∈ T*  S w}
Given a context free grammar G, an LR(0) item for G is a production rule with a position marked in its righthand side. For instance, given a production rule A → a B c, we can form four items: [A → •a B c], [A → a •B c], [A → a B• c] and [A → a B c•]. When no confusion is possible, we will drop the square brackets.
Intuitively, the meaning of an item A → α•β is that the parsing has already recognized α. The symbol that follows the marker is called the goal symbol and represents the next symbol to be processed by the parser. Once this symbol is recognized, the marker will be advanced.
9.6 Definition of LR(0) Grammar
A grammar is said to be LR(0) grammar if
 Its start symbol does not appear on the righthand side of any other production.
 If the closure set of a item has a production of the form A → α•, then there is no production of the form B → β• or B → β•γ
The construction of the parsing tables is based on the notion of LR(0) items (simply called items here) which are grammar rules with a special dot added somewhere in the righthand side. For example, the rule E → E + B has the following four corresponding items:
Rules of the form A → ε have only a single item A → •. These rules will be used to denote the state of the parser. The item E → E• + B, for example, indicates that the parser has recognized a string corresponding with E on the input stream and now expects to read a + followed by another string corresponding with B.
Item sets
It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example, if there is also a rule E → E * B, then the items E → E • + B and E → E• * B will both apply after a string corresponding with E has been read. Therefore, we will characterize the state of the parser by a set of items, in this case, the set {E → E• + B, E → E• * B}.
Closure of item sets
An item with a dot in front of a nonterminal, such as E → E + •B, indicates that the parser expects to parse the nonterminal B next. To ensure the item set contains all possible rules the parser may need in the midst of parsing, it must include all items describing how B itself will be parsed. This means that if there are rules such as B → 1 and B → 0, then the item set must also include the items B → •1 and B → •0. In general, this can be formulated as follows:
If there is an item of the form A → v • Bw in an item set and in the grammar there is a rule of the form B → w′, then the item B → • w′ should also be in the item set.
Any set of items can be extended such that it satisfies this rule: This is because we can simply continue to add the appropriate items until all nonterminals preceded by dots are accounted for. The minimal extension is called the closure of an item set and written as closure(I) where I is an item set. It is these closed item sets that we will take as the states of the parser, although only the ones that are actually reachable from the begin state will be included in the tables.
Augmented grammar
Before we start determining the transitions between the different states, the grammar is always augmented with an extra rule:
where S is a new start symbol and E is the old start symbol. The parser will use this rule for reduction exactly when it has accepted the input string.
State whether the following grammar is an LR(0) grammar.
Solution: Add a new production as S → A.
Construct LR(0) items.
1 

A → •a A a 
1 
A → •B 
3 
B → •b 
4 
I_{1}: S → A • 

I_{2}: A → a• A a 
5 
A → •a A a 
1 
A → •B 
3 
B → •b 
4 
I_{3}: A → B• 

I_{4}: B → b• 

I_{5}: A → aA• a 
6 
I_{6}: A → aAa• 
The given grammar is LR(0) grammar as no item set that terminates with dot has any other production.
State whether the following grammar is LR(0).
It is for this augmented grammar that we will determine the item sets and the transitions between them.
I_{0}: S → •E 
1 
E → •E * B 
1 
E → •E + B 
1 
E → •B 
2 
3  
B → •1 
4 
I_{1}: S → E• 

E → E• * B 
5 
E → E• + B 
6 
I_{2}: E → B• 

I_{3}: B → 0• 

I_{4}: B → 1• 

I_{5}: E → E * • B 
7 
B → •0 
3 
B → •1 
4 
I_{6}: E → E + • B 
8 
B → •0 
3 
B → •1 
4 
I_{7}: E → E * B• 

I_{8}: E → E + B• 
DFA for the item set is as follows.
This grammar is not LR (0), as in state I_{1}, there is one production ending with • and in the same set, there are other items with • in other positions. Hence, this cannot be LR (0) grammar.
9.7 LR(1) Grammar
LR(1) grammar consists items which are LR(0) items with a look ahead element, which is either a terminal or a $ (a special symbol which is the rightend marker of the string).
LR(1) item would be of the form
This is a valid item for a viable prefix γ if there is a rightmost derivation
S δAy δαβy, where δα = γ, and either
 a is the first symbol of y, or
 y = ε and a is $.
Closure of LR(1) items is computed by the following steps:
 Add a new transition S → •A, {$} where S is new root symbol and A is the starting symbol of the grammar.
 If there is a transition A → α• Bβ,{a_{1}, a_{2}, …a_{m}} in State I, then there would a transition A → α B• β, {a_{1}, a_{2}, …a_{m}} in the next state on B.
 If there is a transition A→ α• Bβ, {a_{1}, a_{2}, …a_{m}} in State I and if there exists a production B → γ, then add a transition B → •γ, T in the same set, where T is set of terminals b such that
 β derives a terminal string beginning with b or
 β ε and b is a for some 1 ≤ i ≤ n.
The grammar is said to LR(1) if it satisfies the following constraints.
 The start symbol does not appear on the right side of any other production.
 In any set of items I, if there is a production A → α•, {a_{1}, a_{2}, …a_{m}}, then
 No a_{i} appears immediately to the right of the dot in any item of I.
 If B → β•, {b_{1}, b_{2}, … b_{k}} is another complete item in I, then a_{i} ≠ b_{j} for any 1 ≤ i ≤ m and 1 ≤ j ≤ k.
Find whether the following grammar is LR(1).
Solution: First add a new production S → A.
Computing LR(1) items.
I_{0} S → •A, {$} 
1 
A → •BA, {$} 
2 
A → •, {$} 

B → •aB, {a  b  $} 
3 
B → •b, {a  b  $} 
4 
I_{1} S → •A, {$} 

I_{2} A → B•A, {$} 
5 
2 

A → •, {$} 

B → •aB, {a  b  $} 
3 
B → •b, {a  b  $} 
4 
I_{3} B → a•B,{a  b  $} 
6 
B → •aB, {a  b  $} 
3 
B → •b, {a  b  $} 
4 
I_{4} B → b•, {a  b  $} 

I_{5} A → BA•, {$} 
5 
I_{6} B → aB•, {a  b  $} 
6 
DFA for LR(1) items is shown below.
This grammar is LR(1) grammar as it satisfies the required rules of LR(1) grammar.
Solved Problems
Problem 1: Find First () and Follow() sets for each nonterminals.
Solution: First(A) = First(aABe)
This is same as first of first symbol, that is, First(A) = {a}
First(B) = {c, ε} as First(terminal) is {terminal}
and First(B) is {ε} Since B→ ε
Similarly First(C) = {d, ε}.
Problem 2: Check whether the following grammar is LL(1).
Solution: This grammar is an ambiguous grammar.
The string ab can be derived in two ways. An ambiguous grammar is not LL(1).
So, this is not LL(1).
Problem 3: Check whether the following grammar is LL(1):
Solution: The rule for checking is
• A grammar without null rules is LL(1), for each production of the form A → β_{1}  β_{2} β_{3}, First(β_{1}), First(β_{2}), First(β_{3}), … must be mutually disjoint, that is,
i) First(β_{i}) ∩ First(β_{j}) = ∅
Hence, the given grammar is LL(1) if
First(AaAb) ∩ First(BbBa) = ∅
That is, {a} ∩ {b} = ∅. So condition is satisfied.
The 2nd and 3rd production in the given grammar has only one rule on r.h.s. So there is no need to check any condition.
Hence, this is LL(1).
Problem 4: Check whether the following grammar is LL(1):
Solution: This grammar is a left recursive grammar because of rule L → L, S  S. Any left Grammar is not LL(1).
Hence, it is not LL (1).
Problem 5: Check whether the following grammar is LR(0)
Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.
There are no final items with one more nonfinal item or another final item. Hence, grammar is LR(0).
Problem 6: Check whether the following grammar is LR(0).
Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.
State I_{2} has final item with one more nonfinal item. Hence, grammar is not LR(0).
Problem 7: Check whether the following grammar is LR(1):
Solution: Draw the DFA with LR(1) items by using Closure( ) and goto( ) functions.
I_{0} S → •S, $ 
1 
S → •Aa, $ 
2 
S → •bAc, $ 
3 
S → •Bc, $ 
4 
S → •bBa, $ 
3 
A → •d, a 
5 
B → •d, c 
5 
I_{1} S → S•, $ 

I_{2} S → A•a, $ 
6 
I_{3} S → b•Ac, $ 
7 
S → b•Ba, $ 
8 
A → •d, c 
9 
B → •d, a 
9 
I_{4} S → B•c, $ 
10 
I_{5} A → d•, a 

B → d•, c 

I_{6} S → Aa•, $ 

I_{7} S → bA•c, $ 
11 
I_{8} S → bB•a, $ 
12 
I_{9} A → d•, c 

B → d•, a 

I_{10} S → Bc•, $ 

I_{11} S → bAc•, $ 

I_{12} S → bBa•, $ 
There are no final items with one more nonfinal item or another final item. Hence, grammar is LR(1).
Problem 8: Check whether the following grammar is LR(0).
Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.
I_{0} S → •S 
1 
S → •AA 
2 
A → •aA 
3 
A → •b 
4 
I_{1} S → S• 

I_{2} S → A•A 
5 
A → •aA 
3 
A → •b 
4 
I_{3} A → a•A 
6 
A → •aA 
3 
A → •b 
4 
I_{4} A → b• 
5 
I_{5} S → AA• 
4 
I_{6} A → aA• 
There are no final items with one more nonfinal item or another final item. Hence, the grammar is LR(0).
Problem 9: Check whether the following grammar is LR(1):
Solution: Draw the DFA with LR(1) items by using Closure( ) and goto( ) functions.
There are no final items with one more nonfinal item or another final item. Hence, the given grammar is LR(1).
Problem 10: Check whether the following grammar is LL(1) or not.
Solution: For each production, apply Rule 2.
S → aBCe when there is only one production for nonterminal no need to check any condition.
B → b  ε …. First(b) ∩ Follow(B) is
C → c  ε …. First(c) ∩ Follow(C) is
So the given grammar is LL(1).
Problem 11: Check whether the following grammar is LL(1) or not.
Solution: For each production, apply Rule 1.
S → aSbS  bSaS …. First(aSbS) ∩ Follow(bSaS) is
Hence, the condition is satisfied.
S → aSbS  ε …. First(aSbS) ∩ Follow(S) is
Hence, the condition is not satisfied.
So the given grammar is not LL(1).
Problem 12: State whether the following grammar is LR(0).
Solution: In the given grammar (0) is augumented rule. The LR items can be computed without adding any new grammar rule. The list of items are listed below.
I_{0}: S` → •S 
1 
S → •AS 
2 
S → •b 
3 
A → •SA 
1 
A → •a 
4 
I_{1}: S`→ S• 

A → S•A 
5 
A → •SA 
1 
A → •a 
4 
S → •AS 
5 
S → •b 
3 
I_{2}: S → A•S 
6 
S → •AS 
2 
S → •b 
3 
A → •SA 
6 
A → •a 
4 
I_{3}: S → b• 

I_{4}: A → a• 

I_{5}: A → SA• 

S → A•S 
6 
S → •AS 
2 
S → •b 
3 
A → •SA 
6 
A → •a 
4 
A → S•A 
6 
A → •SA 
2 
A → •a 
3 
S → •AS 
6 
S → •b 
4 
DFA for the item set is as follows.
The given grammar is not LR(0) as in the States I_{1}, I_{5}, I_{6}, there is a production ending with • and there are other productions which have • in other positions.
Problem 13: State whether the following grammar is LR(0).
Solution: It is for this augmented grammar that we will determine the item sets and the transitions between them.
I_{0}: S` → •S 
1 
S → •iSeS 
2 
2 

S → •a 
3 
I_{1}: S`→ S• 

I_{2}: S → i•SeS 
4 
S → i•S 
4 
S → •iSeS 
2 
S → •iS 
2 
A → •a 
3 
I_{3}: S → a• 

I_{4}: S → iS•eS 
5 
S → iS• 

I_{5}: S → iSe•S 
4 
S → •iSeS 
2 
S → •iS 
2 
S → •a 
3 
I_{6}: S → iSeS• 
DFA for the item set is as follows.
The given grammar is not an LR(0) grammar as in State I_{4}, there is a production ending with • and there are other productions with • in other position.
Problem 14: State whether the following grammar is LR(1).
Solution: It is for this augmented grammar that we will determine the item sets and the transitions between them.
I_{0}: S` → •S, $ 
1 
S → •iSeS, $ 
2 
S → •iS, $ 
2 
S → •a, $ 
3 
I_{1}: S`→ S•, $ 

I_{2}: S → i•SeS, $ 
4 
S → i•S, $ 
4 
S → •iSeS, e/$ 
5 
S → •iS, e/$ 
5 
S → •a, e/$ 
6 
I_{3}: S → a•, $ 

I_{4}: S → iS•eS, $ 
7 
S → iS•, $ 

I_{5}: S → i•SeS, e/$ 
8 
S → i•S, e/$ 
8 
S → •iSeS, e/$ 
5 
S → •iS, e/$ 
5 
S → •a, e/$ 
6 
I_{6}: S → a•, e/$ 

I_{7}: S → iSe•S, $ 
9 
S → •iSeS, $ 
2 
S → •iS, $ 
2 
S → •a, $ 
3 
I_{8}: S → iS•eS, e/$ 
10 
S → iS•, e/$ 

I_{9}: S → iSeS•, $ 

I_{10}: S → iSe•S, e/$ 
11 
S → •iSeS, e/$ 
5 
S → •iS, e/$ 
5 
S → •a, e/$ 
6 
I_{11}: S → iSeS•, e/$ 
The DFA for the LR(1) items is shown below.
The given grammar is not LR(1) as in State I_{8}, there is a production ending with •, and the symbol e listed for the production as look ahead is to the right of • in other production.
Problem 15: State whether the following grammar is LR(1).
Solution: It is for this augmented grammar we will determine the item sets and the transitions between them.
I_{0}: S` → •S, $ 
1 
S → •AA, $ 
2 
A → •aA, a/$ 
3 
A → •b, a/$ 
4 
I_{1}: S`→ S•, $ 

I_{2}: S → A•A, $ 
5 
A → •aA, $ 
6 
A → •b, $ 
7 
I_{3}: A → a•A, a/b 
8 
A → •aA, a/b 
3 
A → •b, a/b 
4 
I_{4}: A → b•, a/b 

I_{5}: S → AA•, $ 

9 

A → •aA, $ 
6 
A → •b, $ 
7 
I_{7}: A → b•, $ 

I_{8}: A → aA•, a/b 

I_{9}: A → aA•, $ 
The DFA for the LR(1) items is shown below.
The grammar is LR(1) grammar as it satisfies the rules.
Summary
 LR(K) stands for lefttoright scan of input string using the rightmost derivation with a look ahead of K symbols.
 Every LR(K) grammar is an unambiguous grammar.
 For every LR(K) grammar, there exists a deterministic push down automaton.
 The CFL generated by LR(0) grammar has strings which satisfy the prefix property.
 For any LR grammar, the first root nonterminals should not appear on the right side of any other production.
 LR(0) grammars form a subset of LR(1) grammars.
Short Answers
 List the rules to find first
Answer:
 If x is a terminal, then first(x) is x itself.
Ex: first (+) = {+}, First(id)={id}.
 If x is a nonterminal
 & is defined with εrules i.e. x → ε, then First (x) ={ε}.
 & is defined with non εrules i.e. x → A_{1}A_{2}A_{3 }then
First (x) = First (A_{1}A_{2}A_{3}) = First (A_{1}) if A_{1} =∗>= First (A_{1}) – {ε} ∪ First (A_{2} A_{3})) if A_{1} =∗> ε
 If x is a terminal, then first(x) is x itself.
 Compute the first (S) the given grammar S → Ab, A → a  ε
Answer: First(S) = {a, b}
 Compute the first (S) the given grammar
S → ABCDE, A → a ε, B → b, C → c ε, D → d, E → e
Answer: First(S) = {a, b, c, d, e}
 Define Follow
Answer: Follow of any non terminal is the element that appears first immediately after the last element derived by that non terminal.
 Find follow of C in the given grammar
S → aB b, B → bC b, C → cS d
Answer: Follow of (C) = {$}
 How do you say the given grammar is LR(0)?
Answer: A grammar is said to be LR(0) grammar if, Its start with a symbol does not appear on right hand side of any other production and if the closure set of item has a production of the form A → α • then there is no production of the form B → β • or B → β • g
Fill in the Blanks
 In LR(K) grammars, k stands for ______________.
 LR(0) grammars are more powerful than LR(1) grammars. (True/False)
 The deterministic pushdown automaton uses ______________ grammars.
 The class of languages that is generated by LR(0) grammar is also called _______.
 Regular grammars form a superset of LR(0) grammars. (TrueFalse)
 ______________ property states that if w ∈ L, then proper prefix of w Ï L.
 ____________ grammars are unambiguous.
 The string obtained by the rightmost derivation that is in sentential form is called _____________.
 The string obtained by either rightmost derivation or left most derivation that has only terminals is called ______________.
 All CFGs are either LR(0) or LR(1) grammars.(TrueFalse)
 Look ahead
 False
 LR
 deterministic CFGs
 False
 Prefix
 LR(K)
 Handle
 Yield
 False
Objective Question Bank
 An LL(1) grammar is used for as below parser
 Topdown
 Bottomup
 Both
 None
 An LR(0) grammar defines
 CSL
 recursive
 recursively enumerable
 DCFL
 The item A→•b,{a/b/$} is a/an
 LR(3)
 LR(1)
 LR(0)
 Grammar rule
 The item B→•b is a/an
 LR(3)
 LR(1)
 LR(0)
 Grammar rule
 An LR(1) grammar is suitable for
 Topdown
 Bottomup parser
 Both
 None
 S → SS/(S)/a is not suitable for LL(1) because the grammar is
 ambiguous
 left recursive
 right recursive
 None
 S → S + A/A, A→a is not suitable for LL(1) because the grammar is
 ambiguous
 left recursive
 right recursive
 None
 The statement “Every unambiguous grammar is LL(1)”
 true
 false
 cannot say
 None
 The statement “Every LR(0) is LL(1)” is
 true
 false
 cannot say
 None
 The statement “Every LR(0) is LR(1)” is
 true
 false
 cannot say
 None
 The following grammar is S→A  a, A → a
 LL(1)
 LR(0)
 LR(1)
 None
 The LR(0) grammar define
 CSL’s
 CFL’s
 DCFL’s
 None
 Consider the following grammar
A → BCD a, B→ a  ε, C→ b  ε, D→ c  ε
First(A) is
 {a, b, c, ε}
 {a, b, c}
 {a, b, c}
 None
 Consider the following grammar
A → BCD a, B→ a  ε, C→ b  ε, D→ c  ε
Follow (A) is
 {b, c, d, ε}
 {b, c}
 {b, c, d, $}
 None
 Which of the following is true?
 LL(1) ⊂ LR(1)
 LR(0) ⊂ LR(1)
 LR(1) ⊂ LL(1)
 None
Answers
 A
 D
 B
 C
 B
 A
 B
 B
 C
 A
 D
 C
 A
 C
 B
Exercises
 Check whether the following grammar is LL(1) or not. S→ aS  Sa  a
 Check whether the following grammar is LL(1) or not.
S → AaAb  BbBaA → εB → ε
 List LR(0) items for the following grammar:
S → (S)  {S}  SS  a
 Find whether the above grammar is LR(0) or not.
 Show that the following grammar is not LR(0).
S → S sub S sup S  S sub S  S sup S  a  b
 Is the following grammar LR(0)?
S → bA  aB, A → aBB  aS  a, B → bAA  bS  b
 List LR(1) items for the following grammar:
E → E + E  E*E  E − E  E/E  (E)  a
 State whether the above grammar is LR(1) or not.
 Find whether the following grammar is LR(1).
S → S sub S sup S  S sub S  S sup S  a  b
 Check whether the following grammar is LL(1) or not.
S → Aa  bAc  dc  bdaA → d