Please enable JavaScript.

Coggle requires JavaScript to display documents.

Compiler Construction - Coggle Diagram

- - - - Function Inlining, Constant Folding & Propagation, Common Subexpression Elimination, Lifting Loop-Invariant Code, Array Bounds Check Elimination, Null Check Elimination
  - - - Blocks, with dominators
      - Locals in every block
      - Static single assignment (SSA)
        
        Multiple variable with same name are clashed together with Phi functions
    - - Create a CFG, detect loops, remove unreachable blocks, compute immediate dominator for each basic block, convert JVM to HIR, eliminate redundant phi functions.
  - - - degree > R heuristic
      - Liveness intervals of virtual registers
        
        Graph with alive virtual registers as nodes and edges between registers alive at the same time.
- - - - Terminal and non-terminal symbols, production rule and starting symbol
        
        Backus-Naur Form
      - Derivations
        
        Left-most derivation: production rule applied on the left-most non-terminal symbol. Right-most derivation: opposite.
      - Ambiguity
        
        A sentence s is ambiguous if there is at least another set of production rules that lead to that sentence.
        
        An ambiguous grammar is a grammar that has at least one ambiguous sentence
    - - Goal oriented: substitute every non-terminal parsing goal with a sequence of sub-goals
        
        Predictive: next token tells what rule to apply
        
        LL(1)
        
        LL(1) makes the stack explicit
        
        Left-to-right, left-most derivation, 1 token at a time
        
        Token n is observed, symbol t is popped from the stack
        
        If t is terminal, n is consumed
        
        If t!=n, error
        
        If t is non-terminal, n is used to choose the next production rule (whose RHS symbols are pushed on the stack)
        
        If the stack is empty, the parsing is completed.
        
        Table driven (non-terminals, terminals and production rules)
        
        Not all context-free grammars are LL(1). For example, a class of non-LL(1) grammars are those having rules with left recursion.
        
        Recursive descent
        
        Uses the program stack to nest parsing goals
  - - - Maps names (as strings) to the things they name
    - - JCompilationUnitContext
      - ClassContext
      - MethodContext
      - LocalContext
    - - surroundingContext
      - classContext
      - compilationUnitContext
      - IDefns
        
        TypeNameDefn or LocalVariableDefn
  - - - A regular expression describes a "matching pattern", and defines a language L(r) of strings over an alphabet
        
        N-FSA
        
        Constructed with the Thompson construction, it is inefficient and needs backtracking. Makes use of epsilon moves.
        
        Minimal FSA
        
        Constructed partitioning the states, first in final and non-final states. Goal: for all states in each block, each input symbol leads to a same target block. Perfect.
        
        D-FSA
        
        Constructed with the powerset
        (or subset) construction procedure, based on the epsilon-closure. It groups states reachable with the epsilon move. It is too big.
    - - Based on RegEx and lexical states