9. LR(k) and LL(1) Grammars – Formal Languages and Automata Theory

9

LR(k) and LL(1) Grammars

  • The most widely used top-down parsers are constructed with LL(1) grammars. The most powerful bottom-up 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.

  1. If x is a terminal, then First (x) is x itself.
    Ex: First(+) = {+}, First(id) = {id}.
  2. If x is a non-terminal
    1. & is defined with ε-rules, that is, X → ε, then First(X) = {ε}.
    2. & is defined with non-ε-rules, that is, X → A1A2A3 then
      First(x) = First(A1A2A3) = First(A1) if A1 ε
      = First(A1) − {ε} ∪ First(A2 A3) if A1 ε
Example 9.1

Find First(·) of each non-terminal in the grammar given:

 

S → AB
A → a | ε
B → b | ε

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, ε}.

Example 9.2

Find First(·) of each non-terminal in the grammar given:

 

S → ABCDE
A → a | ε
B → b | ε
C → c | ε
D → d | ε
E → e

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 non-terminal, 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).
Example 9.3

Find Follow(·) of each non-terminal in the grammar

 

S → aABb
A → c | ε
B → d | ε

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}

Example 9.4

Find Follow(·) of each non-terminal in the grammar

 

S → ABCDE
A → a | ε
B → b | ε
C → c | ε
D → d | ε
E → e | ε

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

  1. 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,
    1. First(βi) ∩ First(βj) = Ø
  2. A grammar with null rules is LL(1) provided for each production of the form
    1. A → β | ε, First(β) and Follow(A) must be mutually disjoint, that is,
      1. First(β) ∩ Follow(A) = Ø
  3. An ambiguous grammar cannot be LL(1).
  4. Left recursive grammar is not LL(1).

Given any grammar, by using the above rules, we can verify for LL(1).

Example 9.5

Check whether the following grammar is LL(1) or not.

 

S → aB | ε
B → bC | ε
C → cS | ε

Solution: For each production, apply Rule 2.

 

S → aB | ε … First(aB) ∩ Follow(S) is {a} ∩ {$} = Ø.

 

Hence, the condition is satisfied.

 

B → bC | ε … First(bC) ∩ Follow(B) is
{b} ∩ {$} = Ø

 

Hence, the condition is satisfied.

 

C → cS| ε … First(c) ∩ Follow(C) is
{c} ∩ {$} = Ø

Hence, the condition is satisfied.

So, the given grammar is LL(1).

Example 9.6

Check whether the following grammar is LL(1) or not.

 

S → A | a
A → a

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

Example 9.7

Check whether the following grammar is LL(1) or not.

 

S → (L) | a
L → L, S | S

Solution: This is a left recursive grammar. According to Rule 4, it is not LL(1).

Example 9.8

Check whether the following grammar is LL(1) or not.

 

S → aB | b
B → bC | b
C → cS | d

Solution: For each production apply Rule 2.

S → aB | b … First(aB) ∩ First(b) is

{a} ∩ {b} = Ø

Hence, the condition is satisfied.

B → bC | b … First(bC) ∩ First(b) is

{b} ∩ {b} ≠ Ø

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 left-to-right scanning of input string producing a right-most derivation using k-symbol 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.

Example 9.9

Let G be S → AB, A → aAb | ε, B → Bb | b.

It is easy to see that L(G) = {ambn | n > m ≥ 1}. Some sentential forms of G obtained by right-most derivation are AB, ABbk, amAbmbk, ambm+k, where k ≥ 1. AB appears as the RHS of S→AB. So AB may be a handle for AB or ABbk. If we apply the handle to AB, we get S AB. If we apply the handle to ABbk, we get Sbk ABbk. But Sbk 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

  1. S αA w αβw, where α, β ∈ V*, w ∈ T*.
  2. S α’A’w’ α’β’w’, where α′ β′ ∈ V*, w’ ∈ T* and
  3. 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.

  1. If G is in LR(k) grammars, there exists a deterministic pushdown automaton A accepting L(G).
  2. If A is a deterministic pushdown automaton A, there exists an LR(k) grammar G such that L(G) = N(A).
  3. 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.
  4. The class of deterministic languages is a proper subclass of the class of CFL.
  5. DCFL is closed under complementation, but not under union and intersection.
  6. A CFL is generated by an LR(0) grammar if and only if it is accepted by a DPDA and has the prefix property.
  7. There is an algorithm to decide whether a given CFG is LR(k) for given natural number k.
