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.