AD-604-C Compiler Design - May 2024 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 8 Marks
   aExplain input buffering with example. Discuss about lexical errors in detail.
   How to answer

   • Define input buffering and need for lookahead in lexical analysis
   • Explain two-buffer scheme with sentinels and buffer pointers
   • Give example of buffering with forward and lexeme pointers
   • Define lexical errors and error handling: panic mode, insertion/deletion
2. 6 Marks
   bWhat is Lexical Analyzer? Explain role of Lexical analyzer.
   How to answer

   • Define lexical analyzer as first phase of compiler
   • Explain tasks: tokenization, stripping whitespace/comments, symbol table interaction
   • Explain role as interface between source and parser with pushback/lookahead
   • Give example of token vs lexeme vs pattern
3. 14 Marks
   Compute LR(0) items for the following grammar and construct SLR Parser table. $$S \to L=R \mid R$$ $$L \to *R \mid id$$ $$R \to L$$
   How to answer

   • Augment grammar and compute canonical LR(0) collection via closure and goto
   • Draw DFA of LR(0) items for states I0 to In
   • Compute FOLLOW sets for L, R, S
   • Construct SLR action/goto table and identify conflicts if any
4. 8 Marks
   aExplain different polymorphic functions with example.
   How to answer

   • Define polymorphism in type systems
   • Explain parametric, subtype, ad-hoc/overloading polymorphism
   • Give example for each in programming language/compiler context
   • Mention use in type checking
5. 6 Marks
   bExplain different dynamic allocation strategies.
   How to answer

   • Define dynamic storage allocation and activation records
   • Explain stack allocation strategy
   • Explain heap allocation and garbage collection
   • Compare static vs stack vs heap
6. 8 Marks
   aDescribe What is DAG? Construct DAG for the following basic blocks: $$D := B*C; E := A+B; B := B+C; A := E-D;$$
   How to answer

   • Define DAG for basic blocks and common subexpression
   • Show steps to construct nodes for D:=B*C etc.
   • Draw DAG sharing common nodes B+C
   • List labels and final node assignments
7. 6 Marks
   bExplain about peephole optimization with example.
   How to answer

   • Define peephole optimization as local sliding window optimization
   • List techniques: redundant loads/stores, strength reduction, jump simplification
   • Give assembly-level before/after examples
   • Mention benefits and limitations
8. 6 Marks
   aExplain different code improving transformation.
   How to answer

   • Define code improving transformations
   • Explain common subexpression elimination, copy propagation
   • Explain dead-code elimination, loop optimization, strength reduction
   • Give example for each transformation
9. 8 Marks
   bDefine code optimization. Explain function preserving code optimization.
   How to answer

   • Define code optimization and its criteria
   • Explain function-preserving transformations concept
   • Explain examples: common subexpression, constant folding, copy propagation
   • Distinguish machine-dependent vs independent optimization
10. 6 Marks
    aDefine parsing. Explain types of Top down parsing.
    How to answer

    • Define parsing and syntax analysis
    • Define top-down parsing from root to leaves
    • Explain types: backtracking, recursive descent, predictive LL(1)
    • Mention FIRST/FOLLOW use in predictive parsing
11. 8 Marks
    bExplain Recursive Descent parsing method with example.
    How to answer

    • Define recursive descent with one procedure per non-terminal
    • Explain working with example grammar and input string
    • Show parse tree / trace of recursive calls
    • Mention backtracking and limitations
12. 8 Marks
    aExplain L-attribute definition with suitable example.
    How to answer

    • Define L-attributed definition and left-to-right dependency
    • Explain inherited vs synthesized attributes in L-attribute
    • Give example with grammar and semantic rules
    • Show dependency graph / evaluation order
13. 6 Marks
    bExplain Register allocation and assignment with suitable example.
    How to answer

    • Define register allocation vs assignment problem
    • Explain graph coloring and spilling concept
    • Explain simple assignment with example basic block
    • Mention peephole / target machine considerations
14. 14 Marks
    Write a short note on following:

    1. a)Symbol table
    2. b)Type checking
    3. c)Loop optimization
    4. d)Constant folding
    How to answer

    • Define symbol table: structure and operations
    • Explain type checking and type expressions
    • Explain loop optimization techniques
    • Explain constant folding with example