Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 69 views

    LALR Parser For A Grammar: Compiler Design

    Uploaded by

    Nameet Jain
    The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

    Copyright:

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

    LALR Parser For A Grammar: Compiler Design

    Uploaded by

    Nameet Jain
    69 views8 pages
    The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

    Original Description:

    Original Title

    Compiler Design

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

    Copyright:

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

    LALR Parser For A Grammar: Compiler Design

    Uploaded by

    Nameet Jain
    The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

    Copyright:

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

    LALR parser for a Grammar

    Compiler Design

    Submitted By:
    Nameet Kumar Jain (2K18/CO/221)
    Pranjal Choudhary (2K18/CO/253)
    Submitted to :
    Geetanjali Garg Maam
    Grammar & Augmented Grammar
    Grammar Augmented Grammar
    S -> N S’ -> S
    S -> N
    N -> V = E
    N -> V = E
    N -> E
    N -> E
    E -> V
    E -> V
    V -> x V -> x
    V -> * E V -> * E

    The purpose of this new starting production is to indicate to the parser when it should
    stop parsing and announce acceptance of input.
    Need of Canonical Collection of LR(1) Items

    LALR refers to the lookahead LR. To construct the LALR (1) parsing table, we
    use the canonical collection of LR (1) items. In the LALR (1) parsing, the LR (1)
    items which have same productions but different look ahead are combined to
    form a single set of items.
    Canonical collection of Lr(1) items
    LR(1) Table Construction

    ○ The LR(1) table construction algorithm uses LR(1) items to represent valid
    configurations of an LR(1) parser
    ○ An LR(1) item is a pair [P, a], where P is a production A→β with a • at some
    position in the rhs and a is a lookahead word (or EOF).
    ○ The • in an item indicates the position of the top of the stack.
    ○ [A→•βγ,a] means that the input seen so far is consistent with the use of A →βγ
    immediately after the symbol on top of the stack.
    ○ [A →β•γ,a] means that the input seen so far is consistent with A →βγ at this point
    in the parse, and that the parser has already recognized β.
    ○ [A →βγ•,a] means that the parser has seen βγ, and that a lookahead symbol of a is
    consistent with reducing to A
    LR(1) Table
    LR table

    Stat ACTION GOTO


    e = x * $ S' S N E V
    0 s5 s6 1 2 4 3

    1 accept

    2 r1

    3 s7 r4

    4 r3

    5 r5 r5

    6 s5 s6 8 9

    7 s5 s6 10 9

    8 r6 r6

    9 r4 r4

    10 r2
    STACK Table of Input
    Table
    Step Stack Input Action
    1 0 x=*x$ s5
    2 0 x 5 =*x$ r5
    3 0 V =*x$ 3
    4 0 V 3 =*x$ s7
    5 0 V 3 = 7 *x$ s6
    6 0 V 3 = 7 * 6 x$ s5
    7 0 V 3 = 7 * 6 x 5 $ r5
    8 0 V 3 = 7 * 6 V $ 9
    9 0 V 3 = 7 * 6 V 9 $ r4
    10 0 V 3 = 7 * 6 E $ 8
    11 0 V 3 = 7 * 6 E 8 $ r6
    12 0 V 3 = 7 V $ 9
    13 0 V 3 = 7 V 9 $ r4
    14 0 V 3 = 7 E $ 10
    15 0 V 3 = 7 E 10 $ r2
    16 0 N $ 2
    17 0 N 2 $ r1
    18 0 S $ 1
    19 0 S 1 $ accept
    Parse Tree

    A parse tree is an ordered, rooted tree


    that represents the syntactic structure of
    a string according to some context-free
    grammar.
    ● All leaf nodes have to be terminals.
    ● All interior nodes have to be
    non-terminals.
    ● In-order traversal gives original input
    string.

    You might also like