Compiler Construction Flashcards
Importance of Studying Compilers
- Language design
- Bridging the gap between HLL and LLL
- Contributing to Language Development
- Code Optimization
Code generation Phase
The code generation phase in a compiler plays a crucial role in translating the intermediate representation of a program into target machine code or assembly code. This phase involves transforming the abstract representation of the program into executable instructions that can run on a specific hardware platform. Here are the key functions of the code generation
1. Translating Highlevel constructs
2. Instruction selection
3. Memory allocation
4. Control Flow management
5. Code Emission
6 Register Allocation
7.
Phases of a Compiler
- Lexical Analysis: Analyzing the code and breaking it down into tokens( identifiers,Assignment operator, identifier, punctuation symbol, etc)
- Syntax Analysis: checking wether the tokens generated are consistent with the grammar of the language
- Semantics Analyser: checking the meaning of the syntax
- Intermediate code generator
- Code Optimizer: further optimization of the code(rewriting the code)
- Code Generation: Code converted to target architecture
Syntactic vs semantic Error
Occurs when the code generated violates the rules of the particular Language
Semantic error occurs when the syntax is correct but does not perform the intended logic or operation
explain the two major tasks performed by compiler.
1. Parsing:
- Lexical Analysis (Scanning): The first task of a compiler is to perform lexical analysis or scanning. It involves breaking down the source code into individual tokens or lexemes. Lexemes are the smallest units of a program, such as keywords, identifiers, operators, and literals. The scanner reads the source code character by character and identifies these tokens.
- Syntax Analysis (Parsing): Once the source code is tokenized, the compiler performs syntax analysis or parsing. This phase checks whether the sequence and arrangement of tokens adhere to the grammar rules of the programming language. It builds a hierarchical structure called the Abstract Syntax Tree (AST) to represent the program’s syntactic structure. If there are syntax errors (syntactic errors), the compiler reports them to the programmer.
2. Code Generation:
Intermediate Code Generation (Optional): In some compilers, an intermediate code generation phase is employed to create an intermediate representation of the program. This intermediate code is a platform-independent and language-independent representation that simplifies subsequent optimization and code generation stages.
**- Optimization **(Optional): Many compilers include an optimization phase to improve the efficiency and performance of the generated code. This phase applies various optimization techniques to the intermediate code or directly to the AST to eliminate redundant operations, reduce memory usage, and enhance execution speed.
- Code Generation: The final major task of a compiler is code generation. This phase translates the validated source code or intermediate code into machine code specific to the target computer architecture. The generated machine code can be in the form of assembly language or binary code that can be executed directly by the CPU. The
Parsers error recovery strategies
error recovery strategies used by parsers to handle errors in code:
Panic Mode (Synchronization):
The parser skips input tokens until it finds a synchronization point, often indicated by keywords or punctuation.
Advantages: Simple and prevents cascading errors.
Disadvantages: May skip multiple errors before recovery, imprecise error reporting.
Phrase-Level Recovery (Local Correction):
The parser attempts to fix immediate syntax errors by replacing or deleting tokens.
Advantages: Focuses on correcting individual errors, potentially more accurate error messages.
Disadvantages: Limited to certain error types and doesn’t address root causes.
Global Correction:
The parser performs more extensive code transformations to make the entire input conform to the grammar.
Advantages: Handles complex errors, provides better error messages.
Disadvantages: Requires complex algorithms, may not always succeed.
Error Production (Error Symbols):
Parsers use specially defined error symbols to represent errors in the parse tree.
Advantages: Allows precise detection of multiple errors, detailed error information.
Disadvantages: Requires modifying the grammar and can lead to ambiguity.
Compiler vs Interpreter
Compiler:
Definition: A compiler is a software tool that translates the entire high-level source code into machine code or an equivalent form before execution. It generates a standalone executable file.
Advantage
1. Ready to run
2. Often faster
3. Source Code is private
Examples: GCC (GNU Compiler Collection) for C/C++, Rustc for Rust, and Clang for C/C++.
Interpreter:
An interpreter is a software tool that translates and executes high-level source code line by line or statement by statement, without generating a separate executable file.
Advantage
1. Easy to debug
2. Cross platform
Disadvantage
1. Slower
2. Source Code is public
3. Interpreter is required
Examples: Python interpreter for Python, Node.js for JavaScript, and Ruby interpreter for Ruby
What are the goals of the Programming Languages Analysis?
- Language Understanding and Specification
- Language Design and Improvement
- Compiler and Interpreter DevelopmentLanguage Comparison and Selection
- Language Comparison and Selection
Regular Expression
It is a sequence of characters that defines a search pattern, allowing you to match, search for, and manipulate strings based on specific patterns.
Context-free grammar
a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context.
Deterministic finite Automata
is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string
Non-Deterministic finite Automata
(NFA) is a type of finite state machine with inputs, and its state transitions may not be uniquely determined by the input at all times
4a
Intermediate Representation (IR):
Intermediate representation is an abstract, high-level representation of a program that is used within the compiler or interpreter during various phases of compilation or interpretation.
Register Allocation:
Register allocation is a compiler optimization technique that assigns variables and intermediate values to processor registers for efficient execution.
Assembly and Linking:
Assembly is the process of translating low-level assembly language code, which consists of human-readable mnemonics and operands, into machine code instructions that can be executed directly by a computer’s CPU.
Two broad functions of a compiler
Analysis
Synthesis
funtions of optimizer in a compiler
- Constant Folding
- Dead Code Elimination
- Loop Optimization
- Control flow optimization
- Instructon Scheduling
