IT-603-A Compiler Design - Jun 2025 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
   aSpecify the reasons for separating the lexical analysis and syntax analysis.
   How to answer

   • Define roles of lexical analysis vs syntax analysis
   • Simpler design and modularity
   • Improved efficiency, portability and error handling
   • Reasons: separation of concerns, regular vs context-free powers
2. 7 Marks
   bExplain with an example how the lex program performs lexical analysis for identifiers and arithmetic operators.
   How to answer

   • Brief structure of lex program: definitions, rules, user subroutines
   • Regular expressions for identifiers and arithmetic operators
   • Example lex rules with actions returning tokens
   • How lex generates lexical analyzer and token stream
3. 7 Marks
   aConstruct the parse tree for the string $a+b*c$ using the grammar $E \rightarrow E+E \mid E*E \mid a \mid b \mid c$ by eliminating the ambiguity.
   How to answer

   • Rewrite ambiguous grammar $E \rightarrow E+E \mid E*E \mid a \mid b \mid c$ to enforce precedence
   • Give unambiguous grammar with precedence of $*$ over $+$
   • Show derivation steps for $a+b*c$
   • Draw parse tree with $+$ at root and $b*c$ as right subtree
4. 7 Marks
   bCompare SLR and LALR parsers.
   How to answer

   • Define SLR and LALR parsers and canonical collection basis
   • Compare table size, power and construction method
   • Compare resolving conflicts and lookaheads
   • Give example grammar where LALR succeeds but SLR fails
5. 14 Marks
   Construct CLR(1) parsing table for the grammar $S \rightarrow L=R \mid R$ $R \rightarrow L$ $L \rightarrow *R \mid id$.
   How to answer

   • Augment grammar and compute LR(1) items and closures
   • Construct canonical collection of sets for $S \rightarrow L=R \mid R$, $R \rightarrow L$, $L \rightarrow *R \mid id$
   • Compute GOTO and ACTION with lookaheads
   • Present CLR(1) parsing table with shift/reduce/accept entries
6. 7 Marks
   aExplain bottom up evaluation of S-Attributes with an example.
   How to answer

   • Define S-attributed grammar with only synthesized attributes
   • Explain bottom-up evaluation using LR parser stack with semantic values
   • Give example with annotated parse tree / stack actions
   • Order of evaluation follows post-order traversal
7. 7 Marks
   bExplain how an L-attributed grammar is converted into a translation scheme.
   How to answer

   • Define L-attributed grammar and restriction on inherited attributes
   • Explain embedding actions and marker non-terminals
   • Steps to convert inherited/synthesized rules into translation scheme
   • Example with traversal order and stack implementation
8. 7 Marks
   aExplain dependency graph with an example.
   How to answer

   • Define dependency graph for attribute instances in parse tree
   • Explain nodes as attributes and edges as dependencies
   • Give example grammar with parse tree and graph
   • Use for evaluation order and cycle detection
9. 7 Marks
   bWrite the different intermediate forms for the equation $d = (a-b) + (a-c) + (a-c)$.
   How to answer

   • Write three-address code / quadruples / triples for $d=(a-b)+(a-c)+(a-c)$
   • Show syntax tree and DAG representation
   • Show postfix / prefix notation
   • Compare forms and common subexpression handling
10. 7 Marks
    aDiscuss the various data structures used to implement the symbol table.
    How to answer

    • Define symbol table purpose and operations
    • Describe list, hash table, binary tree structures
    • Describe scoped / hash with chaining and open addressing
    • Compare search, insert, memory and scope handling
11. 7 Marks
    bExplain in brief about the Heap Storage allocation strategy?
    How to answer

    • Define heap allocation and dynamic lifetime
    • Explain malloc/free, fragmentation and garbage collection
    • Contrast with stack and static allocation
    • Give example of activation with variable-size data
12. 7 Marks
    aExplain optimization of basic blocks.
    How to answer

    • Define basic blocks and leaders
    • Explain DAG construction and local transformations
    • List optimizations: common subexpression, dead code, strength reduction
    • Show example before and after optimization
13. 7 Marks
    bCompare reducible and non reducible flow graphs.
    How to answer

    • Define flow graphs, dominators and back edges
    • Define reducible vs non-reducible graphs
    • Compare with examples and effect on data-flow analysis
    • Mention transformation to reducible form
14. 14 Marks
    Write short notes on any two of the following.

    1. a)Bootstrapping
    2. b)Operator precedence parser
    3. c)Dependency graph
    4. d)Activation record
    How to answer

    • Select any two topics from four options
    • Give definition, working and diagram for each
    • Mention use in compiler phases with example
    • Conclude with advantages/limitations