Compiler Design and Construction - Unit Wise Questions
1. List out the tasks performed by Lexical Analyser. Define DFA. Convert the Regular Expression (a+b)*a(a+b) to DFA directly. (3+1+6)
1. Explain the various phases of compiler in detail with practical example.
1. Explain briefly about different phases involved in compiler, with a block diagram.
1. Define the compiler. Explain the phases of compiler.
1. Explain the analysis phase of the compiling a source program with example.
1. Draw block diagram to represent different phases of compiler. Explain different steps in analysis phase.
1. Draw block diagram of compiler. Explain different steps in synthesis phase.
1. Differentiate between compiler and interpreter. "Symbol table is a necessary component of compiler", justify this statement with examples.
2. Differentiate between LR(0) and LR(1) algorithm. Construct LR(1) parse table of the following grammar.(3+7)
S->AA
A->aA | b
3. Define type checking. Differentiate between type casting and coercion? Write SDD to carry out type checking for the following expression.
E->n|E*E| E==|E[E] | E↑
4. Define compiler and differentiate it with an interpreter.
5. What are the typical entries made in symbol table? Explain.
6. Define Left recursive grammar. Remove left recursion from the following grammar.
S→SB | Ca
B→Bb | c
C→aB | a
8. What are the compiler construction tools? Explain.
4. Define compiler. Explain analysis phase of compiler.
7. What are the disadvantages of shift reduce parsing. Perform shift reduce parsing of string
w= (x-x) -(x/x) for given grammar.
E→ E-E | E/E | (E) | x
8. Define attribute grammar with example of inherited and synthesized attributes.
10. Differentiate between C compiler and Pascal compiler.
10. Discuss the importance of error handler in compiler. How is it manipulated in the different phases of compilation?
10. Differentiate between Pascal compiler and C++ compiler.
10. Discuss the importance of error handler in compiler. How is it manipulated in the different phases of compilation.
9. Define three address codes. Write down Quadruples for,
a = -b*(c+d)/e
1. What do you mean by compiler? Explain the semantic analysis phase of compiler construction.
10. List out different types of run time storage management techniques. Explain any one of them.
11. What is the advantages of code optimization? Explain about dead - code elimination.
12. Explain about the factors affecting target code generation.
2. Convert the following RE to DFA directly.
(a+b)*ab
2. Why are regular expressions used in token specification? Write the regular expression to specify the identifier like in C.
2. Design a lexical analyzer generator and explain it.
2. List out the major tasks carried out in Lexical Analysis Phase. Convert the following NFA to DFA.
2. Explain about design of lexical analyzer generator with its suitable diagram.
2. What is the role of regular expression in lexical analysis? Also give example.
2. Given a regular expression (ε + 0)*10. Construct the DFA recognizing the pattern described by this regular expression using syntax tree based reduction.
2. What are the functional responsibilities of a lexical analyzer? Write a lexical analyzer that recognizes the identifier of C language.
1. Differentiate between top-down and bottom-up parsing methods. Construct SLR parse table for the following grammar.
2. Define token, pattern and lexeme with suitable example. How input buffering can be implemented for scanner, Explain.
3. Differentiate between top-down parsing and bottom-up parsing.
3. What are regular definitions? Given the following CFG,
Write the regular definitions for
the terminals used. Also, construct the transition diagram for id and num.
3. Discuss the specification of lexical analyzer generator Lex.
3. What is shift reduce parsing techniques? Show shift reduce parsing action for the string (x+x)*a, given the grammar
3. Differentiate between recursive descent and non-recursive predictive parsing method. Find first and follow of all the non-terminals in the following grammar.
3. What is shift reduce parsing technique? Show shift reduce parsing action for the string a*(a+a), given the grammar
2. What are static and dynamic type checking? Write SDD to carry out type checking for the following expression.
E->id |E1 op E2 | E1 relop E2 | E1[E2] | E1↑
3. What are the problem with top down parsers? Explain the LR parsing algorithm.
3. Find first and follow of all the non terminals in the following grammar.
3. Given the regular expression (0 + 1)* 011 , construct a DFA equivalent to this regular expression computing follow pos ().
4. Find first and follow for the non-terminals in the following grammar.
4. Differentiate between LR(0) and LR(1) algorithm.
4. Construct SLR parsing table for the following grammar.
S -> aAa | bAb | ba
4. Consider the following grammar:
a. Eliminate Left recursion.
b. Compute FIRST & FOLLOW
for the symbol in the grammar.
4. Explain the role of the parser. Write an algorithm for non-recursive predictive parsing.
4. Define finite automata. Construct a finite automata that will accept a string at zeros and ones that contains an odd number of zeros and an even number of ones.
4. Construct SLR parse table for the following grammar.
4. Consider the grammar:
a. Show that this grammar is ambiguous by constructing two different leftmost derivations for sentence abab.
b. Construct the corresponding rightmost derivations for abab.
c. Construct the corresponding parse trees for abab.
4. Translate the arithmetic expression a*-(b+c) into syntax tree. Explain the ambiguous grammar.
4. Given a regular expression (a+∈) bc*. Construct the DFA recognizing the pattern described by the regular expression using syntax tree based reduction.
5. Consider the following grammar:
a. Show steps of shift-reduce parsing for the input string id+id*id.
b. Identify conflicts during the parsing.
5. What is Syntax Directed Definition? Define synthesized and inherited attributes with example.
5. Explain in detail about the recursive-descent parsing with example.
5. Consider the grammar
Calculate the
canonical LR(0) items.
5. Construct the grammar:
Compute the
complete LR(0) collection of item set from above grammar.
5. Construct LR(1) parse table for
5. Define Syntax directed definition. Construct annotated parse tree for the input expression (5*3+2)*5 according to the following syntax directed definition.
|
Production |
Semantic
Rule |
|
L
-> En |
Print
E.val |
|
E
-> E1 + T |
E.val
-> E1.val + T.val |
|
E
-> T |
E.val
->T.val |
|
T
-> T1 * F |
T.val
-> T1.val * F.val |
|
T
-> F |
T.val
-> F.val |
|
F
-> (E) |
F.val
-> (E.val) |
|
F
-> digit |
F.val
-> digit.lexval |
5. What is semantic analysis? Why is it necessary to perform semantic analysis? Explain.
6. Write Syntax Directed Definition to carry out type checking for the following expression.
E -> id | E1 op E2 | E1 relop E2 | E1[E2] | E1 ↑
6. Given the following grammar:
6. Describe the inherited and synthesized attributes of grammar using an example.
6. Show that the following grammar is not in a LL(1) grammar.
6. Describe the L- attributed definitions. How L-attributed definitions are evaluated?
6. What are the main issues involved in designing lexical analyzer? Mention the various error recovery strategies for a lexical analyzer.
6. How can syntax directed definition be used in type checking?
6. Write Syntax Directed Definition to carry out type checking for the following expression.
E -> id | E1 op E2 | E1 relop E2 | E1[E2] | E1 ↑
6. Differentiate between static and dynamic type checking. How can we carry out type checking for the following expression using syntax-directed definition?
7. Define the term ‘item’, ‘closure’ and ‘goto’ used in LR parsing. Compute the SLR DFA for the following grammar.
7. Define a context free grammar. What are the component of context free grammar? Explain.
7. Write the type expressions for the following types:
a.
An array of pointers to real’s, where the array index range from 1 to 100.
b.
Function whose domains are function from two characters and whose range
is a pointer of integer.
7. What do you mean by kernel and non-kernel items? Compute the kernel items for LR(0) for the following grammar.
7. Write the type expressions for the following types:
a. An array of pointers to real’s, where the array
index range from 1 to 100.
b. Function whose domains are function from two characters and
whose range is a pointer of integer.
8. What do you mean by S-attributed definition and how they are evaluated? Explain with example.
8. For the following grammar,
9. Consider the following grammar for arithmetic expression using an operator ‘op’ to integer or real numbers.
E → E1 op E2 | num.num
| num | id
6. Given a regular expression (ε + 0)*10. Construct the DFA recognizing the pattern described by this regular expression using syntax tree based reduction.
7. Define the terms token, pattern and lexeme. How input buffer can be used for scanner. Explain.
8. Find first and follow of all the non terminals in the following grammar.
E ➜ TA ; A➜+TA|ɛ ; T➜FB ; B➜*FB | ɛ ; F➜(E) | id
9. What is Syntax Directed Definition? Define synthesized and inherited attributes with example.
5. “Symbol table is a necessary component of compiler”, justify this statement with examples.
9. What is activation record? Discuss the different activities performed by caller and callee during procedure call and return.
10. Discuss the importance of symbol table in computer. How is it manipulated in the different phases of compilation?
10. What do you mean by runtime storage allocation? Differentiate static and dynamic allocation.
3. What is the role of intermediate code generation in the entire compilation process? Convert the following into three address code.
a+(b-c)*d
5. What are the different issues in the design of code generator? Explain with example about the optimization of basic blocks.
5. Explain the dynamic programming code generation algorithm with example.
6. What do you mean by code optimization? Explain the basic blocks and their optimization.
7. What is the theme of code optimization? Why is code optimization important in computer?
7. What is code optimization? What is its importance?
7. Explain with example about different methods of intermediate code representation.
7. Define three address codes. Write three address codes for
S --> do m=n-p while a<=b
7. What are the generic issues in the design of code generators? Explain
8. Defıne code optimization. Discuss about any three code optimization techniques with example.
8. What are the various issues of code generator? Explain the benefits of intermediate code generation.
8. Explain different types of loop optimization techniques.
8. What do you mean by intermediate code? Explain the role of intermediate code in compiler design.
8. Explain about peephole optimization with example.
8. What do you mean by three address code? Write the syntax directed definition for following grammar to produce the three address codes for assignments
S -> id = E
E -> id
8. What is the purpose of code optimization? Explain different types of loop optimization techniques with example.
9. Discuss about different factors affecting the process of target code generation.
9. What do you mean by three-address code representation? Explain with example.
9. Discuss the issues in design of simple code generator.
9. Explain the peephole optimization. Write a three address code for the expression r:= 7*3+9.
9. Explain the principle sources of code optimization with example.
9. What are the advantages of intermediate code? Describe various representation of intermediate code.
9. Define three address codes. Write three address code for
a = -b*(c+d)
9. What is operation of simple code generator? Explain.
10. Discuss about the different factors affecting target code generation.
10. How next-use information is useful in code-generation? Explain the steps involved on computing next-use information.
10. What is three address code? Translate the expression a = b * - c + b * - c in to three address code statement.
10. Define the following optimization techniques:
a.
Unreachable code elimination
b.
Flow-of-control optimization
10. Why optimization is often required in the code generated by simple code generator? Explain the unreachable code optimization.
11. Why is it necessary to optimize code? Explain any two code optimization techniques with example.
12. Explain about the factors affecting code generation.