Example 9.10

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.

Example 9.11

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 non-terminal 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 non-terminal symbols with capital letters and terminal symbols with lower-case letters. For any two strings v and w ∈ (N ∪ T)+, we write V ⇒Gw if w can be derived from V by substituting a non-terminal 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 image w}

Given a context free grammar G, an LR(0) item for G is a production rule with a position marked in its right-hand 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 right-hand 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 → β•γ

Items

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 right-hand side. For example, the rule E → E + B has the following four corresponding items:

 

E → •E + B
E → E• + B
E → E + •B
E → E + B•

 

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 non-terminal, such as E → E + •B, indicates that the parser expects to parse the non-terminal 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 non-terminals 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:

 

(0) S → E

 

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.

Example 9.12

State whether the following grammar is an LR(0) grammar.

 

A → aAa | B, B → b

Solution: Add a new production as S → A.

Construct LR(0) items.

I0: S → •A
1
A → •a A a
1
A → •B
3
B → •b
4
I1: S → A •
I2: A → a• A a
5
A → •a A a
1
A → •B
3
B → •b
4
I3: A → B•
I4: B → b•
I5: A → aA• a
6
I6: A → aAa•

The given grammar is LR(0) grammar as no item set that terminates with dot has any other production.

Example 9.13

State whether the following grammar is LR(0).

 

(0) S → E
(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

 

It is for this augmented grammar that we will determine the item sets and the transitions between them.

I0: S → •E
1
E → •E * B
1
E → •E + B
1
E → •B
2
B → •0
3
B → •1
4
I1: S → E•
E → E• * B
5
E → E• + B
6
I2: E → B•
I3: B → 0•
I4: B → 1•
I5: E → E * • B
7
B → •0
3
B → •1
4
I6: E → E + • B
8
B → •0
3
B → •1
4
I7: E → E * B•
I8: E → E + B•

DFA for the item set is as follows.

This grammar is not LR (0), as in state I1, 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 right-end marker of the string).

LR(1) item would be of the form

 

A → α • β, {a1, a2, …am}

 

This is a valid item for a viable prefix γ if there is a right-most 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:

  1. Add a new transition S → •A, {$} where S is new root symbol and A is the starting symbol of the grammar.
  2. If there is a transition A → α• Bβ,{a1, a2, …am} in State I, then there would a transition A → α B• β, {a1, a2, …am} in the next state on B.
  3. If there is a transition A→ α• Bβ, {a1, a2, …am} 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 → α•, {a1, a2, …am}, then
    • No ai appears immediately to the right of the dot in any item of I.
    • If B → β•, {b1, b2, … bk} is another complete item in I, then ai ≠ bj for any 1 ≤ i ≤ m and 1 ≤ j ≤ k.
Example 9.14

Find whether the following grammar is LR(1).

 

A → BA | ε, B → aB | b

Solution: First add a new production S → A.

Computing LR(1) items.

I0 S → •A, {$}
1
A → •BA, {$}
2
A → •, {$}
B → •aB, {a | b | $}
3
B → •b, {a | b | $}
4
I1 S → •A, {$}
I2 A → B•A, {$}
5
A → •BA, {$}
2
A → •, {$}
B → •aB, {a | b | $}
3
B → •b, {a | b | $}
4
I3 B → a•B,{a | b | $}
6
B → •aB, {a | b | $}
3
B → •b, {a | b | $}
4
I4 B → b•, {a | b | $}
I5 A → BA•, {$}
5
I6 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 non-terminals.

 

A → a A B e
B → c | ε
C → d | ε

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

 

S → Aa A b | BaBb
A → ε
B → ε

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):

 

S → Aa A b | BbBa
A → ε
B → ε

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):

S → (L) | b
L → L, S | S

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)

 

S (L) | b
L L, S | S

Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.

There are no final items with one more non-final item or another final item. Hence, grammar is LR(0).

