Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Module-3 1

    Uploaded by

    AMAL KRISHNA A P
    This document discusses bottom-up parsing techniques including shift-reduce parsing, operator precedence parsing, and LR parsing. It describes the concepts of handles, handle pruning, shift and reduce actions, and precedence relations as they relate to bottom-up parsing.

    Copyright:

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

    Module-3 1

    Uploaded by

    AMAL KRISHNA A P
    6 views25 pages
    This document discusses bottom-up parsing techniques including shift-reduce parsing, operator precedence parsing, and LR parsing. It describes the concepts of handles, handle pruning, shift and reduce actions, and precedence relations as they relate to bottom-up parsing.

    Original Description:

    compiler design s6 ktu

    Original Title

    module-3.1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses bottom-up parsing techniques including shift-reduce parsing, operator precedence parsing, and LR parsing. It describes the concepts of handles, handle pruning, shift and reduce actions, and precedence relations as they relate to bottom-up parsing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    6 views25 pages

    Module-3 1

    Uploaded by

    AMAL KRISHNA A P
    This document discusses bottom-up parsing techniques including shift-reduce parsing, operator precedence parsing, and LR parsing. It describes the concepts of handles, handle pruning, shift and reduce actions, and precedence relations as they relate to bottom-up parsing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 25

    MODULE 3

    BOTTOM – UP PARSING

    1
    Module 3
    Bottom-up Parsing
    •Handle Pruning.
    •Shift Reduce parsing.
    •Operator precedence parsing (Concept only).
    •LR parsing –
    – Constructing SLR, LALR and canonical LR parsing tables

    2
    BOTTOM-UP PARSING
    • Bottom-up parsing starts from the leaf nodes of a tree and
    works in upward direction till it reaches the root node.

    • Here, we start from a sentence and then apply production rules


    in reverse manner in order to reach the start symbol.

    3
    4
    SHIFT-REDUCE PARSER

    5
    SHIFT-REDUCE PARSER
    • Bottom-up parsing approach
    – Shift reduce parsing attempts to construct a parse tree for an
    input string beginning at the leaves (bottom) and working up
    towards the root (top).
    – At each reduction step parser searches for substrings of the
    working string that match the right side of some production.
    – When it finds such a substring, it reduces it, i.e., substitutes the
    left side non-terminal for the matching right side. The goal is to
    reduce all the way up to the start symbol and report a successful
    parse

    6
    Accept

    7
    Actions in SRP
    • Shift
    • Reduce
    • Accept
    • Error

    8
    Handle Pruning
    • Handle
    – A handle of a string is a substring that matches the right side of a production,
    and whose reduction to the nonterminal on the left side of the production
    represents one step along the reverse of a rightmost derivation.
    • Handle Pruning
    – The process of discovering a handle and reducing it to appropriate LHS is
    called handle pruning.
    – Right most derivation in reverse can be obtained by handle pruning.

    9
    10
    • Shift/reduce conflict

    11
    • Reduce/Reduce conflict

    12
    • Reduce/reduce conflict

    13
    OPERATOR PRECEDENCE
    PARSER

    14
    Operator-Precedence Parser
    • Bottom-up parser

    • In an operator grammar, no production rule can


    have:
    – ε at the right side
    – two adjacent non-terminals at the right side.
    E AaB
    • Ex: E AB
    A a
    A ε
    B b
    B b
    E EOE
    E id E E+E | E-E | E*E | E/E | id
    O +|*|/|-
    15
    Precedence Relations
    • In operator-precedence parsing, we define three
    precedence relations between certain pairs of
    terminals.
    a <. b b has higher precedence than a
    a =· b b has same precedence as a
    a .> b b has lower precedence than a

    16
    Precedence Table
    Consider the grammar:
    Input String:
    E → E+E
    E → E*E id + id * id
    E → id

    The operator-precedence table for this grammar:

    id + * $
    . . .
    id > > >
    + <. .
    > <. .
    >
    * <. .
    > .
    > .
    >
    $ <. <. <.

    17
    • The intention of the precedence relations is to find
    the handle :
    <. with marking the left end,
    =· appearing in the interior of the handle, and
    .
    > marking the right hand.

    • Input string id + id * id with the precedence


    relations inserted will be:
    $ <. id .> + <. id .> * <. id .> $

    18
    To Find The Handles
    1. Scan the string from left end until the first .> is encountered.
    2. Then scan backwards (to the left) over any =· until a <. is
    encountered.
    3. The handle contains everything to left of the first .> and to
    the right of the <. is encountered.

    In the above example:


    $ <. id .> + <. id .> * <. id .> $ E → id $ id + id * id $
    $ <. + <. id .> * <. id .> $ E → id $ E + id * id $
    $ <. + <. * <. id .> $ E → id $ E + E * id $
    . . .
    $< +< * >$ E → E*E $ E + E * .E $
    $ <. + .> $ E → E+E $E+E$
    $$ $E$
    19
    OPP Algorithm

    PUSH

    20
    Operator-Precedence Parsing Algorithm
    • Input: Input string w and a table of precedence
    relations
    • Output: If w is well formed, a parse tree otherwise
    an error indication

    Initialize: The stack contains $ and input buffer the


    string w$

    21
    Algorithm
    set ip to point to the first symbol of w$ ;
    OPP LE PUSH
    repeat forever
    if ( $ is on top of the stack and ip points to $ ) then return // Successful Completion

    else
    {
    let a be the topmost terminal symbol on the stack;
    let b be the symbol pointed to by ip;

    if ( a <. b or a =· b ) then //SHIFT


    {
    push b onto the stack;
    advance ip to the next input symbol;
    }
    else if ( a .> b ) then // REDUCE PUSH
    {
    repeat
    pop stack
    until ( the top of stack terminal is related by <. to the terminal most recently popped );
    }
    else error();
    }
    22
    Operator-Precedence Parsing Algorithm --
    Example
    Stack Input Action
    $ id+id*id$ $ <. id shift
    $id +id*id$ id .> + reduce E → id ($ E + id * id $)
    $ +id*id$ $ < . + shift
    $+ id*id$ + <. id shift
    $+id *id$ id .> * reduce E → id ($ E + E * id$)
    $+ *id$ + <. * shift
    $+* id$ * <. id shift
    $+*id $ id .> $ reduce E → id ($ E + E *E $)
    $+* $ * .> $ reduce E → E*E ($ E + E $)
    $+ $ + .> $ reduce E → E+E ($ E $)
    $ $ accept

    23
    Operator Precedence Parsing
    • Advantages:
    – simple
    – powerful enough for expressions in programming
    languages
    – No problem even if grammar is ambiguous

    • Disadvantages:
    – It cannot handle the unary minus
    – Applicable only for small class of grammars.(operator
    grammar)
    24
    25

    You might also like