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
        
        6 more items...
        
        There should not be any ε as in RHS
        
        Disadvantages
        
        3 more items...
        
        Operator Precedence Parsing
        
        3 more items...
        
        Parsing
        
        3 more items...
        
        Function Table
        
        8 more items...
        
        Conversion
        
        1 more item...
        
        LR(k) parsers
        
        8 more items...
        
        Viable prefix
        
        9 more items...
        
        Types
        
        5 more items...
        
        DFA State Comparison
        
        2 more items...
        
        Number of states relation
        
        1 more item...
        
        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 → a1α1 | a2α2 | a3α3 | ...
        
        That means, for a particular NT, each alternative rule starts
        with different Terminal symbols
        
        CFG without ε-rules
        
        ai ∈ Terminal and αi ∈ (Terminal ∪ Non-Terminal )*, A ∈ Non-Terminal
        
        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 a terminal
        
        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) Table
        
        2 more items...
        
        Time Complexity
        
        1 more item...
        
        5 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 Check
        
        1 more item...
        
        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...
        
        In case of RDP, an explicit stack is not present, rather we use the return-stack normally available as a hidden stack in an HLL like C (or even in most of the modern CPU hardware)
        
        A predictive parser is a recursive descent parser that does not require backtracking
        
        Can be parsed deterministically, i.e. without backtracking, by LL(k) methods
        
        Predictive parsing is possible only for the class of LL(k) grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input
        
        Left Recursion Elimination
        
        Left Factoring
        
        Relation between Left Recursion & Left Factoring
        
        Types
        
        Recursive Descent Parser
        
        Types
        
        Non-Backtracking
        
        1 more item...
        
        Backtracking
      - 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
        
        Comes from lexical analysis phase
        
        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
        
        Count number of blocks
        
        Additional entry and exit blocks have to be counted
        
        Count number of edges
        
        Additional 2 edges for entry and exit are needed
      - 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
        
        Example
        
        Register Allocation
        
        A program contains an unbounded number of variables
        
        Must execute on a machine with a bounded number of registers
        
        Two variables can use the same register if they are never in use at the same time
        
        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
        
        Liveness at nodes
        
        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
        
        Statement
        
        Common Sub-Expression Elimination
        
        Use DAG
        
        Available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed
        
        Constant Propagation
        
        Constant Folding
        
        Dead Code Elimination
        
        Strength Reduction
        
        Loop
        
        Code Motion
        
        Loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program
        
        Loop-invariant code motion (also called hoisting or scalar promotion) is a compiler optimization which performs this movement automatically.
        
        Loop Invariant Computation
        
        Loop Unrolling
        
        Loop Fusion
      - Global 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
        
        Tips
        
        Strings including double quotes is one token
    - - 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
      - Single Static Assignment
        
        Number of variables needed
        
        Total number of source variables + Number of assignments
      - Intermedia Code Types
        
        Tree Form
        
        Syntax Tree
        
        Optimized form of parse tree with non terminal symbols eliminated
        
        Used to represent expression statements
        
        For expression statement operators present at root and operands are present at leaf nodes
        
        Common subexpression is repeatedly evaluated
        
        Order of evaluation should be proper
        
        Directed Acyclic Graph
        
        DAG is a syntax tree in which common sub-expressions are eliminated
        
        Minimization Techiques
        
        If there is a - in the calculation, check if some terms cancel and its just variable substitution
        
        Check if multiple variables store the same calculation and replace with single node
        
        Tree form is only suitable for expression statements
        
        Not suitable for high level language statements
        
        Linear Form
        
        Three Address Code
        
        In TAC every high level language statement is represented using atmost 3 addresses
        
        Codes
        
        Common subexpression is repeatedly evaluated
        
        Optimized code not generated
        
        Notation
        
        Quadruple Notation
        
        Cannot identify temporary and program variables as there is no way to identify just based on name
        
        Triples Notation
        
        No result field
        
        Target variable is implicit
        
        Intermediate variables can be easily known
        
        Indirect Triples
        
        Implemented using linked list
        
        Allows rearrangement
        
        Postfix Code
      - Register Allocation
        
        Write the register slots separately
        
        For each line executed add a new row to the slots
        
        Add a new slot to avoid spilling
        
        Reuse registers
        
        One register maybe assigned multiple variables if they have the same value
        
        If a variable will be never be used again or not be used again till a reassignment then reuse the register for other variable
        
        Reuse for intermediate values as much as possible
    - - 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
  - - - 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
  - - - 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)
        
        An access link from record A points to the record of the closest enclosing block in the program. The chain of access links traces the static structure (think: scopes) of the program.
        
        Refers to non-local data held in other activation records
        
        Control link (optional):
        
        A control link from record A points to the previous record on the stack. The chain of control links traces the dynamic execution of the program.
        
        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 copy-restore is similar to call by reference except that the values of actual parameters are changed when the called function ends, unlike call by reference
      - Call by Name
        
        Parameters are replaced as string.
        
        Arguments in the parameter expression may be defined by the called function.
      - Call by Result
    - - Assembler
        
        The C compiler, compiles the program and translates it to assembly program (low-level language)
        
        An assembler then translates the assembly program into machine code (object)
      - Linker
        
        A linker tool is used to link all the parts of the program together for execution (executable machine code)
      - Loader
        
        A loader loads all of them into memory and then the program is executed
  - - - Types
        
        Synthesized attributes
        
        A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production
        
        Synthesized attributes represent information that is being passed up the parse tree
        
        The attribute can take value only from its children (Variables in the RHS of the production)
        
        Inherited attributes
        
        An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute
        
        The attribute can take value either from its parent or from its siblings (variables in the LHS or RHS of the production)
        
        The sibling maybe both to the left or right
      - S-attributed SDT
        
        If an SDT uses only synthesized attributes, it is called as S-attributed SDT
        
        S-attributed SDTs are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes
        
        Semantic actions are placed in rightmost place of RHS
      - L-attributed SDT
        
        If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT
        
        Attributes in L-attributed SDTs are evaluated by depth-first and left-to-right parsing manner
        
        Semantic actions are placed anywhere in RHS
        
        S attribute is a subset of L attributed
        
        If right sibling attribute is used, it is neither L attributed or S attributed