Problem 6: Check whether the following grammar is LR(0).

 

E → T + E | T
T → i

Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.

State I2 has final item with one more non-final item. Hence, grammar is not LR(0).

Problem 7: Check whether the following grammar is LR(1):

 

S → Aa | bAc | Bc | bBa
A → d
B → d

Solution: Draw the DFA with LR(1) items by using Closure( ) and goto( ) functions.

I0 S → •S, $
1
S → •Aa, $
2
S → •bAc, $
3
S → •Bc, $
4
S → •bBa, $
3
A → •d, a
5
B → •d, c
5
I1 S → S•, $
I2 S → A•a, $
6
I3 S → b•Ac, $
7
S → b•Ba, $
8
A → •d, c
9
B → •d, a
9
I4 S → B•c, $
10
I5 A → d•, a
B → d•, c
I6 S → Aa•, $
I7 S → bA•c, $
11
I8 S → bB•a, $
12
I9 A → d•, c
B → d•, a
I10 S → Bc•, $
I11 S → bAc•, $
I12 S → bBa•, $

There are no final items with one more non-final item or another final item. Hence, grammar is LR(1).

Problem 8: Check whether the following grammar is LR(0).

 

S → AA
A → a A | b

Solution: Draw the DFA with LR(0) items by using Closure( ) and goto( ) functions.

I0 S → •S
1
S → •AA
2
A → •aA
3
A → •b
4
I1 S → S•
I2 S → A•A
5
A → •aA
3
A → •b
4
I3 A → a•A
6
A → •aA
3
A → •b
4
I4 A → b•
5
I5 S → AA•
4
I6 A → aA•

There are no final items with one more non-final item or another final item. Hence, the grammar is LR(0).

Problem 9: Check whether the following grammar is LR(1):

 

S → AA
A → a A | b

Solution: Draw the DFA with LR(1) items by using Closure( ) and goto( ) functions.

There are no final items with one more non-final item or another final item. Hence, the given grammar is LR(1).

Problem 10: Check whether the following grammar is LL(1) or not.

 

S → aBCe
B → b | ε
C → c | ε

Solution: For each production, apply Rule 2.

S → aBCe when there is only one production for non-terminal no need to check any condition.

B → b | ε …. First(b) ∩ Follow(B) is

{b} ∩ {c, e} = ∅ the condition is satisfied.

C → c | ε …. First(c) ∩ Follow(C) is

{c} ∩ {e} = ∅ the condition is satisfied.

So the given grammar is LL(1).

Problem 11: Check whether the following grammar is LL(1) or not.

 

S → aSbS | bSaS | ε

Solution: For each production, apply Rule 1.

S → aSbS | bSaS …. First(aSbS) ∩ Follow(bSaS) is

{a} ∩ {b} = ∅

Hence, the condition is satisfied.

S → aSbS | ε …. First(aSbS) ∩ Follow(S) is

{a} ∩ {a, b, $}1 ≠ ∅

Hence, the condition is not satisfied.

So the given grammar is not LL(1).

Problem 12: State whether the following grammar is LR(0).

 

(0) S` → S
(1) S → AS
(2) S → b
(3) A → SA
(4) A → a

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.

I0: S` → •S
1
S → •AS
2
S → •b
3
A → •SA
1
A → •a
4
I1: S`→ S•
A → S•A
5
A → •SA
1
A → •a
4
S → •AS
5
S → •b
3
I2: S → A•S
6
S → •AS
2
S → •b
3
A → •SA
6
A → •a
4
I3: S → b•
I4: A → a•
I5: A → SA•
S → A•S
6
S → •AS
2
S → •b
3
A → •SA
6
A → •a
4
I6: S → AS•
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 I1, I5, I6, 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).

 

(0) S` → S
(1) S → iSeS
(2) S → iS
(3) S → a

Solution: It is for this augmented grammar that we will determine the item sets and the transitions between them.

I0: S` → •S
1
S → •iSeS
2
S → •iS
2
S → •a
3
I1: S`→ S•
I2: S → i•SeS
4
S → i•S
4
S → •iSeS
2
S → •iS
2
A → •a
3
I3: S → a•
I4: S → iS•eS
5
S → iS•
I5: S → iSe•S
4
S → •iSeS
2
S → •iS
2
S → •a
3
I6: S → iSeS•

