CSC376 · TU past paper
Compiler Design and Construction 2078 question paper
The complete TU 2078 exam paper for Compiler Design and Construction (CSC376), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksNumericalFinite Automata relevant to compiler constHideAnswer
List out the tasks performed by Lexical Analyser. Define DFA. Convert the Regular Expression (a+b)∗a(a+b)(a+b)^*a(a+b)(a+b)∗a(a+b) to DFA directly.[10]
- RE to convert (canonical/deduplicated form): $r = (a+b)^,a,(a+b)$ - Alphabet: $\Sigma = {a, b}$ - Marks: 10 Note: The question string repeats the pattern; the intended standard example is $(a+b)^a(a+b)$. --- 1. Scanning the source ...
- 210 marksNumericalLR parsingHideAnswer
Differentiate between LR(0) and LR(1) algorithm. Construct LR(1) parse table of the following grammar.S→AAS \rightarrow AAS→AAA→aA∣bA \rightarrow aA | bA→aA∣b[10]
S.N. LR(0) LR(1) -------------------- 1 Item has no look-ahead: form $[A \to \alpha.\beta]$ Item carries a look-ahead: form $[A \to \alpha.\beta, a]$ 2 Reductions applied on all input symbols (LR(0)/SLR use FOLLOW) Reduction applied only...
- 310 marksType Checking and ConversionHideAnswer
Define type checking. Differentiate between type casting and coercion? Write SDT to carry out type checking for the following expression. $E \rightarrow n \mid E * E \mid E == E \mid E[E] \mid E \uparrow$ [10]
--- Type checking is the process performed during semantic analysis where the compiler verifies that each operator in an expression has operands of compatible (matching) types as defined by the language specification. - It ensures that o...
- 45 marksBasic concepts related to Compiler such asHideAnswer
Define compiler and differentiate it with an interpreter. [5]
A compiler is a translator software program that takes its input in the form of a program written in a particular (high-level) programming language and produces output in the form of a program in another language (typically machine langu...
- 55 marksInformation provided by Symbol TableHideAnswer
What are the typical entries made in symbol table? Explain. [5]
A symbol table is a data structure used by compilers to hold information about source-program constructs. Information is collected incrementally by the analysis phase and used by the synthesis phase to generate target code. --- Each entr...
- 65 marksNumericalBasic parsing techniquesHideAnswer
Define Left recursive grammar. Remove left recursion from the following grammar. S→SB∣CaS \rightarrow SB | CaS→SB∣CaB→Bb∣cB \rightarrow Bb | cB→Bb∣cC→aB∣aC \rightarrow aB | aC→aB∣a[5]
Grammar productions: - $S \rightarrow SB \mid Ca$ - $B \rightarrow Bb \mid c$ - $C \rightarrow aB \mid a$ A grammar is left recursive if it contains a non-terminal $A$ such that there is a derivation $A \Rightarrow^{+} A\alpha$ for some ...
- 75 marksNumericalBottom-up parsingHideAnswer
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)∣xE \rightarrow E-E | E/E | (E) | xE→E−E∣E/E∣(E)∣x[5]
Grammar: $$E \rightarrow E - E \mid E / E \mid (E) \mid x$$ Input string: $w = (x-x).(x/x)$ Terminals visible in string: (, ), x, -, /, . Note on missing data: The grammar defines operators - and / only. The string contains a . (dot) ope...
- 85 marksAttribute TypesHideAnswer
Define attribute grammar with example of inherited and synthesized attributes. [5]
An attribute grammar (also called a Syntax-Directed Definition, SDD) is a context-free grammar together with attributes and semantic rules, where: - Attributes are associated with grammar symbols (terminals and non-terminals) - Semantic ...
- 95 marksNumericalQuadruplesHideAnswer
Define three address codes. Write down Quadruples for: $a = -b*(c+d)/e$. [5]
Three Address Code and Quadruples
STEP 1 - EXTRACT: Given Data
- Expression to translate: $a = -b * (c + d) / e$
- Required output format: Quadruples
- Also required: Definition of three address code
No numeric data is involved; this is a code-generation problem. All required information is present.
STEP 2 - SOLVE
Definition of Three Address Code
Three address code (TAC) is an intermediate representation of a program in which each statement contains at most three addresses (or operands): two for the operands and one for the result. The general form is:
$$x = y ; \text{op} ; z$$
where $x$, $y$, $z$ are names, constants, or compiler-generated temporary variables, and $\text{op}$ is an operator (arithmetic, logical, etc.). Each statement performs at most one operation, which makes it easy to translate into machine code and to optimize.
Three address code can be implemented in three ways: Quadruples, Triples, and Indirect Triples.
Breaking the Expression into Three-Address Statements
Expression: $a = -b * (c + d) / e$
Applying operator precedence (parentheses first, then unary minus, then $*$ and $/$ left to right):
Step Statement Explanation 1 $t_1 = -b$ unary minus on $b$ 2 $t_2 = c + d$ evaluate parenthesis 3 $t_3 = t_1 * t_2$ multiply 4 $t_4 = t_3 / e$ divide by $e$ 5 $a = t_4$ assign to $a$
Quadruple Representation
A quadruple has four fields: (op, arg1, arg2, result).
Index op arg1 arg2 result (0) uminusb _ $t_1$ (1) +c d $t_2$ (2) *$t_1$ $t_2$ $t_3$ (3) /$t_3$ e $t_4$ (4) =$t_4$ _ a Notes:
uminusdenotes the unary minus operator (distinguished from binary subtraction)._indicates an unused field.
Final Result
The expression $a = -b*(c+d)/e$ produces 5 quadruples using 4 temporary variables ($t_1, t_2, t_3, t_4$), matching the standard textbook decomposition.
- 105 marksRun-time storage managementHideAnswer
List out different types of run time storage management techniques. Explain any one of them. [5]
There are three main types of run-time storage management techniques: 1. Static Storage Management 2. Stack-based (Dynamic) Storage Management 3. Heap-based Storage Management --- In static storage management, memory is allocated at comp...
- 115 marksCode OptimizationHideAnswer
What is the advantages of code optimization? Explain about dead-code elimination. [5]
--- Code optimization is the process of improving intermediate code so that the output program runs faster and takes less memory space. Its main advantages are: 1. Improved Execution Speed: It arranges the sequence of statements in order...
- 125 marksCode GeneratorHideAnswer
Explain about the factors affecting target code generation. [5]
Target code generation is the final phase of compilation that translates optimized intermediate code into machine-level instructions for a specific target machine. Several factors influence how efficient and correct the generated target ...