Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    LR Parsing

    Uploaded by

    Shreyansh Jain
    The document discusses operator precedence parsing and LR parsing. It defines precedence relations between terminals as higher (<.), same (=.), or lower (>.). It presents a sample grammar and its partial operator precedence table. It then walks through an example parse of the input string "id+id*id" using this grammar and table, showing the stack and input at each step. It introduces LR parsing as the most powerful shift-reduce parsing and discusses the basic configuration, actions of shifting and reducing, and use of parsing tables and transition diagrams to determine the next state.

    Copyright:

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

    LR Parsing

    Uploaded by

    Shreyansh Jain
    23 views21 pages
    The document discusses operator precedence parsing and LR parsing. It defines precedence relations between terminals as higher (<.), same (=.), or lower (>.). It presents a sample grammar and its partial operator precedence table. It then walks through an example parse of the input string "id+id*id" using this grammar and table, showing the stack and input at each step. It introduces LR parsing as the most powerful shift-reduce parsing and discusses the basic configuration, actions of shifting and reducing, and use of parsing tables and transition diagrams to determine the next state.

    Original Title

    LR parsing

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses operator precedence parsing and LR parsing. It defines precedence relations between terminals as higher (<.), same (=.), or lower (>.). It presents a sample grammar and its partial operator precedence table. It then walks through an example parse of the input string "id+id*id" using this grammar and table, showing the stack and input at each step. It introduces LR parsing as the most powerful shift-reduce parsing and discusses the basic configuration, actions of shifting and reducing, and use of parsing tables and transition diagrams to determine the next state.

    Copyright:

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

    LR Parsing

    Uploaded by

    Shreyansh Jain
    The document discusses operator precedence parsing and LR parsing. It defines precedence relations between terminals as higher (<.), same (=.), or lower (>.). It presents a sample grammar and its partial operator precedence table. It then walks through an example parse of the input string "id+id*id" using this grammar and table, showing the stack and input at each step. It introduces LR parsing as the most powerful shift-reduce parsing and discusses the basic configuration, actions of shifting and reducing, and use of parsing tables and transition diagrams to determine the next state.

    Copyright:

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

    CS 671 – Spring 2008

    Precedence Relations

    In operator-precedence parsing, we define three


    disjoint precedence relations between certain
    pairs of terminals.

    a <. bb has higher precedence than a


    a =· b b has same precedence as a
    a .> b b has lower precedence than a

    The determination of correct precedence


    relations between terminals are based on the
    traditional notions of associativity and
    precedence of operators. (Unary minus causes a
    problem).
    CS 671 – Spring 2008
    Using Operator -Precedence Relations
    E  E+E | E-E | E*E | E/E | E^E | (E) | -E | id

    The partial operator-precedence id + * $


    table for this grammar id .
    > .
    > .
    >
    + <. .
    > <. .
    >
    * <. .
    > .
    > .
    >
    $ <. < . < .
    Then the input string id+id*id with the precedence
    relations inserted will be:

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


    Handle of a string: Substring that
    matches the RHS of some production
    AND that can be reduced to the non-
    terminal on the LHS
    CS 671 – Spring 2008
    Set ip to point to the first symbol of w$
    Stack=$
    Repeat forever:
    if $==topofstack and ip==$ then accept
    Else { a=topofstack; b=ip;
    if a<.b or a.=.b then push(b);advance ip;
    if a.>b then repeat pop() until the top stack
    terminal is related by <.
    else error

    CS 671 – Spring 2008


    STACK INPUT Remark
    $ id + id * id$ $ <. id
    $ id + id * id$ id >. +
    $ + id * id$ $ <. +
    $+ id * id$ + <. id
    $ + id * id$ id .> *
    $+ * id$ + <. *
    $+* id$ * <. id
    $ id .> $
    $ + * id
    $ * .> $
    $+* + .> $
    $
    $+ $
    $ accept
    $
    A sequence of pops
    corresponds to the
    application of some of
    the productions
    CS 671 – Spring 2008
    LR Parsing

    CS 671 – Spring 2008


    LR Parsers
    • The most powerful shift-reduce parsing (yet efficient) is:

    LR(k) parsing.

    left to right right-most k lookhead


    scanning derivation (if k is omitted  it is 1)

    • LR parsing is attractive because:


    • LR parsing is most general non-backtracking shift-reduce parsing, yet
    it is still efficient.

    • An LR-parser can detect a syntactic error as soon as it is possible to do


    so a left-to-right scan of the input.
    LR Parsing Algorithm
    • A parsing program
    • A parsing table
    • A stack
    • An input tape
    • An output tape
    A Configuration of LR Parsing Algorithm
    • A configuration of a LR parsing is:

    ( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )

    Stack Rest of Input

    • Sm and ai decides the parser action by consulting


    the parsing action table. (Initial Stack contains
    just So )
    LR Actions
    action[sm,a] = shift s
    execute a shift move:
    (s0X1s1X2s2 .. Xmsm, ai ai+1 .. an$)
    shifted current input ai and next state s
    onto stack
    (s0X1s1X2s2 .. Xmsmais, ai+1 .. an$)
    action[sm,a] = reduce a
    execute a reduce move:
    (s0X1s1X2s2 .. Xmsm, ai ai+1 .. an$)
    pop 2r symbols
    Push A and s onto stack
    no change in input
    (s0X1s1X2s2 .. Xm-r sm-r A s, ai ai+1 .. an$)where
    LR Actions
    3. Accept – Parsing successfully completed

    4. Error -- Parser detected an error (an empty


    entry in the action table)
    Transition Diagram for LR Tables
    id * id + id

    In S0 with input symbol


    id, shift the symbol
    onto the stack and enter
    state S5
    id * id + id

    S5 with input symbol *

    Reduce
    using grammar
    production6
    id * id + id

    S5 with input symbol *

    Reduce
    using grammar
    production6
    id * id + id

    T2

    Reduction exposes S0
    and goto of S0 gives
    next state for the
    leading non-terminal, T.
    The next state is S2
    id * id + id
    id * id + id
    id * id + id
    id * id + id

    Reduction exposes S7
    and goto of S7 gives
    next state for the
    leading non-terminal, F.
    The next state is S10
    Pop 6
    elements

    Insert LHS
    (T)

    You might also like