# Unit 1: Introduction to Compiler Design ## 1.1 Introduction to Compiler * **Compiler:** A program that translates source code written in a high-level programming language into an equivalent program in a low-level language (e.g., machine code or assembly code). * **Key Goal:** To make programs executable by the computer. * **Types of Translators:** * **Compiler:** Translates entire program before execution. * **Interpreter:** Translates and executes program statement by statement. * **Assembler:** Translates assembly code to machine code. ## 1.2 Phases and Passes * **Phases of a Compiler:** A compiler is typically structured into a sequence of phases, each performing a specific task. * **Analysis (Front-end):** Understands the source code. 1. **Lexical Analysis:** Scans the source code and groups characters into meaningful sequences called **tokens**. 2. **Syntax Analysis (Parsing):** Checks if the sequence of tokens conforms to the grammatical rules of the language, creating a **parse tree**. 3. **Semantic Analysis:** Checks for meaning and consistency (e.g., type checking, variable declaration). 4. **Intermediate Code Generation:** Produces an intermediate representation of the source code, independent of the target machine. * **Synthesis (Back-end):** Generates the target code. 5. **Code Optimization:** Improves the intermediate code for faster or smaller execution. 6. **Code Generation:** Translates the optimized intermediate code into the target machine code. * **Symbol Table Management:** A data structure used throughout all phases to store information about identifiers (variables, functions, etc.). * **Error Handling:** Detects and reports errors in the source code at each phase. * **Passes:** A pass is a single traversal of the entire source program (or its intermediate representation). A compiler can be implemented with one or more passes. * **Single-pass compiler:** Processes the entire program in one go. * **Multi-pass compiler:** Requires multiple traversals. **[Figure: Compiler Phases]** This diagram illustrates the sequential flow of the six main phases of a compiler. Understanding this order is crucial for comprehending how source code is transformed and how errors are detected at different stages. ## 1.3 Bootstrapping * **Bootstrapping:** The process of writing a compiler for a language in that same language. * **How it works:** 1. Write a compiler for a simpler language L0 in a more primitive language L1. 2. Use the L0 compiler to compile a compiler for language L1 written in L0. 3. Now you have a compiler for L1 written in L1. * **Exam Importance:** Demonstrates how self-hosting compilers are created. ## 1.4 Finite State Machines and Regular Expressions * **Finite State Machine (FSM) / Finite Automaton (FA):** A mathematical model of computation. * Consists of a finite set of states, an input alphabet, a transition function, a start state, and a set of accept states. * Accepts or rejects sequences of symbols. * **Regular Expressions (RE):** A sequence of characters that defines a search pattern. * Used to describe sets of strings. * **Operators:** * `|` (union/OR): `a|b` matches 'a' or 'b'. * `.` (concatenation): `ab` matches 'a' followed by 'b'. * `*` (Kleene star): `a*` matches zero or more 'a's. * `+` (Kleene plus): `a+` matches one or more 'a's. * `?` (optional): `a?` matches zero or one 'a'. * `()` (grouping). * **Application to Lexical Analysis:** Regular expressions are used to define the patterns for tokens. Finite automata are used to recognize these patterns. * **RE $\rightarrow$ FA:** For every regular expression, there exists an equivalent Finite Automaton that accepts the same language. * **FA $\rightarrow$ RE:** For every Finite Automaton, there exists a regular expression that describes the language accepted by the FA. ## 1.5 Implementation of Lexical Analysers * **Lexical Analyser (Scanner):** The first phase, responsible for reading the source code and producing a stream of tokens. * **Tasks:** * **Tokenization:** Grouping characters into tokens. * **Eliminating Whitespace and Comments:** Often ignored. * **Error Detection:** Identifying lexically incorrect input. * **Implementation Methods:** * **Hand-coded:** Writing scanner logic directly in a programming language. * **Table-driven:** Using transition tables generated from FSMs. * **Using Lexical Analyser Generators (e.g., LEX).** ## 1.6 Lexical Analyser Generator (LEX) * **LEX:** A program that generates a lexical analyser from a specification file. * **Input:** A file containing regular expressions and associated C code actions. * **Output:** A C source file for the lexical analyser. * **Key Features:** * Defines **tokens** using regular expressions. * Associates **actions** (C code) to be executed when a pattern is matched. * Handles **longest match rule** (chooses the longest string matching a pattern). * **Usage:** 1. Write `.l` file (LEX specification). 2. Run `lex lex.l` to generate `lex.yy.c`. 3. Compile `lex.yy.c` along with other source files. ## 1.7 Formal Grammars and Syntax Analysis * **Formal Grammar:** A set of rules that define the syntax of a language. * **Application to Syntax Analysis (Parsing):** Grammars define the structure of valid programs. The parser checks if the token stream conforms to the grammar. * **Types of Grammars:** Chomsky Hierarchy (Type 0, 1, 2, 3). For compilers, primarily context-free grammars (CFG) are used. * **Context-Free Grammar (CFG):** A grammar where each production rule has a single non-terminal on the left-hand side. * **Components:** * **Terminals (T):** Symbols that appear in the language (e.g., keywords, identifiers, operators). * **Non-terminals (N):** Syntactic variables that can be replaced by sequences of terminals and non-terminals. * **Productions (P):** Rules of the form $A \rightarrow \beta$, where $A \in N$ and $\beta \in (N \cup T)^*$. * **Start Symbol (S):** A designated non-terminal from which all strings are derived. * **Derivation:** The process of applying grammar rules to derive strings. * **Parse Tree:** A tree representation of the derivation of a string from the start symbol of a grammar. Internal nodes are non-terminals, leaves are terminals. ## 1.8 BNF Notation * **BNF (Backus-Naur Form):** A common notation for specifying context-free grammars. * Non-terminals are enclosed in angle brackets (e.g., ``). * `::=` means "is defined as". * Terminals are usually written directly. * `|` is used to separate alternatives. * **Example:** ```bnf ::= + | ::= * | ::= ( ) | id ``` ## 1.9 Ambiguity * **Ambiguous Grammar:** A grammar for which there exists at least one string that has more than one distinct parse tree. * **Problem:** Leads to uncertainty in parsing and interpretation. * **Detection:** Difficult to detect generally. * **Resolution:** * **Rewrite the grammar:** Often by introducing new non-terminals or adjusting production rules. * **Operator Precedence:** Define explicit rules for operator precedence and associativity. * **Exam Point:** Ambiguity is undesirable in compiler design. ## 1.10 YACC * **YACC (Yet Another Compiler Compiler):** A parser generator that produces a parser from a grammar specification. * **Input:** A file defining the grammar rules in a BNF-like syntax, along with actions. * **Output:** A C source file for a parser (often used with LEX for lexical analysis). * **Parser Type:** Typically generates LALR(1) parsers (a type of bottom-up parser). * **Key Features:** * Defines grammar rules. * Associates **actions** (C code) to grammar rules, executed when a rule is reduced. * Handles **operator precedence and associativity** declarations. * **Usage:** 1. Write `.y` file (YACC specification). 2. Run `yacc yacc.y` to generate `y.tab.c` (parser code) and `y.tab.h` (header file). 3. Run `lex lex.l` to generate `lex.yy.c` (lexer code). 4. Compile `lex.yy.c`, `y.tab.c`, and potentially `y.tab.h` together.