Compiler Design

Core Concepts

Core Concepts

1. The Phases of a Compiler The compilation process is typically broken down into several distinct phases.

• Lexical Analysis (Scanning): The first phase. The source code is read as a stream of characters and grouped into meaningful sequences called lexemes. For each lexeme, the scanner produces a token. For example, the statement a = b + 5; might be broken into tokens for 'a', '=', 'b', '+', '5', and ';'.
• Syntax Analysis (Parsing): The parser takes the stream of tokens from the lexical analyzer and verifies that it conforms to the grammar of the source language. It builds a tree-like representation of the program, often an Abstract Syntax Tree (AST), which represents the grammatical structure.
• Semantic Analysis: This phase checks the AST for semantic consistency with the language definition. It performs type checking (e.g., you can't add a string to an integer without conversion), ensures variables are declared before use, etc.
• Intermediate Code Generation: After semantic analysis, the compiler generates a machine-independent intermediate representation of the source code. This makes it easier to translate the source program into different target machine codes.
• Code Optimization: This phase attempts to improve the intermediate code to make it run faster and/or take up less space. This can involve rearranging code, removing unnecessary instructions, etc.
• Code Generation: The final phase. The optimized intermediate code is translated into the target language, which is typically machine code or assembly language for a specific processor.

2. Key Tools and Concepts

• Formal Grammars: Used to formally describe the syntax of a programming language. Context-Free Grammars (CFGs) are commonly used.
• Parsing Techniques:
  • Top-Down Parsing (e.g., LL parsers): Starts building the parse tree from the root (start symbol) and works down to the leaves (tokens).
  • Bottom-Up Parsing (e.g., LR parsers): Starts from the leaves (tokens) and works up to the root.
• Symbol Table: A data structure used by the compiler to store information about identifiers (like variable names, function names) in the source code, such as their type, scope, and memory location.

3. Interpreters vs. Compilers

• Compiler: Translates the entire program into machine code before execution. The resulting executable is fast.
• Interpreter: Reads and executes the source code line by line. It's generally slower but offers more flexibility and easier debugging. (e.g., classic Python).
• Hybrid (JIT - Just-In-Time Compilation): Many modern languages (like Java and modern Python implementations) use a hybrid approach, where code is first compiled to an intermediate bytecode, which is then interpreted or compiled to native machine code at runtime for better performance.

Examples & Use Cases

Examples & Use Cases

Phases for the statement position = initial + rate * 60

1. Lexical Analysis:

   • Tokens: id1, =, id2, +, id3, *, 60
   • The symbol table is updated with entries for position, initial, and rate.

2. Syntax Analysis (Parsing):

   • An AST is created, with = as the root. The left child is id1 (position). The right child is a '+' node. The '+' node's children are id2 (initial) and a '' node. The '' node's children are id3 (rate) and the number 60.

3. Semantic Analysis:

   • Checks that position, initial, and rate are all numeric types. Converts the integer 60 to a floating-point number if necessary.

4. Intermediate Code Generation:

   • Generates three-address code:

     t1 = int_to_float(60)
     t2 = id3 * t1
     t3 = id2 + t2
     id1 = t3
     

5. Code Optimization:

   • Might pre-calculate the value if rate was a constant. For this example, it could optimize by combining steps:

     t1 = id3 * 60.0
     id1 = id2 + t1
     

6. Code Generation:

   • Translates the optimized intermediate code into assembly language for a target machine.

     MOV R1, id3
     MUL R1, 60.0
     MOV R2, id2
     ADD R2, R1
     MOV id1, R2

Practice Questions

Practice Questions

1. MCQ: Which phase of the compiler is responsible for checking type compatibility? A) Lexical Analysis B) Syntax Analysis C) Semantic Analysis D) Code Generation

2. Short Answer: What is the main difference between a compiler and an interpreter?

3. Task: For the code statement if (x > 10) y = 1;, list the tokens that would be generated by the lexical analyzer.

Quick Summary

Quick Summary

• A compiler translates high-level source code into low-level machine code.
• The process involves several phases: Lexical Analysis (tokens), Syntax Analysis (parse tree), Semantic Analysis (type checking), Intermediate Code Generation, Code Optimization, and Code Generation (target code).
• A symbol table is used throughout compilation to keep track of identifiers.
• Interpreters execute code line by line, offering more flexibility but typically lower performance than compiled code.