DFA for the item set is as follows.

The given grammar is not an LR(0) grammar as in State I4, 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).

 

(0) S` → S
(1) S → iSeS
(2) S → iS
(3) S → a

Solution: It is for this augmented grammar that we will determine the item sets and the transitions between them.

I0: S` → •S, $
1
S → •iSeS, $
2
S → •iS, $
2
S → •a, $
3
I1: S`→ S•, $
I2: S → i•SeS, $
4
S → i•S, $
4
S → •iSeS, e/$
5
S → •iS, e/$
5
S → •a, e/$
6
I3: S → a•, $
I4: S → iS•eS, $
7
S → iS•, $
I5: S → i•SeS, e/$
8
S → i•S, e/$
8
S → •iSeS, e/$
5
S → •iS, e/$
5
S → •a, e/$
6
I6: S → a•, e/$
I7: S → iSe•S, $
9
S → •iSeS, $
2
S → •iS, $
2
S → •a, $
3
I8: S → iS•eS, e/$
10
S → iS•, e/$
I9: S → iSeS•, $
I10: S → iSe•S, e/$
11
S → •iSeS, e/$
5
S → •iS, e/$
5
S → •a, e/$
6
I11: S → iSeS•, e/$

The DFA for the LR(1) items is shown below.

The given grammar is not LR(1) as in State I8, 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).

 

(0) S` → S
(1) S → AA
(2) S → aA
(3) S → b

Solution: It is for this augmented grammar we will determine the item sets and the transitions between them.

I0: S` → •S, $
1
S → •AA, $
2
A → •aA, a/$
3
A → •b, a/$
4
I1: S`→ S•, $
I2: S → A•A, $
5
A → •aA, $
6
A → •b, $
7
I3: A → a•A, a/b
8
A → •aA, a/b
3
A → •b, a/b
4
I4: A → b•, a/b
I5: S → AA•, $
I6: A → a•A, $
9
A → •aA, $
6
A → •b, $
7
I7: A → b•, $
I8: A → aA•, a/b
I9: A → aA•, $

The DFA for the LR(1) items is shown below.

The grammar is LR(1) grammar as it satisfies the rules.

Summary

  1. LR(K) stands for left-to-right scan of input string using the right-most derivation with a look ahead of K symbols.
  2. Every LR(K) grammar is an unambiguous grammar.
  3. For every LR(K) grammar, there exists a deterministic push down automaton.
  4. The CFL generated by LR(0) grammar has strings which satisfy the prefix property.
  5. For any LR grammar, the first root non-terminals should not appear on the right side of any other production.
  6. LR(0) grammars form a subset of LR(1) grammars.

Short Answers

  1. List the rules to find first

    Answer:

    1. If x is a terminal, then first(x) is x itself.
      Ex: first (+) = {+}, First(id)={id}.
    2. If x is a nonterminal
      1. & is defined with ε-rules i.e. x → ε, then First (x) ={ε}.
      2. & is defined with non ε-rules i.e. x → A1A2A3 then
        First (x) = First (A1A2A3) = First (A1) if A1 =∗>
        = First (A1) – {ε} ∪ First (A2 A3)) if A1 =∗> ε
  2. Compute the first (S) the given grammar S → Ab, A → a | ε

    Answer: First(S) = {a, b}

  3. Compute the first (S) the given grammar

    S → AB|CD|E, A → a |ε, B → b, C → c |ε, D → d, E → e

    Answer: First(S) = {a, b, c, d, e}

  4. Define Follow

    Answer: Follow of any non terminal is the element that appears first immediately after the last element derived by that non terminal.

  5. Find follow of C in the given grammar

    S → aB |b, B → bC |b, C → cS |d

    Answer: Follow of (C) = {$}

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

  1. In LR(K) grammars, k stands for ______________.
  2. LR(0) grammars are more powerful than LR(1) grammars. (True/False)
  3. The deterministic pushdown automaton uses ______________ grammars.
  4. The class of languages that is generated by LR(0) grammar is also called _______.
  5. Regular grammars form a superset of LR(0) grammars. (True|False)
  6. ______________ property states that if w ∈ L, then proper prefix of w Ï L.
  7. ____________ grammars are unambiguous.
  8. The string obtained by the right-most derivation that is in sentential form is called _____________.
  9. The string obtained by either right-most derivation or left most derivation that has only terminals is called ______________.
  10. All CFGs are either LR(0) or LR(1) grammars.(True|False)

