Compiler Design

Answer: (iv) All of the Above

Explanation

A lexeme is the actual sequence of characters in the source program that matches the pattern of a token. The scanner groups the characters of int total = 25; into these lexemes:

Lexeme	Token class
int	keyword
total	identifier
=	assignment operator
25	integer constant
;	separator

So int, total and 25 are all lexemes.

$$\boxed{\text{(iv) All of the Above}}$$

Answer: (iii) All strings over $\{a, b\}$, including $\varepsilon$

Explanation

• $(a \mid b)$ matches exactly one symbol: either $a$ or $b$.
• The Kleene star $^*$ allows zero or more repetitions of that choice.

So the language is $\{\varepsilon, a, b, aa, ab, ba, bb, aaa, \dots\}$, i.e. every string over the alphabet $\{a,b\}$, with $\varepsilon$ (zero repetitions) included.

Why the other options fail:

• (i), (ii): they allow only one of the two symbols.
• (iv): it forces the string to start with $ab$, but $(a\mid b)^*$ also accepts $b$, $\varepsilon$, etc.

$$\boxed{\text{(iii)}}$$

Answer: (ii) DFA and NFA recognize the same class of languages

Explanation

Both DFAs and NFAs recognize exactly the regular languages.

• Every DFA is already an NFA (a special case).
• Every NFA can be converted to an equivalent DFA by the subset construction.

So neither is more powerful, which rules out (i) and (iii). An NFA is often smaller than the equivalent DFA: an NFA with $n$ states may need up to $2^n$ DFA states. That is a size difference only, and option (iv) is false because many NFAs need no more states than their DFAs (a DFA is itself an NFA).

$$\boxed{\text{(ii)}}$$

The six phases of a compiler (with an example)

A compiler translates a high-level program into target (machine) code in several phases. They are divided into the front end (source-language dependent) and back end (machine dependent).

1. Lexical Analysis (Scanner)

   • Reads the raw character stream and groups it into meaningful tokens (identifiers, keywords, operators, literals).
   • Output: a stream of tokens $\langle \text{type, attribute}\rangle$.
   • Uses a symbol table to record identifiers.
   • Example: for position = initial + rate * 60, tokens are: ident(position), =, ident(initial), +, ident(rate), *, num(60).

2. Syntax Analysis (Parsing)

   • Groups tokens into a parse tree / syntax tree according to the grammar.
   • Detects syntactic errors (e.g. x = + * y).
   • Output: a parse tree (for position = initial + rate*60 we get precedence built in: rate*60 is computed first).

3. Semantic Analysis

   • Checks the parse tree for semantic correctness: type checking, name/declaration matching, etc.
   • For types: if position, initial, rate are float and 10 is int, it may insert implicit conversion int→real.
   • Output: annotated syntax tree.

4. Intermediate Code Generation

   • Produces a machine-independent intermediate representation (e.g. three-address code).
   • Example for the above assignment:

     t1 = int_to_float(10)
     t2 = rate * t1
     t3 = initial + t2
     position = t3
     

5. Code Optimization

   • Improves the intermediate code, e.g. reduces t1 = int_to_float(10) because 10 is a constant that can be folded and converted once. After optimization:

     t2 = rate * 10.0
     position = initial + t2
     

6. Code Generation (Target Code Generation)

   • Maps optimized intermediate code onto target machine's assembly instructions, e.g.:

     MOVF R2, #10.0      (or LDF)
     MULF R2, R1
     ADDF R2, R0
     MOVF position, R2
     

Symbol Table is a central data structure maintained throughout all phases, storing names, types, scope, and addresses.

$$\boxed{\text{Order: Lexical → Syntax → Semantic → Intermediate Code → Optimization → Code Generation}}$$

Short notes (any two)

---

(a) LEX and YACC

