unit 1:

@@@structure of a compiler@@@
[Link] Analysis: The first phase of a compiler is lexical analysis, also known as
scanning. This phase reads the source code and breaks it into a stream of tokens,
which are the basic units of the programming language. The tokens are then passed
on to the next phase for further processing. [Link] Analysis: The second phase of
a compiler is syntax analysis, also known as parsing. This phase takes the stream of
tokens generated by the lexical analysis phase and checks whether they conform to
the grammar of the programming language. The output of this phase is usually an
Abstract Syntax Tree (AST).
[Link] Analysis: The third phase of a compiler is semantic analysis. This phase
checks whether the code is semantically correct, i.e., whether it conforms to the
language’s type system and other semantic rules. In this stage, the compiler checks
the meaning of the source code to ensure that it makes sense. The compiler
performs type checking, which ensures that variables are used correctly and that
operations are performed on compatible data types. The compiler also checks for
other semantic errors, such as undeclared variables and incorrect function calls.
[Link] Code Generation: The fourth phase of a compiler is intermediate
code generation. This phase generates an intermediate representation of the
source code that can be easily translated into machine code.
[Link]: The fifth phase of a compiler is optimization. This phase applies
various optimization techniques to the intermediate code to improve the
performance of the generated machine code.
[Link] Generation: The final phase of a compiler is code generation. This phase
takes the optimized intermediate code and generates the actual machine code that
can be executed by the target hardware.
@@programming language in basics@@
1. Lexical Elements
 Keywords: Predefined reserved words (e.g., if, while).
 Identifiers: Names given to variables or functions.
 Operators: Symbols for operations (+, -, *).
 Delimiters: Separators like ;, {, }.
 Literals: Fixed values (e.g., numbers, strings).
 Comments: Non-executable notes in the code.
2. Syntax
 Grammar: Rules for structuring code.
 Statements: Instructions (e.g., x = y + z;).
 Expressions: Combinations of variables and operators.
 Control Structures: Logic flow using loops and conditions.
 Functions: Blocks of reusable code.
3. Semantics
 Static Semantics: Compile-time checks (e.g., type rules).
 Dynamic Semantics: Runtime behavior of code.
4. Types
 Primitive Types: Basic types (int, float).
 Derived Types: Arrays, pointers, classes.
 Type Checking: Ensures compatibility in operations.
5. Scope and Binding
 Scope: Where a variable can be accessed (e.g., local/global).
 Binding: Linking variables to values or types.
6. Data Structures
 Variables: Memory for data.
 Constants: Fixed values.
  Arrays: Collections of data.
 Structures: Custom data types.
7. Error Handling
 Compile-Time Errors: Syntax and type issues.
 Runtime Errors: Errors during execution.
 Logical Errors: Incorrect logic.
8. Standard Libraries
 Predefined functions for common tasks (e.g., printf).
9. Programming Paradigms
 Ways to code: Imperative, Object-Oriented, Functional, Procedural.
10. Intermediate Representations
 ASTs: Tree structures of code.
 Three-Address Code: Simplified instructions.
 Control Flow Graphs: Visual code flow.
@@recognition of tokens@@
Recognition of Tokens in Compiler Design
Token recognition is the process of identifying meaningful units in the source code.
It is handled during the lexical analysis phase of a compiler. Here's how it works:
A token is a sequence of characters that represents a single meaningful element in
the source code. Examples include:
 Keywords: if, while, return
 Identifiers: x, sum, myFunction
 Operators: +, -, *, /
 Literals: 42, 'a', "hello"
 Delimiters: ;, ,, (, )
Steps to Recognize Tokens
1. Read Input: The source code is read character by character.
2. Pattern Matching: Regular expressions or rules are used to match sequences
of characters to token types.
o Example: if matches the keyword pattern.
3. Generate Tokens: Each recognized sequence is assigned a token type (e.g.,
KEYWORD, IDENTIFIER).
4. Ignore Whitespace/Comments: Spaces, tabs, and comments are skipped
during tokenization.
Example
For the code:
int x = 10;
Tokens identified:
 int → KEYWORD
 x → IDENTIFIER
 = → OPERATOR
 10 → LITERAL
 ; → DELIMITER
Unit 2:
@@context free grammars@@:Context-Free Grammars (CFG) are used to define
the syntax of programming languages in compiler design. They describe how valid
sentences (statements) in a language are constructed.
Key Concepts:Grammar Components:
o Terminals: Symbols that appear in the source code (e.g., keywords,
operators).
o Non-terminals: Abstract symbols representing groups of strings (e.g.,
<expression>, <statement>).
o Start Symbol: The starting non-terminal (e.g., <program>).
o Production Rules: Rules that define how non-terminals can be
expanded into terminals and other non-terminals.
Example
A simple grammar for arithmetic expressions:
1. <expression> → <expression> + <term> | <term>
2. <term> → <term> * <factor> | <factor>
3. <factor> → ( <expression> ) | id
How It Works
1. Begin with the start symbol (e.g., <expression>).
2. Apply production rules to derive valid strings.
3. Terminate when only terminals are left.
Example Derivation
For the input id + id * id:
1. <expression>
2. <term> + <term>
3. <factor> + <term>
4. id + <term>
5. id + <factor> * <factor>
 6. id + id * id
CFGs are critical for parsing and ensuring code follows the correct structure.
@@introduction to LR parsing@@

Introduction to LR Parsing:LR Parsing is a bottom-up parsing technique used in

compilers to process the syntax of programming languages. It efficiently handles

context-free grammars by constructing parse trees in reverse (from leaves to

root)….Types of LR Parsers

1. Simple LR (SLR):

o Simplest form of LR parsing.

o Uses Follow sets to resolve conflicts.

o Handles smaller and simpler grammars.

o Suitable for basic language constructs.

2. More Powerful LR Parsers:

o Lookahead LR (LALR):

 Combines multiple SLR states for efficiency.

 Balances power and resource usage.

 Used in many practical compilers.

o Canonical LR:

 Most powerful but computationally expensive.

 Rarely used due to complexity.

Key Features

 Shift-Reduce Parsing: Shifts input onto a stack and reduces using grammar

rules.

 Parsing Table: Guides the parser with states and actions.

@@Variants of Syntax Trees@@

Variants of Syntax Trees in Compiler Design:Syntax trees represent the hierarchical

structure of a program based on its grammar. Different types of syntax trees are

used in compiler design, depending on the analysis phase or specific needs.

1. Parse Tree (Concrete Syntax Tree)

 Represents all grammar rules applied during parsing.

 Includes all terminals and non-terminals from the grammar.

 Example: For a + b, every rule used (e.g., <expression> → <term> + <term>) is

shown.

2. Abstract Syntax Tree (AST)

 Simplified version of the parse tree.

 Represents essential structure without unnecessary grammar details.

 Focuses on operators, operands, and expressions.

 Example: For a + b, only the operator + and operands a and b are shown.

3. Directed Acyclic Graph (DAG)

 Optimized form of AST.

 Merges common sub-expressions to avoid duplication.

4. Dependency Tree:1..Represents dependencies between constructs in a program.

 Often used in semantic analysis or intermediate representations.

@@@switch statements@@

Switch Statements in Compiler Design:A switch statement is a control structure used

in programming to handle multiple conditions efficiently. In compiler design, it is

processed during the syntax analysis and code generation phases.

Key Components

1. Expression: Evaluated once to determine the case (e.g., switch(x)).

2. Cases: Blocks of code for specific values (e.g., case 1: ...).

3. Default: Executed if no cases match (optional).

Implementation in Compiler

1. Syntax Analysis: The grammar for a switch statement is parsed (e.g., switch

(expr) { case ... default ... }).

2. Intermediate Code Generation:

o Jump Tables: A table of addresses for case blocks for efficiency.

o Sequential Checks: Evaluates cases one by one for simpler

implementation.

3. Optimization:
 o Jump Table is preferred for a large number of cases for faster execution.

o If-Else Ladder is used for fewer or non-contiguous cases.

Example (C-like Syntax)

switch(x) {

case 1:

printf("One");

break;

case 2:

printf("Two");

break;

default:

printf("Default");

The compiler converts this into efficient low-level instructions using jump tables or

conditional branches.
Unit 5:

@@principle sources of optimization

Principal Sources of Optimization in Compiler Design:Optimization improves

program performance and reduces resource usage by refining the generated code

without altering its functionality.

Key Sources of Optimization

1. Common Sub-expression Elimination

o Identifies and removes duplicate calculations.

o Example: Replace x = a + b + c + a + b; with temp = a + b; x = temp + c +

temp;.

2. Loop Optimization

o Invariant Code Motion: Moves calculations outside the loop if they

don’t change.

 Example: for (i = 0; i < n; i++) y = 2 * x; → y = 2 * x; for (i = 0; i < n;

i++).

o Loop Unrolling: Reduces loop overhead by executing multiple iterations

together.

3. Dead Code Elimination

o Removes code that does not affect the program’s output.

4. Constant Folding

o Computes constant expressions at compile time.

o Example: Replace x = 2 + 3; with x = 5;.

5. Strength Reduction

o Replaces expensive operations with cheaper ones.

o Example: Replace x = y * 2; with x = y << 1; (bitwise shift).

6. Inline Function Expansion

o Replaces function calls with the actual function body to avoid call

overhead.

7. Peephole Optimization

o Analyzes and simplifies small instruction sequences in the generated

code.

o Example: Replace add r1, 0 with no operation.

Introduction to Data-Flow Analysis in Compiler Design:Data-Flow Analysis is a

technique used in compilers to gather information about how data is defined, used,

and propagated throughout a program. It helps in optimizing the code by analyzing

the flow of data across control structures.

Key Concepts

1. Control Flow Graph (CFG)

o Represents the flow of control in a program.

o Nodes = Basic blocks (sequential statements).

o Edges = Control flow between blocks (e.g., loops, branches).

2. Data-Flow Equations

o Mathematical representations used to express how data changes as it

flows through the program.

3. Properties Analyzed:

o Reaching Definitions: Determines which definitions (assignments) of

variables reach each point in the program.

o Live Variables: Identifies variables used before they are redefined

(useful for dead code elimination).

still valid, avoiding redundant calculations.

Applications

 Code Optimization: Eliminates redundant calculations, dead code, and

unnecessary assignments.

 Register Allocation: Determines which variables need to stay in registers at

different program points.

 Error Detection: Identifies uninitialized variables and unused code.

Example

In a loop:

x = a + b;

y = x + c;

z = y * 2;

 Reaching Definitions: Tracks whether x = a + b reaches the second line.

 Available Expressions: Identifies a + b as reusable.

 Live Variables: Determines if x, y, or z are needed after the loop.

Data-Flow Analysis forms the foundation for many compiler optimizations.

Peephole optimization@@

**Peephole Optimization is a technique that looks at small sets of instructions in the

generated code to replace them with faster or more efficient versions while keeping

the program's behavior unchanged.

### **Key Features**

-Local Optimization**: Works on small code sections.

- Post-Compilation**: Applied after code generation.

### **Common Techniques**

1. **Constant Folding**:

Simplifies constant expressions (e.g., `ADD 2, 3 → MOV 5`).

2. **Redundant Instruction Removal**:

Removes unnecessary instructions.

Example:

MOV R1, R2

MOV R2, R1 → Optimized to remove the second line.

3. **Strength Reduction**:
 Replaces costly operations with simpler ones (e.g., `MUL R1, 2 → ADD R1, R1`).

4. **Dead Code Elimination**:

Removes unused instructions (e.g., `MOV R1, 5` if `R1` is never used).

5. **Jump Optimization**:

Removes unnecessary jumps (e.g., `JMP L1` → `JMP L2` if `L1` immediately jumps

to `L2`)

### **Advantages**

- Speeds up execution.

- Reduces code size.

- Easy to implement.

### **Limitations**

- Works only on small code windows.

- Misses broader optimizations.