Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    SLR Parsing Techniques: Submitted By: Abhijeet Mohapatra 04CS1019

    Uploaded by

    arunkumar_pselvam2556
    This document discusses SLR parsing techniques. SLR parsing uses LR(0) parsing tables but only allows reductions if the next input symbol is in the follow set of the non-terminal being reduced. It describes constructing SLR parsing tables from a grammar by starting with the initial item set and taking closures and gotos to generate all item sets. The parsing table is filled using the item sets, with shift actions for terminals and reduce actions if a dot is at the end of the right side or accept if the dot is at the end of S'.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    SLR Parsing Techniques: Submitted By: Abhijeet Mohapatra 04CS1019

    Uploaded by

    arunkumar_pselvam2556
    15 views16 pages
    This document discusses SLR parsing techniques. SLR parsing uses LR(0) parsing tables but only allows reductions if the next input symbol is in the follow set of the non-terminal being reduced. It describes constructing SLR parsing tables from a grammar by starting with the initial item set and taking closures and gotos to generate all item sets. The parsing table is filled using the item sets, with shift actions for terminals and reduce actions if a dot is at the end of the right side or accept if the dot is at the end of S'.

    Original Description:

    Simple left to right parsing technique

    Original Title

    Slr 1019

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses SLR parsing techniques. SLR parsing uses LR(0) parsing tables but only allows reductions if the next input symbol is in the follow set of the non-terminal being reduced. It describes constructing SLR parsing tables from a grammar by starting with the initial item set and taking closures and gotos to generate all item sets. The parsing table is filled using the item sets, with shift actions for terminals and reduce actions if a dot is at the end of the right side or accept if the dot is at the end of S'.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    15 views16 pages

    SLR Parsing Techniques: Submitted By: Abhijeet Mohapatra 04CS1019

    Uploaded by

    arunkumar_pselvam2556
    This document discusses SLR parsing techniques. SLR parsing uses LR(0) parsing tables but only allows reductions if the next input symbol is in the follow set of the non-terminal being reduced. It describes constructing SLR parsing tables from a grammar by starting with the initial item set and taking closures and gotos to generate all item sets. The parsing table is filled using the item sets, with shift actions for terminals and reduce actions if a dot is at the end of the right side or accept if the dot is at the end of S'.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 16

    SLR PARSING

    TECHNIQUES
    Submitted By:
    Abhijeet Mohapatra
    04CS1019.
    A Simple LR parser or SLR parser is an LR
    parser for which the parsing tables are
    generated as for an LR(0) parser except that it
    only performs a reduction with a grammar rule
    A w if the next symbol on the input stream
    is in the follow set of A
    CONSTRUCTION OF SLR
    PARSING TABLES
    INPUT: Grammar G with production rules.

    CENTRAL IDEA
    To construct from the input grammar, a DFA
    to recognize viable prefixes. This is done by
    grouping items into sets which can be
    visualized as subset construction from the
    states of a NFA recognizing the viable
    prefixes.
    Item: An LR (0) item or simply, an item of a
    grammar G is a production of G with a dot . at
    some position of the right side. For example, the
    production A XYZ yields four items,
    A .XYZ
    A X.YZ
    A XY.Z
    A XYZ.
    A production rule of the form A yields only
    one item A . . Intuitively, an item shows how
    much of a production we have seen till the current
    point in the parsing procedure.
    Augmented Grammar G: This equals G
    {S S} where S is the start state of G. The
    start state of G = S. This is done to signal to
    the parser when the parsing should stop to
    announce acceptance of input.

    Closure Operation: If I[] is a set of items for
    a grammar G,
    closure(I) = I {B . | (A .B
    closure(I)) ((B ) grammar G}
    Goto Operation: For a set of items I, and
    grammar symbol X,

    goto(I, X) = { Closure (all items
    containing A X.) such that A .X
    is in I}
    = set of items that are valid
    for the viable prefix X, where I is valid
    for some viable prefix .
    Kernel and Non-Kernel items: Kernel items
    include the set of items that do not have the dot
    at leftmost end, along with S .S
    Non-kernel items are the items which have the
    dot at leftmost end.
    void items (grammar G){
    set C;
    int i, j, n;
    C = {closure ({[S .S]})};
    do{
    n = 0;
    for (i = 0; i < size(C); i++)
    for (j = 0; G.symbol[j] != 0; j++)
    if (size(goto(C[i],X)) > 0 &&
    !iselement(goto(C[i],X),C) )
    { C = union(C, goto(C[i],X)); n++;}
    } while (n != 0);
    } // size of items in grammar G.
    Example:
    Grammar G:
    S S
    S aABe
    A Abc
    A b
    B d
    Set of items generated:-
    I0 = {[S .S], [S .aABe]}
    I1 = {S S.}
    I2 = {S a.ABe, A .Abc, A .b}
    I3 = {S aA.Be, A A.bc, B .d}
    I4 = {A b.}
    I5 = {S aAB.e}
    I6 = {A Ab.c}
    I7 = {B d.}
    I8 = {S aABe.}
    I9 = {A Abc.}
    The table for parsing action and goto function
    for the given grammar is:-
    Where
    1. rj means reduce by production numbered j,
    2. acc means accept
    3. si means shift and stack state i.
    4. blank means error.
    GOTO GRAPH
    Transition Rules:
    If there is a transition from,
    A-> . X to A-> X .
    then, the transition in the GOTO Graph is labeled X
    If there is a transition
    A-> . B to B-> .
    then, the transition is labeled , and since we take -
    closure of all items, these productions lie in the same
    item as that of A-> . B to A-> B . .
    RULES FOR FILLING THE SLR
    PARSE TABLE
    The Rules for filling the action entries in the table are:
    1.If [ A-> .a ] is in I i and goto ( Ii , a ) = I j, then set action [i
    ,a] to shift j .Here a must be a terminal.
    2. If [A-> .] is in I i, then set action[i , a ] to reduce A ->
    for all a in FOLLOW (A); here A may not be in S.
    3. If [ S-> S.] is in I i , then set action [I, $] to accept.
    If any conflicting actions are generated by the given rules, then
    we say the grammar is not in SLR or LR (0) and we fail to
    produce a parser.
    We then fill the goto entries.
    The goto transitions for the state i are constructed for all the
    non-terminals A using the Rule:
    If goto( I i, A ) = Ij , then goto [i , A ] = j .
    GOTO GRAPH FOR GRAMMAR G

    You might also like