Please enable JavaScript.

Coggle requires JavaScript to display documents.

(Compiler) - Coggle Diagram

- - - - Handle
        
        Definition
        
        A handle of a right sentential form ‘γ’ (γ=αδβ) is a production E→δ and a position in γ where δ can be found and substituted by E to get the previous step in the right most derivation of γ — previous and not “next” because we are doing rightmost derivation in REVERSE
        
        Handle is a substring of a given input string which matches any production rule in the right hand side and reduces the left hand side of production in right most derivation(reverse manner)
        
        Handle can be given as a production or just the RHS of a production
      - Make a syntax tree for each identified construct
      - Types
        
        Bottom Up Parsing
        
        Shiftreduce parsing
        
        Types
        
        Operator Precedence Parsing
        
        Operator Grammar
        
        5 more items...
        
        There should not be any ε as an RHS
        
        Disadvantages
        
        3 more items...
        
        Operator Precedence Parsing
        
        3 more items...
        
        LR(k) parsers
        
        9 more items...
        
        Viable prefix
        
        3 more items...
        
        Types
        
        5 more items...
        
        Actions
        
        Shift
        
        Accept
        
        Error
        
        Reduce
        
        Data Structures
        
        Input Buffer
        
        Stack
        
        Conflicts
        
        Shift-Reduce Conflict
        
        A Shift/Reduce conflict occurs if both shift and reduce possibilities are present
        
        Reduce-Reduce Conflict
        
        A reduce/reduce conflict occurs if there are two or more rules that apply to the same sequence of input. This usually indicates a serious error in the grammar.
        
        In general, bottomup parsing algorithms are more powerful than topdown methods,but not surprisingly, the constructions required are also more complex
        
        CYK Algorithm
        
        Top Down Parsing
        
        LL(k) grammars
        
        L
        
        Leftmost Derivation
        
        k
        
        Number of look-ahead symbols
        
        L
        
        Left-to-Right Scan
        
        Most used sub-classes
        
        Simple LL(1)
        
        A → a 1 α 1 | a 2 α 2 | a 3 α 3 | ...
        
        That means, for a particular NT, each alternative rule starts
        with different Terminal symbols
        
        CFG without ε-rules
        
        a i ∈ V T and α i ∈ (V T ∪ V N )*, A ∈ V N
        
        Parsing
        
        2 more items...
        
        LL(1) without ε-rules
        
        We extend the simple LL(1) parser, by removing the restriction that the first symbol on the RHS be in V .t
        
        Such grammars are as much powerful, no more no less, as the Simple LL(1) grammars
        
        Notation
        
        6 more items...
        
        LL(1) Grammar
        without ε-rules
        
        2 more items...
        
        Process
        
        2 more items...
        
        Parsing Function
        
        2 more items...
        
        LL(1) with ε-rules
        
        FIRST(α) set is to be extended to include zero length strings
        
        Nullable Non-Terminals
        
        Notation
        
        2 more items...
        
        LL(1) Grammar
        
        3 more items...
        
        Parsing Function
        
        2 more items...
        
        Recursive-descent parser (RDP)
        
        RDP has no left-recursive rule, either right-recursive or iterative rules (extended BNF) only
        
        The
        extended BNF can be thought of as a set of rules whose RHS are generalized form of regular
        expressions
        
        Parsing Functions
        
        4 more items...
        
        Can be parsed deterministically, i.e. without backtracking, by LL(k) methods
        
        Left Recursion Elimination
      - Analyze the stream of (tokens, value) pairs and find language syntactic constructs, like
        ASSIGNMENT, IF-THEN-ELSE, WHILE, FOR, etc
      - Sentential Form and Sentence
        
        Sentential Form
        
        A sentential form is any string derivable from the start symbol
        
        A sentential form that occurs in the rightmost derivation of some sentence is called right-sentential form
        
        A sentential form that occurs in the leftmost derivation of some sentence is called left-sentential form
        
        Sentence
        
        A sentence is a sentential form consisting only of terminals
      - Reduced Grammars
        
        Redundancies
        
        redundant NT, which does not generate any Terminal string
        
        unreachable NT
        
        redundant rules like A → A
      - Derivations
        
        Right canonical Direct Derivation
        
        if
        
        x right produces y
        
        Rightmost reduction (i.e. derivation in reverse) is used for Bottom-up parsing, while doing left-to-right scan
        
        If A → β is a production in the grammar
        
        ϕ2 ∈ Vt (Terminal Symbols)
        
        ϕ1Aϕ2 => ϕ1βϕ2
        
        Leftmost canonical Direct Derivation
        
        Leftmost derivation corresponds to left-to-right scan for Top-down parsing
      - Most of the programming languages are designed to be context-free languages (CFL)
      - Detect syntax errors while doing the above
      - I/O
        
        Input
        
        Token Stream
        
        Output
        
        Parse Tree
        
        Tree Representation of the derivation is known as derivation tree
        
        All leaf nodes of the parse tree is known as yield of the parse tree
        
        While reading yield from left to right, sentence of the grammar can be generated
    - - Machine Independent
      - Machine Dependent
      - Basic Blocks
        
        Properties
        
        The last statement is a Jump or Conditional Jump
        
        Does not contain any other labels, Jumps or Conditional Jumps
        
        First statement may have a label
        
        We can only enter at the beginning of a basic block and exit at the end
        
        Flow Graphs
        
        The concept of Basic Blocks is used to form what is known as Flow-graphs, wherein they appear as nodes
        
        A flow-graph indicates which block can follow which other blocks
        
        The idea of flow-graphs is useful in machine-independent optimization
        
        Formal Algorithm to Delineate BBs
        
        Find all statements which start a Basic Block
        
        The first statement of the program
        
        Any labelled statement target of a branch
        
        Any statement following a branch
        
        For each statement starting
        a BB, the BB consists of
        
        That statement
        
        All statements, but excluding, the start of the next BB
        
        End of the program
      - Reference and Define Information
        
        For a 4-tuple i: op X Y Z in a BB
        
        BB references X and Y
        
        BB defines Z
      - Data Flow Analysis
        
        Data-flow analysis derives information about the dynamic
        behavior of a program by only examining the static code
        
        Liveness Analysis
        
        A variable is live at a particular point in the program if its value at that point will be used in the future (dead, otherwise).
        
        To compute liveness at a given point, we need to look into the future
        
        CFG
        
        A CFG is a graph whose nodes represent program statements and whose directed edges represent control flow
        
        Flow Graph Terms
        
        A CFG node has out-edges that lead to successor nodes and in-edges that come from predecessor nodes
        
        pred[n] is the set of all predecessors of node n
        
        succ[n] is the set of all successors of node n
        
        Def or
        definition
        
        An assignment of a value to a variable
        
        def[v] = set of CFG nodes that define variable v
        
        def[n] = set of variables that are defined at node n
        
        Use
        
        A read of a variable’s value
        
        use[v] = set of CFG nodes that use variable v
        
        use[n] = set of variables that are used at node n
        
        Liveliness
        
        A variable v is live on a CFG edge if
        
        ∃ a directed path from that edge to a use of v (node in use[v]),
        
        that path does not go through any def of v (no nodes in def[v])
        
        Data-flow
        
        Liveness of variables is a property that flows
        through the edges of the CFG
        
        Direction of Flow
        
        Liveness flows backwards through the CFG,
        because the behavior at future nodes
        determines liveness at a given node
        
        We have liveness on edges
        
        Live-Out
        
        A variable is live-out at a node if it is live on any of that node’s out-edges
        
        Live-In
        
        A variable is live-in at a node if it is live on any of that node’s in-edges
        
        Rules for computing liveness
        
        Generate liveness
        
        If a variable is in use[n], it is live-in at node n
        
        in[n] = use[n]
        
        Push liveness
        across edges:
        
        If a variable is live-in at a node n then it is live-out at all nodes in pred[n]
        
        out[n] = ∪ in[s] s ∈ succ[n]
        
        Push liveness across nodes:
        
        If a variable is live-out at node n and not in def[n] then the variable is also live-in at n
        
        in[n] = out[n] – def[n]
      - Local Optimization
        
        Local Optimization
    - - Usually,
        these tokens are internally denoted by small
        integers, e.g. 257 for NUMBER, 258 for
        IDENTIFIER, 259 for OPERATOR, etc
      - Analyze individual character sequences
        and find language tokens, like NUMBER,
        IDENTIFIER, OPERATOR, etc
      - Lexical tokens are generally defined as
        regular expressions (RE), for example:
        NUMBER = [+|-]d*[.]d+
      - Send a stream of pairs (token-type, value) for
        each language construct, to the Parser
      - Usually based on a finite-state machine
        (FSM) model
      - Lexemes
      - Problems
        
        Count Tokens
        
        Match rows (I/O) of lex phase
        
        Check if lex error is generated
    - - Building a Parse Tree
        
        Generate parse tree in RDP
      - Notation
        
        Polish Notation
        
        Prefix Notation
        
        The operator is written to the left as a prefix of the operands
        
        Reverse Polish Notation
        
        Postfix Notation
        
        The operator is written to the right as a postfix of the operands
        
        Evaluation of RPN
        
        Extended RPN(ERPN)
        
        We extend it to deal with programming control constructs also so that we can use it to represent Intermediate code
    - - It converts or maps syntax trees for each construct into a sequence of intermediate language statements
      - Syntax-Directed Translation
        
        Such grammars are called attribute grammars
        
        Syntax-directed translation refers to a method of compiler implementation where the source language
        translation is completely driven by the parser
        
        In other words, the parsing process and parse trees are
        used to direct semantic analysis and the translation of the source program
        
        This can be a separate phase of a compiler or we can augment our conventional grammar with information to control the
        semantic analysis and translation
  - - - Activation
        
        Each execution of procedure is referred to as an activation of the procedure
      - Activation Tree
        
        An activation tree shows the way control enters and leaves activations
        
        Each node represents an activation of a procedure
        
        The root shows the activation of the main function
        
        The node for procedure ‘x’ is the parent of node for procedure ‘y’ if and only if the control flows from procedure x to procedure y
      - Activation Record
        
        Information needed by a single execution of a procedure is managed using an activation record or frame
        
        When a procedure is called, an activation record is pushed into the stack and as soon as the control returns to the caller function the activation record is popped
        
        Contains
        
        Temporary values: stores the values that arise in the evaluation of an expression
        
        Local variables: hold the data that is local to the execution of the procedure.
        
        Machine status: holds the information about status of machine just before the function call.
        
        Access link (optional): refers to non-local data held in other activation records
        
        Control link (optional): points to activation record of caller.
        
        Return value: used by the called procedure to return a value to calling procedure
        
        Actual parameters
    - - Subdivisions
        
        Target code
        
        Static data objects
        
        Dynamic data objects
        
        Automatic data objects
    - - Call by Value
      - Call by Reference
      - Call by Copy Restore
      - Call by Name
        
        Parameters are replaced as string.
        
        Arguments in the parameter expression may be defined by the called function.
      - Call by Result
  - - - Phases
        
        Lexical Analysis
        
        Pre-Processing
        
        Semantic Analysis
        
        Syntax Analysis
      - Has error detection
    - - Phases
        
        Code Optimization
        
        Target Code Generation
        
        Intermediate Code Generation
      - Does not have error detection