Unit 1: Introduction to Compiler
- Draw the detailed block diagram of a compiler showing all phases with inputs and outputs of each phase. Explain how symbol table and error handler interact with different phases of compilation.
- What is a macro? Differentiate between macro and procedure. Explain macro expansion with example. Show the complete macro expansion for: #define SQUARE(x) ((x) * (x)); #define MAX(a, b) ((a) > (b) ? (a) : (b)); #define CUBE(x) (SQUARE(x) * (x)); result = MAX(SQUARE(3), CUBE(2));
- Explain different phases of compiler in brief.
- Difference between compiler and interpreter. "Symbol table is necessary component of compiler". Justify this statement with examples.
- Difference between compiler and interpreter.
- Discuss the importance of error handler in compiler. How is it manipulated in the different phases of compilation?
- What are the roles of macros and preprocessor? Discuss about one pass and multi pass compiler.
Unit 2: Lexical Analyzer
- What is the difference between LR(0), SLR(1), and LR(1) parsing? Explain with examples when each would fail or succeed. Compute the LR(1) items and construct the LR(1) parsing table for: S' → S; S → AA; A → aA | b. Show the parsing actions for the input string "aab".
- Explain the role of lexical analyzer in compiler design. What is input buffering? Describe the buffer-pair scheme with sentinels and explain why it is efficient. Design a lexical analyzer using transition diagram that recognizes: Identifiers (letter followed by letters/digits), Integer constants, Operators: +, -, *, /, <, <=, >, >=, ==, =, Keywords: if, then, else, while. Show the transition diagram and write pseudocode for the nextToken() function.
- What is L-attributed definition? Differentiate between S-attributed and L-attributed definitions with examples. Write an L-attributed syntax-directed definition for the following grammar that builds a syntax tree: E → E₁ + T; E → T; T → T₁ * F; T → F; F → (E); F → id. Draw the annotated parse tree showing all attribute values for the input: id₁ + id₂ * id₃
- What are closure and goto operations in LR parsing? Compute the closure of the following LR(0) item set: I₀ = {[S' → •S, $]}. Grammar: S → AB; A → aA | b; B → c. Then compute GOTO(I₀, a) showing all steps.
- Construct the operator-precedence relations (⋖, ≐, ⋗) for the following grammar: E → E + T | T; T → T * F | F; F → (E) | id. Build the complete operator-precedence table. Parse the string id + id * id using this table showing all stack operations.
- Write short notes on: a) Type checking: Static vs Dynamic type checking with examples; b) Synthesized vs Inherited attributes with expression evaluation example
- What is ambiguous grammar? Explain the "Dangling Else" problem with example. Show how to resolve it. Construct the LL(1) parsing table for the following grammar (after removing left recursion if needed): E → E + T | T; T → T * F | F; F → (E) | id. Parse the string id + id * id using this table.
- Convert the following regular expression to NFA using Thompson's construction: (a|b)*a(a|b). Then convert this NFA to DFA using subset construction method. Finally, minimize the DFA using state minimization algorithm.
- What is recursive descent parsing? Write a recursive descent parser for the following grammar: S → aS | bA; A → bA | c. Show how it parses the string "aabc".
- Given the following DFA with states {A, B, C, D, E, F}, minimize it using state minimization algorithm: Start state: A; Final states: {D, F}; Transitions: δ(A, 0) = B, δ(A, 1) = C; δ(B, 0) = D, δ(B, 1) = E; δ(C, 0) = E, δ(C, 1) = D; δ(D, 0) = D, δ(D, 1) = D; δ(E, 0) = F, δ(E, 1) = F; δ(F, 0) = F, δ(F, 1) = F. Show all steps clearly including partition refinement.
- Compute FIRST and FOLLOW for all non-terminals in the grammar: S → ACB | CbB | Ba; A → da | BC; B → g | ε; C → h | ε. Construct the LL(1) parsing table. Is this grammar LL(1)? Justify your answer.
- What are handles in LR parsing? Explain handle pruning with example. For the grammar: E → E + T | T; T → T * F | F; F → (E) | id. Show the handle at each step for reducing the string: id + id * id
- Give an example of reduce-reduce conflict. Construct the SLR parsing table for the following grammar. E→ (L) | a; L → L, E | E
- Compute the FIRST and FOLLOW of the non-terminals in the following grammar: S → (L) ∣ 1; L → LS ∣∗S
- Define core item. Compute the LR(1) item sets for the following grammar: S → AA; A → aA ∣ b
- Describe the synthesized attribute and inherited attribute with an example.
- What is a type expression? List the properties of LL(1) grammar.
- List out the major tasks carried out in Lexical Analysis Phase. Convert the following NFA to DFA.
- Differentiate between recursive descent and non-recursive predictive parsing method. Find first and follow of all the non-terminals in the following grammar. E→TA; A→ +TA|ε ; T→FB; B→*FB|ε ; F→(E)|id
- Construct SLR parse table for the following grammar. S→E; E→E+T|T; T→T*F|F; F→id
- Define Syntax directed definition. Construct annotated parse tree for the input expression (5*3+2)*5 according to the following syntax directed definition.
- Differentiate between static and dynamic type checking. How can we carry out type checking for the following expression using syntax-directed defination? S→ id = E; S→ if E then S1; S→ while E do S1; S→ S1; S2
- How does Lexical Analyzer recognize a token? Give an example to make it clear. Convert the regular expression a(a+b)(b+c)*a# to DFA.
- Construct the LR(1) parsing table for the following grammar. S → AaAb; A → BbBa; A → ε; B → ε
- What is annotated parse tree? Define S-attributed grammar with an example.
- Describe about syntax directed translation with an example.
- Given the following grammar with SLR parsing table, test whether the string "int * (int + int)" will be accepted or rejected. E -> T + E……….(1); E -> T……….(2); T -> int*T……….(3); T -> int……….(4); T -> (E)……….(5)
- Find the FIRST and FOLLOW of all the non terminals in following grammar. S → aAbCD | ε; A → SD | ε; C → Sa; D → aBD | ε
- Given a regular expression (ε + 0)*10. Construct the DFA recognizing the pattern described by this regular expression using syntax tree based reduction.
- What is shift reduce parsing techniques? Show shift reduce parsing action for the string (x+x)*a, given the grammar
- Construct SLR parsing table for the following grammar. S -> aAa | bAb | ba
- Write Syntax Directed Definition to carry out type checking for the following expression. E -> id | E1 op E2 | E1 relop E2 | E1[E2] | E1 ↑
- What are the task performed in lexical analysis. Define DFA. Given regular expression: (a+b)*a(a+b)
- Difference between LR(0) and LR(1) algorithm. Construct LR(1) parse table for s->AA ,A->aA/b
- Define Left recursive grammar. Remove left recursion from the following grammar. S→SB | Ca; B→Bb | c; C→aB | a
- What are the disadvantages of shift reduce parsin perform shift reduce parsing of string w=(x-x)-(x/x) for grammar E=E-E/ E/E / (E) / x
- Define attribute grammar with example of inherited and synthesized attributes
- Construct the LL(1) parsing table for the following grammar. S → AS1 | C; A → 0; C → 2C | ε
- Compute the FIRST and FOLLOW of all the non-terminals in following grammar. S → AB; A → 0A' | 1A' | ε; A' → SSA' | ε; B → AS | 1
- Generate the LR(0) item sets for the following grammar. A → BB; B → bB | a
- Define explicit and implicit type conversion. Why do we need to check type of the system? Justify with an example.
- Create the LR(1) parsing table for following grammar. S → AA; A → 0A; A → ε
Unit 3: Symbol Table Design and Runtime Storage Management
- What is a symbol table? Compare different data structures for implementing symbol table: Linear list, Hash table, Binary search tree. Which is most efficient and why? Show hash table implementation for storing the following identifiers using hash function h(x) = (sum of ASCII values) mod 7: Identifiers: {sum, count, avg, total, temp}. Use chaining for collision resolution.
- Draw and explain the complete structure of an activation record with all components (return value, actual parameters, control link, access link, saved machine status, local data, temporaries). Show the activation tree and activation record contents for the following code at the point when factorial(1) is executing.
- What types of information are stored in a symbol table? Discuss the activation record.
- What is activation record? Discuss the different activities performed by caller and callee during procedure call and return.
- What are the typical entries made in symbol table? Explain.
- List out the different types of runtime storage management techniques.
Unit 4: Intermediate Code Generator, Code Generator, Optimization and Case studies
- What is peephole optimization? Explain the following peephole optimization techniques with examples: Redundant load/store elimination, Constant folding, Strength reduction, Use of machine idioms. Apply these optimizations to the following assembly code.
- Construct the flow graph for the following code and identify all basic blocks. Identify loop invariant code that can be moved out of the loop, if any.
- What is backpatching? Why is it used in code generation? Generate three-address code with backpatching for the following code: while (a < b) { if (c < d) x = y + z; else x = y – z; }. Also show the quadruples and explain how backpatch function works.
- What is intermediate code? Explain the advantages of three-address code. Generate three-address code, quadruples, triples, and indirect triples for: a = b * (-c) + d / e
- Write syntax-directed definitions for translating boolean expressions into three-address code using backpatching. Generate code for: if (a < b && c > d || e == f) x = 1; else x = 0;
- Explain the following code optimization techniques with examples: a) Copy propagation, b) Constant folding, c) Dead code elimination, d) Strength reduction. Apply all applicable optimizations to: x = 3; y = x; z = x + 5; a = y * 2; b = 8; c = b / 2; d = a + 0;
- What is register allocation? Explain register allocation using graph coloring algorithm. Given the following live ranges, perform register allocation with 3 registers available. Draw the interference graph and assign registers.
- What are the significances of intermediate code? Differentiate between DAG and Syntax tree. Represent the instruction A = B + C − D * E + G using quadruple and triple.
- Write the code generation algorithm for the instruction a = b op c.
- What are the techniques for compiler optimization? Explain.
- Define three address codes. write three address codes for S → do m = n-p while a <= b
- Define code optimization. Discuss about any three code optimization techniques with example.
- Discuss about the different factors affecting target code generation.
- Why code optimization is needed? Describe any two techniques for loop optimization.
- What is three-address code? How high level code is converted to three address code? Illustrate with an example.
- How do you recognize basic block? Discuss about the factors that affect code generator.
- Explain with example about different methods of intermediate code representation.
- Define three address code. Write down Quadruples for a=-b*(c+d)/e
- What are the advantages of code optimization. Define Dead-code elimination.
- Explain the optimization techniques for code optimization. Convert the following program to basic block and control flow. M = A + B; N = C + D; IF (M > N) X = M – N; ELSE E = M + N + X
- What are the advantages of intermediate code? How do you convert procedure call to 3AC?
- Discuss about Directed Acyclic Graph with an example. Represent the expression A = (B + C) – (D – E) using 3AC, Quadruple and Triple.
Miscellaneous / Cross-Chapter Questions
- Write short notes on: a) Error recovery in parsing (panic mode, phrase-level recovery); b) Parameter passing mechanisms (call by value, call by reference, call by name)
- Illustrate the concept of backpatching with an example. Convert the regular expression a(a + b)a# to DFA.
- How do you represent recursion in an activation tree? Generate the three-address code for the following instruction: n = (a + b) * (c - d); for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { x = n + i + j; } }
- Differentiate between one-pass and multi-pass compiler. Construct the LL(1) parsing table for the following grammar. S → ABCD; A → a | ε; B → b; C → 0 | ε; D → d | ε
- What is activation tree? Define type checking system with examples.
- What are the advantages of intermediate code? What types of information are provided by symbol table?
- What is a symbol table? Discuss the general structure of an LR parser.