Compiler Construction (CS-4141) -
Solved Paper
University of Sargodha
BS 7th Term Examination 2019
Subject: Computer Science
Paper: Compiler Construction (CS-4141)
Maximum Marks: 80
Time Allowed: 2:30 Hours
Objective Part (Q.1)
Write short answers (2–3 lines each):
1. i. Benefits of generating intermediate code
Intermediate code makes the compiler easier to design, provides machine-
independence, and allows easier optimization before generating final machine code.
2. ii. Difference between syntax tree and parse tree
A parse tree represents the full derivation of a string using grammar rules, while a
syntax tree is a simplified form showing only the syntactic structure.
3. iii. Code elimination
Code elimination removes useless or unreachable statements (dead code) to improve
efficiency and reduce program size.
4. iv. Parse tree for input '+ z + z ++' with grammar S → A, A → A+A | B++, B → z
A detailed diagram is required (will be inserted manually).
5. v. LL(1) Grammar check for X → YaYb | bZa; Y→ε; Z→ε
The grammar is not LL(1) because FIRST sets overlap, making it ambiguous.
6. vi. Compiler vs Interpreter
Compiler translates the whole program before execution, interpreter executes line by
line.
7. vii. Cross compiler
A cross compiler runs on one machine (host) but generates code for another machine
(target).
8. viii. Scanner vs Parser
Scanner breaks source into tokens, parser checks structure against grammar.
9. ix. Lexical analysis of: if (idx == 0) idx = 50;
Tokens: if, (, id(idx), ==, num(0), ), id(idx), =, num(50), ;
10. x. Linker
Linker combines object code modules and resolves references to create a single
executable.
11. xi. Pre-processor
Pre-processor handles macros, file inclusion, and conditional compilation before
compilation.
12. xii. Syntax analysis layer
Checks tokens against grammar rules, generating a parse/syntax tree.
13. xiii. Phase using RE & FA
Lexical analysis phase.
14. xiv. Phase using CFG
Syntax analysis (parsing) phase.
15. xv. Machine independent vs dependent optimization
Independent: code improvements not tied to hardware (dead code removal).
Dependent: optimizations using CPU features (register allocation, instruction
scheduling).
16. xvi. Ambiguous grammar
A grammar is ambiguous if a string can have more than one parse tree.
Subjective Part (Q.2–Q.6)
Q.2
a) Front-end and Back-end of Compiler:
Front-end: Performs lexical, syntax, semantic analysis, and intermediate code generation.
Produces intermediate representation.
Back-end: Performs optimizations, instruction selection, register allocation, and target code
generation.
Significance: Improves portability, separation of concerns, and optimization reuse.
b) Parse tree for 4 + 3 * 2 (Grammar: E→E+T|E-T|T, T→T*F|T/F|F, F→a|(E)):
Correct parse: 4 + (3 * 2)
Tree diagram to be inserted manually.
Q.3
Optimization of code:
Original:
a=x*2
b=3
c=x
d=c*c
e=b*2
f=a+b
g=e*f
Optimized:
b=3
a = 2*x
e=6
f = 2*x + 3
g = 12*x + 18
Dead code removed (c, d), constants folded, copy propagated, strength reduction applied.
Q.4
a) LALR(1) parsing table construction method:
Steps: Augment grammar, build LR(0) items, compute closures, transitions, add lookaheads,
then merge LR(1) states with same cores. Full ACTION/GOTO table can be generated
separately with diagrams.
b) Parse of strings bdc and daa:
Using the assumed grammar S → A a, A → bAc | Bc | bBa, B→d:
- bdc: Not derivable (string ends with c, grammar requires final 'a').
- daa: Not derivable either (productions don’t yield 'da').
If grammar had S → Aa|bAc|Bc|bBa, derivation may differ.
Q.5
First/first conflict occurs when two alternatives of a nonterminal start with the same
terminal (FIRST sets overlap). Example: A→aα | aβ. In LL parsing this creates ambiguity.
Bottom-up parsers (LR) handle more context via states, so many such grammars parse
without conflict, though shift/reduce or reduce/reduce conflicts may arise instead.
Q.6
Attribute grammar for arithmetic expressions with type checking:
Exp → Exp1 + Term
if [Link] == [Link] then [Link] = [Link]; [Link] = [Link] + [Link]
else [Link] = error
Exp → Term
[Link] = [Link]; [Link] = [Link]
Term → Term1 * Factor
if [Link] == [Link] then [Link] = [Link]; [Link] = [Link] *
[Link]
else [Link] = error
Term → Factor
[Link] = [Link]; [Link] = [Link]
Factor → (Exp)
[Link] = [Link]; [Link] = [Link]
Factor → id
[Link] = lookup(id).type; [Link] = lookup(id).val
This ensures arithmetic only on same-type operands; otherwise reports error.