Kbckbc's Blog - Bravo my life!

Overview of Compilation

1. Introduction
2. Why study compiler Construction?
3. The Fundamental Principles of Compilation
   1. The compiler must preserve the meaning of the program being compiled
   2. The compiler must improve the input program in some discernible way
4. Compiler Structure
   1. Front End
      1. concerned with understanding the source program and recording the result of its analysis into IR form.
   2. Optimizer
      1. focuses on improving the IR form.
   3. Back end
      1. map the transformed IR program onto the bounded resources of the target machine in a way that leads to efficient use of those resources.
5. High-Level View of translation
   1. Understanding the Input
      1. This job falls to the compiler's front end.
      2. It involves both form, or syntax and meaning, or semantics.
      3. Checking syntax
         1. the compiler must compare the program's structure against a definition for the language.
         2. sequence of checking syntax
            1. establish that each word exists in English with a dictionary lookup.
            2. each word is replaced by its syntactic category to create a somewhat more abstract representation of the sentence.
            3. try to fit this sequence of abstracted words into the rules for an programming grammar.
         3. Scanning & Parsing
            1. Scanning
               1. the process of discovering words in a string of characters and classifying them according to their parts of speech.
            2. Parsing
               1. discovering whether a stream of classified words has a derivation in some set of grammatical rule.
      4. Checking meaning
         1. Semantic analysis (Context sensitive analysis)
            1. the compiler must ensure that variable names are used in a fashion consistent with their declarations
            2. A compiler's front end may contain a separate pass that performs semantics analysis, or that analysis may be folded into the parser
   2. Creating and Maintaining the Run-Time Environment.
      1. to handle a complete programming language, the compiler must create and support a variety of abstractions.
      2. designing and implementing a compiler involves the construction of a set of mechanisms that will create and maintain the necessary abstractions at runtime.
   3. Improving the Code
      1. Code optimization
         1. analyzing code to discover fact from context and using that knowledge to improve the code.
         2. two distinct activities
            1. analyzing the code to understand its run-time behavior
               1. Dataflow analysis
               2. Dependence analysis
            2. transforming the code to capitalize on knowledge derived during analysis.
   4. Creating the Output Program
      1. Instruction Selection
         1. The code generator selects a sequence of machine instructions to implement the code being compiled.
      2. Register Allocation
         1. decides which values should reside in the target machine's registers at each point in the code.
         2. (During instruction selection, the compiler deliberately ignored the fact that the target machine has a limited set of registers. Instead, it used an unlimited set of virtual registers and assume that "enough" register existed.
      3. Instruction scheduling
         1. to produce code that executes quickly, the code generator may need to reorder operations to reflect the target machine's specific performance constrains.
      4. Interactions
         1. These all problems interact. :(
6. Desirable Properties of a Compiler.
   1. Speed
      1. the run-time performance of the compiled code is a critical issue.
   2. Space
      1. minimize size of compiled code
   3. Feedback
      1. it must report that fact back to the user.
   4. Debugging
      1. Programmers places a high value on the ability to use a source-level debugger with compiled code.
   5. Compile-Time Efficiency
      1. Compilers are heavily used. In many cases, the compiler user waits for the results, so compilation speed can be an important issue.

Scanning

1. Introduction
1. Scanner
1. takes as input a stream of characters and produces as output a stream of words along their associated syntactic categories.
2. specifying & recognizing pattern.
1. specifying patter : regular expression
2. recognizing patter : finite automata.
2. Parser
1. It consumes scanner's output, in order.
2. It determines whether or not the words form a syntactically correct sentence in the programming language.
3. Semantic analysis(Context-Sensitive analysis)
1. Once the compiler knows that the input is syntactically correct, it subjects that program to deeper analysis.
2. Recognizing Words
1. A formalism for Recognizer
1. Finite Automata(FA)
1. S : Set of state.
2. Sigma : The union of the edge labels in the transition diagram.
3. delta(s,c) : It encodes the transitions of the FA.
4. So : the designated start state
5. Sf : Set of final state
2. Accept or Error
1. Accept
1. process all strings and be in a final state.
2. Error
1. meet a transition which is not defined.
2. process all string and be in a nonfinal state.
2. Recognizing More-Complex Words
   1. Including cycles in FA : simplify the FA significantly.
3. Regular Expression
1. Formalizing the Notation
1. A regular expression is built up from three basic operation.
1. Alternation : R|S
2. Concatenation : RS
3. Closure : R* is just the union of the concatenations of R with itself, zero or more times. R+ is a positive closure, R+ can be rewritten as RR*
2. Precedence
1. Closure has highest precedence, followed by concatenation, followed by alternation.
2. Examples
   1. Examples
   1. Single alphabetic character followed by zero or more alphanumeric characters.
   1. [a...z]([a...z]|[0...9])*
   2. An unsigned integer
   1. 0|[1...9][0...9]*
   3. Real numbers
   1. (0|[1...9][0...9]*)(nil|.[0...9]*)
   4. Quoted character strings
   1. "[^"]*"
   5. Comment
   1. //[^\n]*
   2. {[^}]*}
   2. Cost of operating an FA is proportional to the length of the input string, not to the length or complexity of the regular expression, even though the more complex FA has more state and more transitions.
   3. The cost of operation remains one transition per input characters.
3. Properties of REs
   1. REs are closed under following operations - concatenation, union, closure.
   2. RE == FA