SLR Parsing Table Construction Example

0
608

SLR Parsing Table Construction Example

SLR Parsing Table Construction Example is most important topic in Computer Science, so In this article you will learn easily SLR Parsing Table Construction Example.

The crux of SLR parsing is to determine the steps to be taken for ACTION[i,a] for the
various values of i and a, where state i is constructed from Ii and a is a terminal.

SLR Parsing Table Construction Example
SLR Parsing Table Construction Example
  1. If [A → α.a.β] is in Ii and GOTO (Ii , A) = Ij then ACTION [i , a] is “shift j”.
    This implies that the state j should be pushed onto the state stack and the
    input pointer must move ahead by one character.
  2. If [A → α.] is in Ii and a in FOLLOW (A) then ACTION [i , a] is “reduce A→α”
    for all a in FOLLOW (A). A may not be S’, the start state of the augmented LR
    automaton.
    Here a acts as a watchdog character. If a is in FOLLOW(A), that means that a
    appears after non-terminal A. This ensures that the reduction gives a valid
    move of the rightmost derivation.
  3. If [ S’ → S] is in Ii then ACTION [i , $] should be “accept”
    ACTION [i , a] that does not satisfy any of the above is an “error”.
    Additionally, GOTO (Ii , A) = Ij means that GOTO [ i , A] = j

DEMONSTRATION OF SLR PARSING

The grammar used is the same as the one used consistently before:

  1. E → E + T
  2. E → T
  3. T → T * F
  4. T → F
  5. F → (E)
  6. F → id
    The string to be parsed is id + id * id
    The moves of the LR parser are shown on the next page. For reference:
    FOLLOW(E) = { + , $ }
    FOLLOW(T) = { * , + , $ }
    FOLLOW(F) = { * , + , $}
1

If the right-most column is now traversed upwards, and the productions by which
the reduce steps occur are arranged in that sequence, then that will constitute a
leftmost derivation of the string by this grammar. This highlights the bottom-up
nature of SLR parsing.

THE SLR PARSING TABLE

To understand SLR parsing easily, the SLR parsing table is created using the
principles discussed above in Item I.
The rows of this table are represented by the state numbers and the columns are
divided into two segments – the ACTION function where the columns are
represented by the terminals and the GOTO function where the columns are the
non-terminals.
The SLR parsing table for the previous grammar is shown on the next page, while
the notation for the table is specified here for easy reference.1

  1. Shift i is represented by “si”. (Check the previous notes for the states)
  2. Reduction number j (check Item II for numbering) is represented by “rj”
  3. Accept is represented by “acc”
  4. Error is represented by a blank space in the cell

Using the SLR parsing table, the process of shift-reduce parsing for SLR grammars
can be automated and done easily.

2

THINGS TO NOTE:

  1. CONFLICT FREE NATURE OF SLR
    The above procedure worked for the particular grammar because it is an SLR
    grammar, i.e one that contains no conflicts. An example of a shift/reduce
    conflict is shown below:
    A → B.
    A → B. + C
    If the above two items appear in the same state, then there will be a conflict in
    the case of ACTION [A , +] about whether to shift and move forward in the
    input or reduce by “A → B”.
    Essentially, if each table entry in the parsing table is unique without any
    duplicity, then there are no conflicts and the grammar in question is SLR.
  1. CORRECTNESS OF SLR
    The stack always contains a set of symbols until the input has been matched
    and only the start state remains – therefore a right sentential derivation can
    always be found for the given string, if the table is correctly designed without
    any conflicts. Hence, SLR parsing is correct.
SLR Parsing Table Construction Example

Other Resources:-

Simple LR Parser

Read More:-

LEAVE A REPLY

Please enter your comment!
Please enter your name here