Constructing Canonical lr parsing Tables Construction of the sets of lr(1) items




Yüklə 16.85 Kb.
tarix27.02.2016
ölçüsü16.85 Kb.
Monday, September 12, 2005

LR Parsers
Constructing Canonical LR Parsing Tables
Construction of the sets of LR(1) items

Input: An augmented grammar G’.

Output: The sets of LR(1) items that are the set of items valid for one or more viable prefixes of G’ .

Method:
function closure(I);

begin

repeat

for each item [A α. Bβ, a] in I,

each production Bγin G',

and each terminal b in FIRST(βa)

such that [B. γ, b] is not in I do

add [B. γ, b] to I

until no more sets of items can be added to I

end

return I

end;
function goto(I, X)

begin

let J be the set of items [AX. β, a] such that

[A X β, a] is in I

return closure(J)

end;
procedure items(G')

begin

C := {closure({S'. S,$})};

repeat

for each set of items I in C and each grammar symbol X

such that goto(I , X) is not empty and not in C do

add goto(I , X) to C

until no more sets of items can be added to C

end;
Consider the following augmented grammar:-

S’ S


S CC

C Cc | d

The initial set of items is:-

I0 : S’  .S , $

S .CC, $

C .Cc, c | d

C .d, c | d

We have next set of items as:-

I1 : S’  S., $

I2 : S  .Cc, $

C  .Cc, $

C  .d, $

I3 : C  c.C, $

C  .c C , c | d

C  .d, $

I4 : C  d. , c | d

I5 : S  CC. , $

I6 : C  c.C, $

C  .c C ,$

C  .d , $

I7 : C  d. , $

I8 : C  c C. , c | d

I9 : C  c C. , $

Construction of the canonical LR parsing table.

Input: An augmented grammar G’.

Output: The canonical LR parsing table functions action and goto for G’

Method :


  1. Construct C={I0,I1………..,In}, the collection of sets of LR(1) items for G’.

  2. State I of the parser is constructed from Ii. The parsing actions for state I are determined as follows :

  1. If [A  α. a β, b] is in Ii, and goto(Ii, a) = Ij, then set action[ i,a] to “shift j.” Here, a is required to be a terminal.

b) If [ A  α., a] is in Ii, A ≠ S’, then set action[ i,a] to “reduce A  α.”

c) If [S’S.,$] is in Ii, then set action[ i ,$] to “accept.”

If a conflict results from above rules, the grammar is said not to be LR(1), and the algorithm is said to be fail.


  1. The goto transition for state i are determined as follows: If goto(Ii , A)= Ij ,then goto[i,A]=j.

  2. All entries not defined by rules(2) and (3) are made “error.”

  3. The initial state of the parser is the one constructed from the set containing item [S’.S, $].

Submitted by:



Neeraj Meena

03CS1028


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə