Compiler Design Tutorials

Example 1: FIRST Set Calculation

Consider the grammar:

E → T E'
E' → + T E' | ε
T → id

To find FIRST(E), we look at what E derives. Since E → T E', FIRST(E) depends on FIRST(T). T only derives id, so FIRST(T) = { id }. Because T does not derive ε, FIRST(E) = FIRST(T) = { id }. This shows the general rule: for a production A → B, if B cannot derive ε, then FIRST(A) is simply FIRST(B).

Example 2: Three-Address Code for an Expression

For the expression a = b + c * d, three-address code is generated by breaking the expression into single operations:

t1 = c * d
t2 = b + t1
a  = t2

Each line performs exactly one operator, which is the defining property of three-address code. Multiplication is evaluated before addition, so c * d is computed first and stored in a temporary variable before being added to b.

Example 3: Checking a Grammar for Left Recursion

A production such as A → A α | β is left recursive because A appears as the first symbol on the right-hand side of its own production. Left recursion must be eliminated before top-down parsing, typically by rewriting it as:

A  → β A'
A' → α A' | ε

This transformation preserves the language generated by the grammar while making it usable for recursive-descent or LL(1) parsing.

Beginner Practice

1. Identify the tokens produced by the lexical analyzer for the statement int x = 10;
2. Differentiate between a compiler and an interpreter with one example each.
3. List the six major phases of a compiler in the correct order.
4. Write a regular expression for identifiers that start with a letter and are followed by letters or digits.

Intermediate Practice

1. Compute FIRST and FOLLOW sets for a small grammar with two non-terminals.
2. Eliminate left recursion from a given grammar and construct its predictive parsing table.
3. Generate three-address code for the expression x = (a + b) * (c - d).
4. Explain, with an example, why a grammar may not be suitable for LL(1) parsing.

Revision Challenge

1. Why does LALR parsing produce smaller tables than CLR parsing while covering most practical grammars?
2. Explain the difference between synthesized and inherited attributes with one example each.
3. What is the purpose of a symbol table during semantic analysis and code generation?
4. Give one example of a code optimization technique that does not change a program's output.