Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    CD Unit 3, 1

    Uploaded by

    Pankaj Kumawat
    This document discusses different types of parsers used in compiler construction. It begins by defining a parser as a compiler component that breaks input into smaller tokens from the lexical analysis phase and produces a parse tree. The main types discussed are top-down parsers that build the tree from the start symbol and bottom-up parsers that build up from the terminals. Specific parser techniques covered include LL(1) parsing using a one-token lookahead, recursive descent, operator precedence, LR parsers, and SLR and LALR variants.

    Copyright:

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

    CD Unit 3, 1

    Uploaded by

    Pankaj Kumawat
    6 views7 pages
    This document discusses different types of parsers used in compiler construction. It begins by defining a parser as a compiler component that breaks input into smaller tokens from the lexical analysis phase and produces a parse tree. The main types discussed are top-down parsers that build the tree from the start symbol and bottom-up parsers that build up from the terminals. Specific parser techniques covered include LL(1) parsing using a one-token lookahead, recursive descent, operator precedence, LR parsers, and SLR and LALR variants.

    Original Title

    cd unit 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 different types of parsers used in compiler construction. It begins by defining a parser as a compiler component that breaks input into smaller tokens from the lexical analysis phase and produces a parse tree. The main types discussed are top-down parsers that build the tree from the start symbol and bottom-up parsers that build up from the terminals. Specific parser techniques covered include LL(1) parsing using a one-token lookahead, recursive descent, operator precedence, LR parsers, and SLR and LALR variants.

    Copyright:

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

    CD Unit 3, 1

    Uploaded by

    Pankaj Kumawat
    This document discusses different types of parsers used in compiler construction. It begins by defining a parser as a compiler component that breaks input into smaller tokens from the lexical analysis phase and produces a parse tree. The main types discussed are top-down parsers that build the tree from the start symbol and bottom-up parsers that build up from the terminals. Specific parser techniques covered include LL(1) parsing using a one-token lookahead, recursive descent, operator precedence, LR parsers, and SLR and LALR variants.

    Copyright:

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

    LEX

    Compiler Construction
    Unit 3 Part-1
    CSE

    By Himanshu Swarnkar
    Engineering College Banswara
    Source Program

    Lexical Analyzer
    Stream of token

    Syntax Analyzer
    Parse Tree

    Semantic Analyzer
    Symbol Table Parse tree
    semantically verified Error Handler
    Manager
    Intermediate
    Code Generator
    Three address Code

    Code
    Optimization

    Code Generator

    Target Program
    Parser
     Parser is a compiler that is used to break the data into smaller elements coming from lexical analysis phase.
     A parser takes input in the form of sequence of tokens and produces output in the form of parse tree.
     Syntax analyzer phase we use the software parser to generate the parse tree
     Following are the parser types:
    Parser

    Top Down Bottom Up Parser


    Parser (BUP)
    (TDP) SR Parser(shift Reduce)

    TDP with Full TDP Without Operator LR Parser


    Backtracking Backtracking Precedence (Scanning from L to R, Reverse
    Parser of Right most derivation)

    Brute force
    Method Recursive Descent Non Recursive LR(0) SLR(1) LNR(1) CLR(1)
    Descent(LL(1))
    Top Down Parsing
     When the parser starts construction the parse tree from the start symbol and then tries to transform the start symbol to the input
    stream, it called top down parts tree. Top Down Parse Tree
     Means Starts from the start symbol and ends on the terminals.
    S
     Note: Top down parser follows left most derivation and if focus on what to use.
     Example Given Grammar G(VTPS),
    Production are S→aABe
    Left Most Derivation
    A →Abc/b e
    S→aABe a B
    B →d A
    →aAbcBe
    String w= abbcde
    →abbcBe
    →abbcde d
    A b c
    S
    Bottom Up Parsing
     Bottom up parsing stars with the input string and tries to construct the parse tree b
    up to the start symbol
     Means Starts from the terminals and ends on the start Symbol
    A B
     Note: Bottom Up parser follows Reverse right most derivation and if focus on
    what to reduce
    Right Most Derivation Bottom Up Parse Tree
    S→aABe
    A
    →aAde
    →aAbcde
    →abbcde
    a b b c d e
    LL(1) Parsing (Non recursive Descent)
     A top-down parser that uses a one-token look ahead is called an LL(1) parser.
     The first L indicates that the input is read from left to right.
     The second L says that it produces a left-to-right derivation.
     And the 1 says that it uses one look ahead token. (Some parsers look ahead at the next 2 tokens, or even more than that)
    Input Buffer

    LL(1) Parser

    LL(1) Parser Table

     We must know two function First() and Flollow() fucntions.


    First Follow
    S→ABCDE
    A →a/ε
    B →b/ε
    C →b
    D →d/ε
    E →e/ε

    You might also like