Answers

  1. Look ahead
  2. False
  3. LR
  4. deterministic CFGs
  5. False
  6. Prefix
  7. LR(K)
  8. Handle
  9. Yield
  10. False

Objective Question Bank

  1. An LL(1) grammar is used for as below parser
    1. Top-down
    2. Bottom-up
    3. Both
    4. None
  2. An LR(0) grammar defines
    1. CSL
    2. recursive
    3. recursively enumerable
    4. DCFL
  3. The item A→•b,{a/b/$} is a/an
    1. LR(3)
    2. LR(1)
    3. LR(0)
    4. Grammar rule
  4. The item B→•b is a/an
    1. LR(3)
    2. LR(1)
    3. LR(0)
    4. Grammar rule
  5. An LR(1) grammar is suitable for
    1. Top-down
    2. Bottom-up parser
    3. Both
    4. None
  6. S → SS/(S)/a is not suitable for LL(1) because the grammar is
    1. ambiguous
    2. left recursive
    3. right recursive
    4. None
  7. S → S + A/A, A→a is not suitable for LL(1) because the grammar is
    1. ambiguous
    2. left recursive
    3. right recursive
    4. None
  8. The statement “Every unambiguous grammar is LL(1)”
    1. true
    2. false
    3. cannot say
    4. None
  9. The statement “Every LR(0) is LL(1)” is
    1. true
    2. false
    3. cannot say
    4. None
  10. The statement “Every LR(0) is LR(1)” is
    1. true
    2. false
    3. cannot say
    4. None
  11. The following grammar is S→A | a, A → a
    1. LL(1)
    2. LR(0)
    3. LR(1)
    4. None
  12. The LR(0) grammar define
    1. CSL’s
    2. CFL’s
    3. DCFL’s
    4. None
  13. Consider the following grammar

    A → BCD |a, B→ a | ε, C→ b | ε, D→ c | ε

    First(A) is

    1. {a, b, c, ε}
    2. {a, b, c}
    3. {a, b, c}
    4. None
  14. Consider the following grammar

    A → BCD |a, B→ a | ε, C→ b | ε, D→ c | ε

    Follow (A) is

    1. {b, c, d, ε}
    2. {b, c}
    3. {b, c, d, $}
    4. None
  15. Which of the following is true?
    1. LL(1) ⊂ LR(1)
    2. LR(0) ⊂ LR(1)
    3. LR(1) ⊂ LL(1)
    4. None

Answers

  1. A
  2. D
  3. B
  4. C
  5. B
  6. A
  7. B
  8. B
  9. C
  10. A
  11. D
  12. C
  13. A
  14. C
  15. B

Exercises

  1. Check whether the following grammar is LL(1) or not. S→ aS | Sa | a
  2. Check whether the following grammar is LL(1) or not.

     

    S → AaAb | BbBa
    A → ε
    B → ε

     

  3. List LR(0) items for the following grammar:

     

    S → (S) | {S} | SS | a

     

  4. Find whether the above grammar is LR(0) or not.
  5. Show that the following grammar is not LR(0).

     

    S → S sub S sup S | S sub S | S sup S | a | b

     

  6. Is the following grammar LR(0)?

     

    S → bA | aB, A → aBB | aS | a, B → bAA | bS | b

     

  7. List LR(1) items for the following grammar:

     

    E → E + E | E*E | E − E | E/E | (E) | a

     

  8. State whether the above grammar is LR(1) or not.
  9. Find whether the following grammar is LR(1).

     

    S → S sub S sup S | S sub S | S sup S | a | b

     

  10. Check whether the following grammar is LL(1) or not.

     

    S → Aa | bAc | dc | bda
    A → d