IT-603-A Compiler Design - May 2023 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. 7 Marks
   aList out different phases of the compiler and explain each phase's role in the compilation process.
   How to answer

   • List six phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, code generation plus symbol table and error handler
   • Explain input to output of each phase with example a=b+c*2
   • Show block diagram of compilation flow
2. 7 Marks
   bDiscuss how Finite Automata is used to recognize tokens and perform lexical analysis with an example.
   How to answer

   • Define token, lexeme, pattern and finite automata DFA/NFA
   • Explain transition diagram for identifiers, numbers, keywords
   • Show lexical analyzer recognizing tokens with example
3. 7 Marks
   aExplain briefly about the LEX Compiler.
   How to answer

   • Define LEX as lexical analyzer generator
   • Explain LEX source format: definitions, rules, user subroutines
   • Explain working: lex.l to lex.yy.c to a.out with diagram
4. 7 Marks
   bWrite in detail about operator precedence parsing.
   How to answer

   • Define operator precedence grammar and precedence relations
   • Explain precedence table and stack implementation
   • Explain shift-reduce parsing steps with example
5. 7 Marks
   aCheck whether the given grammar $G: S \to L=R / R$ $L \to *R/id$ $R \to L$ is SLR(1) is correct. Explain the reasons.
   How to answer

   • Augment grammar and construct LR(0) canonical collection
   • Compute FIRST/FOLLOW and SLR(1) table
   • Check for shift-reduce/reduce-reduce conflicts to decide SLR(1)
6. 7 Marks
   bConstruct CLR parsing table for the grammar G $E \to E+T/T$ $T \to T*F/F$ $F \to (E)/id.$
   How to answer

   • Augment grammar and construct LR(1) canonical collection
   • Compute lookaheads and CLR parsing table ACTION/GOTO
   • List states, transitions and table entries
7. 7 Marks
   aExplain bottom up evaluation of L-attributes with an example.
   How to answer

   • Define L-attributed definition and dependency
   • Explain depth-first bottom-up traversal with parse tree
   • Illustrate evaluation with example
8. 7 Marks
   bDifferentiate between S-attributed definition and L-attributed definition.
   How to answer

   • Define S-attributed: only synthesized attributes
   • Define L-attributed: synthesized + inherited with left-to-right restriction
   • Compare on evaluation order, parse tree traversal, implementation
9. 7 Marks
   aWrite the syntax directed translation scheme for case statements.
   How to answer

   • Define syntax directed translation for switch-case
   • Give grammar for case statement with labels
   • Write semantic actions for jump labels and code generation
10. 7 Marks
    bConstruct Quadruples, triples and indirect triples for the given expression: $a+a*(b-c)+(b-c)*d.$
    How to answer

    • Generate three-address code for $a+a*(b-c)+(b-c)*d$
    • Construct quadruples table with op, arg1, arg2, result
    • Construct triples and indirect triples with pointers
11. 7 Marks
    aDifferentiate between static and Dynamic storage allocation strategies.
    How to answer

    • Define static allocation: compile-time binding, stack/static area
    • Define dynamic allocation: heap, runtime allocation/deallocation
    • Compare on lifetime, efficiency, recursion support, overhead
12. 7 Marks
    bDefine Symbol table. Explain the various data structures used to implement the Symbol table.
    How to answer

    • Define symbol table purpose in compilation
    • Explain list, hash table, tree implementations
    • Explain operations: insert, lookup, scope management
13. 7 Marks
    aExplain loop optimization technique with an example.
    How to answer

    • Define loop optimization: code motion, induction variables, strength reduction
    • Explain with example loop moving invariant out
    • Show before-after three-address code
14. 7 Marks
    bExplain the following optimization techniques:

    1. i)Common subexpression elimination
    2. ii)Code Motion
    3. iii)Variable Propagation
    4. iv)Strength reduction
    How to answer

    • Define each technique with purpose
    • Give example three-address code for each
    • Explain effect on execution time and code size
15. 14 Marks
    Write short notes on any two of the following:

    1. i)Capabilities of CFG
    2. ii)Steps to compute FIRST and FOLLOW
    3. iii)Dependency graph and Back patching
    4. iv)Basic block construction
    How to answer

    • Select any two topics with definition and need
    • Explain steps/rules with example or diagram
    • Mention applications in compiler phases