Scribd Logo
Upload

Welcome to Scribd!

  • 89 views

    LL1 ParsingExamples

    Uploaded by

    Sayantan Pal
    The document discusses three examples of LL(1) parsing. It explains the steps to determine if a grammar is LL(1) which includes calculating the first and follow sets, and constructing the parsing table. The examples show applying these steps to various grammars to analyze if they are LL(1) and build their parsing tables.

    Copyright:

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

    LL1 ParsingExamples

    Uploaded by

    Sayantan Pal
    89 views11 pages
    The document discusses three examples of LL(1) parsing. It explains the steps to determine if a grammar is LL(1) which includes calculating the first and follow sets, and constructing the parsing table. The examples show applying these steps to various grammars to analyze if they are LL(1) and build their parsing tables.

    Original Description:

    NIL

    Original Title

    LL1-ParsingExamples

    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 discusses three examples of LL(1) parsing. It explains the steps to determine if a grammar is LL(1) which includes calculating the first and follow sets, and constructing the parsing table. The examples show applying these steps to various grammars to analyze if they are LL(1) and build their parsing tables.

    Copyright:

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

    LL1 ParsingExamples

    Uploaded by

    Sayantan Pal
    The document discusses three examples of LL(1) parsing. It explains the steps to determine if a grammar is LL(1) which includes calculating the first and follow sets, and constructing the parsing table. The examples show applying these steps to various grammars to analyze if they are LL(1) and build their parsing tables.

    Copyright:

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

    LL(1) Parsing

    Example of LL(1) Parser: Example 1


    S  aABb
    Ac|€
    Bd|€
    Step: 1: No left recursion in the grammar, hence no modification
    required.
    Step 2: Calculation of First Set
    First(S) = {a}
    First(A) = {c, €}
    First(B) = {d, €}
    Example of LL(1) Parser
    S  aABb
    Ac|€
    Bd|€
    Step 3: Calculation of Follow Set
    Follow(S) = {$}
    Follow(A) = First(Bb) = First(B) = {d, €)
    Since it contains €, continue FIRST rule.
    First(Bb) = First(B) - € U First (b) = {d, b}
    Follow(A) = {d,b}
    Follow(B)= {b}
    Example of LL(1) Parser
    S  aABb  First(aABb)= a
    A  c | €  First(c)=c and First(€) = € (Use follow)
    B  d | €  First(d)=d and First(€) = € (Use follow)
    Step 4: Parsing Table
    Grammar is LL(1)
    Example String: acdb$ H/w string: adb$
    a b c d $
    S SaABb
    A A€ Ac A€
    B B€ Bd
    Example of LL(1) Parser
    Example String: acdb$
    a b c d $
    S SaABb
    A A€ Ac A€
    B B€ Bd

    Stack Input Action


    $ acdb$ Push S into Stack
    $S acdb$ S
    aABb
    $bBAa acdb$ Pop a
    $bBA cdb$ A
    c
    $bBc cdb$ Pop c
    $bB db$ B
    d
    $bd db$ Pop d
    $b b$ Pop b
    $ $ Accept
    Example of LL(1) Parser: Example 2
    S  AaAb | BbBa
    A€
    B€
    Step: 1: No left recursion in the grammar, hence no modification required.
    Step 2: Calculation of First Set
    First(S) = First(AaAb) U First(BbBa)
    First(AaAb) = First(A) = €
    Since it contains €, continue FIRST rule
    First(AaAb) = First(A) - € U First(aAb) = {a}
    Similarly: First(BbBa) = {b}
    First(S) = {a,b}
    Example of LL(1) Parser: Example 2
    S  AaAb | BbBa
    A€
    B€
    Step 3: Calculation of Follow Set
    Follow(S) = {$}
    Follow(A) = First(aAb) = a Follow(A) = First(b) = {b}
    Follow(A) = {a,b}
    Similarly Follow(B) = {a,b}
    Example of LL(1) Parser: Example 2
    S  AaAb | BbBa
    A€
    B€
    Step 4:Construction of Parsing Table: Grammar is LL(1)
    a b $
    S SAaAb SBbBa
    A A€ A€
    B B€ B€
    Example of LL(1) Parser: Example 3
    S  AB |eDa
    A  ab |c
    B  dC
    C  eC | €
    D  fD | €

    Step: 1: No left recursion in the grammar, hence no modification required.


    Step 2: Calculation of First Set
    First(S) = {a,c,e}
    First(A) = {a,c}
    First(B) = {d}
    First(C) = {e, €}
    First(D) = {f, €}
    Example of LL(1) Parser: Example 3
    S  AB |eDa SeDA
    A  ab |c Follow(D) = First(a) = {a}
    B  dC BdC
    C  eC | € Follow(C) = Follow(B) = {$}
    D  fD | € CeC
    Follow(C) = Follow(C) = {$}
    Step 3: Calculation of Follow Set DfD
    Follow(S) = {$} Follow(D) = Follow(D) = {a}
    SAB
    Follow(A) = First(B) = {d}
    Follow(B) = Follow(S) = {$}
    Example of LL(1) Parser: Example 3
    S  AB |eDa
    A  ab |c
    B  dC
    C  eC | €
    D  fD | €
    Construction of Parsing Table:
    a b c d e f $
    S SAB SAB SeDa
    A Aab Ac
    B BdC
    C CeC C€
    D D€ DfD

    You might also like