• LEX is the lexical-analyzer generator. It takes a specification of token patterns written with regular expressions and produces a C function (e.g. yylex) that scans the input and returns tokens.

  • Structure of a LEX program: declaration %% translation rules %% auxiliary functions.
  • Each token rule: pattern → action (action = C code, e.g. return token_id;).
  • Powers: longest-match rule; a symbol table kept for identifiers/text. Used with YACC. LEX produces the scanner that feeds tokens to the parser.

• YACC ("Yet Another Compiler-Compiler") is the parser generator, producing a LALR(1) (or YACC's default SLR/LALR) parser (function yyparse) from a CFG grammar in BNF with embedded semantic actions.

  • Structure: %{ declarations %} %% productions { semantic action } %% subroutines.
  • Uses the tokens lexed by LEX; each grammar rule may have a semantic value and user code; supports precedence and associativity declarations (%left, %right); optionally builds an AST via actions.
  • Together: LEX gives tokens to YACC, YACC builds the parse tree and schedules the semantic translation.

---

(b) Peephole Optimization

A simple but effective local, post-optimization technique performed on the target (assembly/machine) code over a small window ("peephole") of adjacent instructions.

Techniques in a peephole optimizer:

1. Redundant instruction elimination (dead code): e.g. MOV R0, R1; MOV R0, R1 — delete the second.
2. Flow-of-control optimizations: e.g. jumps to jumps (JMP L; ... L: JMP L1) — replace with direct jump.
3. Algebraic simplifications: x + 0 → x; x*1 → x; x/2` → shift etc.
4. Reduction in strength: replace expensive ops like 2 * x with x + x and x^2.
5. Use of machine idioms: e.g. X = X + 0 removed, X+1 replaced by INC/INC and X<<n for X * 2^n.
6. Constant folding inside window.

Advantage: very cheap, catches a lot; often run repeatedly.

---

(c) Symbol Table

• A compile-time data structure that maps identifiers (names) to their attributes: name, type, category (variable, function, record/array), address (stack/relative/global offset), scope & lifetime, parameter list, and kind (static, local).
• Operations: insert (add new name), lookup/access (find entry), modify; the table is consulted/modified during every phase — lexical (insert), syntax/semantic (lookup/check type), code gen (get address).
• Organization:
  • Lists / hash tables; open (separate chaining) or closed addressing for speed.
  • Scoping: block structure ⇒ re-entrant by saved-bottom markers; often a stack of scopes with a new.. pointer (scope stack).
  • Multiple table organizations: (1) flat global, (2) per-scope linked lists, (3) tree/structural block table (often implemented as stack-based with block index markers).
• Lookup in nested scopes follows lexical chain (innermost outward). Implementations use hash table for names with scope table.
• Applications: optimize code-gen (address known), type checking, overloading, and reporting.

---

(d) Predictive parser

A predictive parser (or LL(1) table parser) is a non-backtracking top-down parser. It uses a parsing table M[A][a], the input's next symbol a, and a stack of grammar symbols to decide deterministically ("predict") which production to apply without backtracking.

• Table-driven: stack holds nonterminals (and $); at each step, if top of stack is terminal, match with input; if it's a nonterminal, use entry M[top][a] to choose the production for A.
• Table is built from FIRST and FOLLOW sets: M[A][a] = A→α if a∈FIRST(α), or (if α nullable) if a∈FOLLOW(A).
• A given grammar can be predictive only when it is LL(1): no multiple entries (no conflict) in any table cell and left-recursion removed + factorized.
• Also called recursive-descent parser when implemented with recursive functions, each nonterminal being one function that calls other via the table (though classic "predictive parser" = table-driven with no backtracking).
• Algorithm: repeat — look at top X and next input a:
  • if X is a, advance both;
  • if X is nonterminal and M[X][a] = X→Y1..Yk, pop X push Yk…Y1 (reverse feedback);
  • if M entry empty → error.
  • Accept when stack = $` and input = `$.

Characteristics: no backtracking ⇒ linear time (O(n) for LL(1)); works for all LL(1) grammars; fastest top-down method; the classic example is predicting grammar E → T E', etc.