A lexical analyzer uses the following token
definitions
letter → [A – Z a - z]
digit → [0 - 9]
id → letter (letter | digit)*
number → digit +
ws → (blank | tab | newline) +
For the string given below,
x1 23mm 78 y 7z zz5 14A 8H AaYcD
the number of tokens (excluding ws) that will be
produced by the lexical analyzer is __________.
(answer in integer)Compiler Design
97 questions in 4 topics. Try each one before you press "Show answer".
Lexical analysis
Which ONE of the following statements is FALSE regarding the symbol table?
- (a)Symbol table is responsible for keeping track of the scope of variables.
- (b)Symbol tables can be implemented using a binary search tree.
- (c)Symbol table is not required after the parsing phase.
- (d)Symbol table is created during the lexical analysis phase.
Consider the following two sets: P. Lexical Analyzer 1. Abstract Syntax Tree Q. Syntax Analyzer 2. Token R.Intermediate code Generator 3. Parse Tree S. Code Optimizer 4. Constant Folding Which one of the following options is the CORRECT match from Set X to Set Y?
- (a)P-4; Q-1; R-3; S-2
- (b)P-2; Q-3; R-1; S-4
- (c)P-2; Q-1; R-3; S-4
- (d)P-4; Q-3; R-2; S-1
A lexical analyzer uses the following patterns to
recognize three tokens T1, T2, and T3 over the
alphabet {a,b,c}.
T1 : a?(b|c)*a
T2 : b?(a|c)*b
T3 : c?(b|a)*c
Note that 'x?' means 0 or 1 occurrence of the symbol
x. Note also that the analyzer outputs the token that
matches the longest possible prefix. If the string
bbaacabc is processed by the analyzer, which one of
the following is the sequence of tokens it outputs?- (a)T1T2T3
- (b)T1T1T3
- (c)T2T1T3
- (d)T3T3
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: (P) Syntax Tree (i) Code Generator (Q) Character Stream (ii) Syntax Analyzer (R)Intermediate Representation (iii)Semantic Analyzer (S) Token Stream (iv) Lexical Analyzer COMPILER DESIGN
- (a)P-ii, Q-iii, R-iv, S-i
- (b)P-ii, Q-i, R-iii, S-iv
- (c)P-iii, Q-iv, R-i, S-ii
- (d)P-i, Q-iv, R-ii, S-iii
Match the following List-1 List-2 P. Lexical analysis (i)Leftmost derivation Q. Top-down parsing (ii) Type checking R. Semantic analysis (iii)Regular expressions S.Runtime environments (iv)Activation records
- (a)P-i, Q-ii, R-iv, S-iii
- (b)P-iii, Q-i, R-ii, S-iv
- (c)P-ii, Q-iii, R-i, S-iv
- (d)P-iv, Q-i, R-ii, S-iii
Match the following ? GROUP 1 GROUP 2 P. Lexical analysis 1. Graph coloring Q. Parsing 2. DFA minimization R. Register allocation 3. Post- order traversal S. Expression evaluation 4. Production Tree
- (a)P-2, Q-3, R-1, S-4
- (b)P-2, Q-1, R-4, S-3
- (c)P-2, Q-4, R-1, S-3
- (d)P-2, Q-3, R-4, S-1
In a compiler, keywords of a language are recognized during:-
- (a)Parsing of the program
- (b)the code generation
- (c)the lexical analysis of the program
- (d)dataflow analysis
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
- (a)Finite state automata
- (b)Deterministic pushdown automata
- (c)Non-Deterministic pushdown automata
- (d)Turing machine
Which data structure in a compiler is used for managing information about variables and their attributes?
- (a)Abstract syntax tree
- (b)Symbol table
- (c)Semantic stack
- (d)Parse Table COMPILER DESIGN
Match all items in Group 1 with correct options from those given in Group 2. Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
- (a)P-4. Q-1, R-2, S-3
- (b)P-3, Q-1, R-4, S-2
- (c)P-3, Q-4, R-1, S-2
- (d)P-2, Q-1, R-4, S-3
Which of the following are true? (I) A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation (II) Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions. (III) Recursion in programming languages cannot be implemented with dynamic storage allocation (IV) Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack- based allocation scheme for activation records (V) Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records.
- (a)II and V only
- (b)I, III and IV only
- (c)I, II and IV only
- (d)II, III and V only
Consider line number 3 of the following C- program.
int main ( ) { /*Line 1 */
int I, N;
/*Line 2 */
fro (I = 0, I < N, I++); /*Line 3 */
}
Identify the compiler's response about this line while
creating the object-module- (a)Both lexical and syntactic errors
- (b)Only a lexical error
- (c)Only syntactic errors
- (d)No compilation error
Consider the following C-program:
double foo (double); /* Line 1 */
int main()
{
double da, db;
// input da
db = foo(da);
}
double foo(double a)
{
return a;
}
COMPILER DESIGN- (a)no compile warning or error
- (b)some compiler-warnings not leading to unintended results
- (c)some compiler-warnings due to type- mismatch eventually leading to unintended results
- (d)compiler errors
Syntax analyzer
Which of the following statements is/are true?
- (a)LL(1) parser uses backtracking
- (b)For a grammar to be LL(1), it must be left- recursive
- (c)For a grammar to be LL(1), it must be left- factored
- (d)The LL(1) parsers are more powerful than the SLR parsers
Consider the following C statements:
char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */
Which of the following options is/are correct?- (a)S1 and S2 have syntactic errors
- (b)S2 has a lexical error and S3 has a syntactic error
- (c)S1 has a lexical error and S3 has a semantic error
- (d)S1 has a syntactic error and S3 has a semantic error
Consider the canonical LR(0) parsing of the
grammar below using terminals {a, b, c} and non-
terminals {A, B, C, S} with S as the start symbol.
S → ACB
A → aA | ε
C → cC | ε
B → bB | b
Which one of the following options gives the
number of shift-reduce conflicts that will occur in
the LR(0) ACTION table?- (a)2
- (b)3
- (c)4
- (d)5
Consider two grammars G1 and G2 with the
production rules given below:
G1: S → if E then S | if E then S else S | a
E → b
G2: S → if E then S | M
M → if E then M else S | c
E → b
where if, then, else, a, b, c are the terminals.
Which of the following option(s) is/are CORRECT?- (a)G1 is not LL(1) and G2 is LL(1).
- (b)G1 is LL(1) and G2 is not LL(1).
- (c)G1 and G2 are not LL(1).
- (d)G1 and G2 are ambiguous.
Which of the following statement(s) is/are TRUE while computing First and Follow during top-down parsing by a compiler?
- (a)For a production A→ε, ε epsilon will be added to First(A)
- (b)If there is any input right end marker, it will be added to First(S), where S is the start symbol.
- (c)For a production A→ε, ε epsilon will be added to Follow(A).
- (d)If there is any input right end marker, it will be added to Follow(S), where S is the start symbol. COMPILER DESIGN
Consider the following grammar G, with S as the
start symbol. The grammar G has three incomplete
productions denoted by (1), (2), and (3):
S → daT | (1)
T → aS | bT | (2)
R → (3) | ε
The set of terminals is {a, b, c, d, f}. The FIRST
and FOLLOW sets of the different non-terminals
are as follows:
FIRST(S) = {c, d, f}, FIRST(T) = {a, b, ε},
FIRST(R) = {c, ε}
FOLLOW(S) = FOLLOW(T) = {c, f, $},
FOLLOW(R) = {f}- (a)(1) S→Rf (2) T→ε (3) R→cTR
- (b)(1) S→fR (2) T→ε (3) R→cTR
- (c)(1) S→fR (2) T→cT (3) R→cR
- (d)(1) S→Rf (2) T→cT (3) R→cR
Which of the following is/are Bottom-Up Parser(s)
- (a)Shift-reduce Parser
- (b)Predictive Parser
- (c)LL(1) Parser
- (d)LR Parser
Consider the operator precedence and associativity
rules for the integer arithmetic operators given in
the table below.
Operator
Precedence
Associativity
+
Highest
Left
-
High
Right
*
Medium
Right
/
Low
Right
The value of the expression 3 + 1 + 5 *2/7 +
2 - 4 -7 -6/2 as per the above rules is ___Consider the augmented grammar with { +, *, (, ), id
} as the set of terminals.
S' →S
S→S+ R|R
R→R*P|P
P→(S) |id
If
I0
is
the
set
of
two
LR(0)
items
{[S'→S.],[S→S.+R]} then goto(closure (I0 ),+)
contains exactly _____ items.Which one of the following statements is TRUE?
- (a)The LALR(1) parser for a grammar G cannot have reduce – reduce conflict if the LR(1) parser for G does not have reduce – reduce conflict.
- (b)Symbol table is accessed only during the lexical analysis phase.
- (c)Data flow analysis is necessary for run-time memory management.
- (d)LR(1) parsing is sufficient for deterministic context – free languages
Consider the following context-free grammar where
the set of terminals is {a,b,c,d,f}.
S→daT|Rf
T→aS|baT|ε
R→caTR|ε
The following is a partially-filled LL(1) parsing table.
a
b
c
d
f
$
S
(1)
S →da T
(2)
T
T →a S
T →ba T
(3)
T →ε
(4)
R
R →caTR
R →ε
Which one of the following choices represents the
correct combination for the numbered cells in the
parsing table ("blank" denotes that the corresponding
cell is empty)?
COMPILER DESIGN- (a)(1) S →Rf (2) S →Rf (3) T →ε (4) T →ε
- (b)(1) blank (2) S →R (3) T →ε (4) T →ε
- (c)(1) S →Rf (2) blank (3) blank (4) T →ε
- (d)(1) blank (2) S →Rf (3) blank (4) blank
Consider the following statements. S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For any context-free grammar, there is a parser that takes at most O(n3 ) time to parse a string of length n. Which one of the following options is correct?
- (a)S1 is true and S2 is false
- (b)S1 is false and S2 is false
- (c)S1 is false and S2 is true
- (d)S1 is true and S2 is true
Consider the following grammar. S →aSB| d B →b The number of reduction steps taken by a bottom- up parser while accepting the string aaadbbb is _______.
Consider the augmented grammar given below:
S' → S
S → 〈L〉 | id
L → L, S | S
Let I0 = CLOSURE ({[S' → ·S]}). The number of
items in the set GOTO (I0 , 〈 ) is: _____.Which one of the following kinds of derivation is used by LR parsers?
- (a)Leftmost in reverse
- (b)Rightmost in reverse
- (c)Leftmost
- (d)Rightmost
Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. Which one of the following is correct for the given parse tree?
- (a)$ has higher precedence and is left associative; # is right associative
- (b)# has higher precedence and is left associative; $ is right associative
- (c)$ has higher precedence and is left associative; # is left associative
- (d)# has higher precedence and is right associative; $ is left associative
Which one of the following statements is FALSE?
- (a)Context-free grammar can be used to specify both lexical and syntax rules.
- (b)Type checking is done before parsing.
- (c)High-level language programs can be translated to different Intermediate Representations.
- (d)Arguments to a function can be passed using the program stack. COMPILER DESIGN
Which of the following statements about parser
is/are CORRECT?
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.- (a)I only
- (b)II only
- (c)III only
- (d)II and III only
Consider the following grammar:
P→xQRS
Q→yz|z
R→w|ε
S→y
What is FOLLOW(Q)?- (a){R}
- (b){w}
- (c){w, y}
- (d){w, $}
Consider the following grammar:
stmt → if expr then expr else expr; stmt|O`
expr → term relop term | term
term → id | number
id → a | b | c
number → [0-9]
where relop is a relational operator (e.g., <, >, ...),
O ` refers to the empty statement, and if, then, else
are terminals.
Consider a program P following the above
grammar containing ten if terminals. The number
of control flow paths in P is ________. For
example, the program
if e1 then e2 else e3
has 2 control flow paths, e1 → e2 and e1 → e3Consider the following expression grammar G: E → E - T | T T → T + F | F F → (E) | id Which of the following grammars is not left recursive, but is equivalent to G?
- (a)E → E – T | T T → T + F | F F → (E) | id
- (b)E →T E' E'→ – TE' | ε T → T + F | F F → (E) | id
- (c)E → TX X →–TX | ε T → FY Y → +FY | ε F → (E) | id
- (d)E → TX | (TX) X → –TX | +TX | ε T → id
Which one of the following grammars is free from left recursion?
- (a)S → AB A → Aa | b B → c
- (b)S → A b | B b | C A → Bd | ε B →e COMPILER DESIGN
- (c)S→Aa | B A→B b | Sc | ε B→ d
- (d)S→Aa | Bb | c A→B d | ε B→ d | ε
Which one of the following is True at any valid state in shift-reduce parsing?
- (a)Viable prefixes appear only at the bottom of the stack and not inside
- (b)Viable prefixes appear only at the top of the stack and not inside
- (c)The stack contains only a set of viable prefixes
- (d)The stack never contains viable prefixes
Among simple LR (SLR), canonical LR, and look- ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?
- (a)SLR, LALR
- (b)Conical LR, LALR
- (c)SLR, conical LR
- (d)LALR, conical LR
Consider the following grammar G. S → F | H F → p | c H →d | c Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(s) is/are correct? S1: LL(1) can parse all strings that are generated using grammar G. S2: LR(1) can parse all strings that are generated using grammar.
- (a)Only S1
- (b)Only S2
- (c)Both S1 and S2
- (d)Neither S1 nor S2
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is __________ ,
A canonical set of items is given below: S → L. > R Q → R. On input symbol < the set has:-
- (a)a shift-reduce conflict and a reduce-reduce conflict.
- (b)a shift-reduce conflict but not a reduce-reduce conflict.
- (c)a reduce-reduce conflict but not a shift-reduce conflict.
- (d)neither a shift-reduce nor a reduce-reduce conflict. COMPILER DESIGN
Consider the grammar defined by the following production rules, with two operators * and + S → T * P T → U | T * U P → Q + P | Q Q → Id U → Id Which one of the following is TRUE?
- (a)+ is left associative, while * is right associative
- (b)+ is right associative, while * is left associative
- (c)Both + and * are right associative
- (d)Both + and * are left associative
Consider the following two sets of LR(1) items of an LR(1) grammar. X→c. X, c/d X→ c. X, $ X-> .cX, c/d X→ .cX, $ X→ .d, c/d X→ .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look ahead is different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in RR conflict. 4. Cannot be merged since goto on c will lead to two different sets.
- (a)1 only
- (b)2 only
- (c)1 and 4 only
- (d)1, 2, 3 and 4
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon-and unit-production (i.e. of type A → ε and A → a) to parse a string with n tokens?
- (a)n/2
- (b)n–1
- (c)2n–1
- (d)2n
For the grammar below, a partial LL(1) parsing table
is also presented along with the grammar. Entries that
need to be filled are indicated as E1, E2 and E3. ε is
the empty string, $ indicates end of input, and |
separates alternate right hand sides of productions.
S → a A b B | b A a B | ε
A → S
B → S
a
b
$
S
E 1
E 2
S →ε
A
A → S
A → S
error
B
B →S
B →S
E3
The FIRST and FOLLOW sets for the non-terminals
A and B are:-
FIRST(A) = {a, b, ε} = FIRST(B)- (a)FOLLOW( A) = {a, b} FOLLOW(B) = {a, b, $}
- (b)FIRST(A) = {a, b, ε} = FIRST(B) FOLLOW(A) = {a, b} FOLLOW(B) = ∅ COMPILER DESIGN
- (c)FIRST(A) = {a, b, $} FIRST(B) = {a, b, ε} FOLLOW(A) = {a, b} FOLLOW(B) = {$}
- (d)FIRST(A) = {a, b} = FIRST(B) FOLLOW(A) = {a, b} FOLLOW(B) = {a, b}
For the grammar below, a partial LL(1) parsing
table is also presented along with the grammar.
Entries that need to be filled are indicated as E1,
E2, and E3. epsilon is the empty string, $ indicates
end of input, and, | separates alternate right hand
sides of productions.
S →a A b B | b A a B | ε
A →S
B → S
a
b
$
S
E 1
E 2
S →ε
A
A → S
A → S
error
B
B →S
B →S
E3
The appropriate entries for E1 , E2, E3 are:-- (a)E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S
- (b)E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε
- (c)E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S
- (d)E1: A → S,S →ε E2: B → S,S → ε E3: B →S
Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓ is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2) ?
- (a)
- (b)
- (c)
- (d)COMPILER DESIGN
The grammar : S → aSa|bS|c is:-
- (a)LL(1) but not LR(1)
- (b)LR(1) but not LL(1)
- (c)Both LL(1) and LR(1)
- (d)Neither LL(1) nor LR(1)
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
- (a)The SLR(1) parser for G has S-R conflicts
- (b)The LR(1) parser for G has S-R conflicts
- (c)The LR(0) parser for G has S-R conflicts
- (d)The LALR(1) parser for G has reduce-reduce conflicts
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
- (a)It is the position in a sentential form where the next shift or reduce operation will occur
- (b)It is non-terminal whose production will be used for reduction in the next step
- (c)It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur
- (d)It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found
Consider the CFG with {S, A, B} as the non-
terminal alphabet, {a,b} as the terminal alphabet, S
as the start symbol and the following set of
production rules:
S → aB S → bA
B → b A → a
B → bS A → aS
B → aBB S → bAA
Which of the following strings is generated by the
grammar?- (a)aaaabb
- (b)aabbbb
- (c)aabbab
- (d)abbbba
The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is
- (a)ambiguous
- (b)left-recursive
- (c)right-recursive
- (d)an operator-grammar
Consider the grammar
S → (S) | a
Let the number of states in SLR(1), LR(1) and
LALR(1) parsers for the grammar be n1, n2 and n3
respectively. The following relationship holds good- (a)n1 < n2 < n3
- (b)n1 = n3 < n2
- (c)n1 = n2 = n3
- (d)n1 ≥ n3 ≥ n2
Consider the context-free grammar
E → E + E
E → (E * E)
E → id
where E is the starting symbol, the set of terminals is
{id, (+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many
parse trees are possible?
COMPILER DESIGN- (a)5
- (b)4
- (c)3
- (d)2
Syntax directed translation
Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations. SDD1 Grammar (G1) Semantic Rules D→TV D.type = T.type V.type = T.type T→ int T.type = int T→ float T.type = float V→V1 id V1.type = V.type put(id.entry,V.type) V→ id put(id.entry,V.type) SDD2 Grammar (G2) Semantic Rules D→D1 id D.type = D1.type put(id.entry, D1.type ) D→T id D.type = T.type put(id.entry, T.type ) T→ int T.type = int T→ float T.type = float D is the start symbol, and int, float and id are the three terminals. The non-terminal V1 is the same as V and the non-terminal D1 is the same as D. Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function put updates the symbol table with the type information for an identifier. Let P and Q be the languages specified by grammars G1 and G2, respectively. Which of the following statements is/are true?
- (a)The languages P and Q are the same
- (b)SDD2 is S-attributed and contains only synthesized attributes
- (c)SDD1 is L-attributed and contains only inherited attributes
- (d)The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table
Given the following syntax-directed translation rules:
Rule 1:
R → AB { B.i = R.i - 1; A.i = B.i; R.i = A.i + 1; }
Rule 2:
P → CD { P.i = C.i + D.i; D.i = C.i + 2; }
Rule 3:
Q → EF { Q.i = E.i + F.i; }
Which ONE is the CORRECT option among the
following?- (a)Rule 1 : is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed
- (b)Rule 1 : is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed.
- (c)Rule 1 : is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed.
- (d)Rule 1 : is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed COMPILER DESIGN
Consider the following syntax-directed definition
(SDD)
S → D H T U { S.val = D.val + H.val + T.val + U.val; }
D → "M" D1 { D.val = 5 + D1.val; }
D → ε { D.val = -5; }
H → "L" H1 { H.val = 5 * 10 + H1.val; }
H → ε { H.val = -10; }
T → "C" T1 { T.val = 5 * 100 + T1.val; }
T → ε { T.val = -5; }
U → "K" { U.val = 5; }
Given "MMLK" as the input, which one of the
following options is the CORRECT value
computed by the SDD (in the attribute S.val)?- (a)45
- (b)50
- (c)55
- (d)60
Which of the following statements is/are FALSE?
- (a)An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects
- (b)The attributes in a L-attributed definition cannot always be evaluated in a depth- first order
- (c)Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed
- (d)All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy
Consider the syntax directed translation given by the following grammar and semantic rules. Here N,I,F and B are non-terminals. N is the starting non- terminal, and #, 0, and 1 are lexical tokens corresponding to input letters "#", "0", and "1", respectively. X.val denotes the synthesized attribute (a numeric value) associated with a non-terminal X.I1 and F1 denote occurrences of I and F on the right- hand side of a production, respectively. For the tokens 0 and 1, 0.val=0 and 1.val= 1 N → I # F N.val = I.val + F.val I → I1 B I.val = (2 I1.val) + B.val I → B I.val = B.val F → B F1 F.val = 1⁄2 (B.val + F1.val) F → B F.val = 1⁄2 B.val B → 0 B.val = 0.val B → 1 B.val = 1.val The value computed by the translation scheme for the input string: 10#011 is ____________. (Rounded off to three decimal places)
Consider the following grammar along with
translation rules.
S → S1 # T { S.val = S1.val * T.val }
S → T { S.val = T.val }
T → T1 % R { T.val = T1.val + R.val }
T → R { T.val = R.val }
R → id { R.val = id.val }
Here # and % are operators and id is a token that
represents an integer and id.val represents the
corresponding integer value. The set of non-terminals
is {S, T, R, P} and a subscripted non-terminal
indicates an instance of the non-terminal.
Using this translation scheme, the computed value of
S.val for root of the parse tree for the expression
20#10%5#8%2%2 is ______
COMPILER DESIGNConsider the following grammar (that admits a
series of declarations, followed by expressions) and
the associated syntax directed translation (SDT)
actions, given as pseudo-code:
P → D* E*
D → int ID {record that ID.lexeme is of type int}
D → bool ID {record that ID. lexeme is of type bool}
E → E1 + E2 {check that E1.type = E2.type = int;
set E.type := int}
E → !E1 {check that E1.type = bool; set E.type =
bool}
E → ID {set E.Type := int}
With respect to the above grammar, which one of
the following choices is correct?- (a)The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
- (b)The actions can be used to correctly type- check any syntactically correct program.
- (c)The actions can be used to type-check syntactically correct Boolean variable declarations and Boolean expressions
- (d)The actions will lead to an infinite loop.
Consider the following ANSI C program:
int main() {
Integer x;
return 0;
}
Which one of the following phases in a seven-phase
C compiler will throw an error?- (a)Lexical analyzer
- (b)Machine dependent optimizer
- (c)Semantic analyzer
- (d)Syntax analyzer
Consider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment. III. Errors violating the condition 'any variable must be declared before its use' are detected during syntax analysis. Which of the above statements is/are TRUE?
- (a)II only
- (b)I only
- (c)I and III only
- (d)None of I, II and III
Consider the production A ⟶ PQ and A ⟶ XY. Each of the five non-terminals A, P, Q, X and Y has two attributes:s is a synthesized attribute, and i is an inherited attribute. Consider the following rules:- Rule 1 : P.i = A.i + 2, Q.i = P.i + A.i and A.s = P.s + Q.s Rule 2 : X.i = A.i + Y.s and Y.i = X.s + A.i Which one of the following is TRUE?
- (a)Only Rule 2 is L-attributed
- (b)Neither Rule 1 nor Rule 2 is L-attributed.
- (c)Both Rule 1 and Rule 2 are L-attributed.
- (d)Only Rule 1 is L-attributed. COMPILER DESIGN
Consider the following grammar and the semantic
actions to support the inherited type declaration
attributes. Let X1, X2, X3, X4, X5 and X6 be the
placeholders for the non-terminals D, T, L or L1 in
the following table :
Production Rule
Semantic Action
D → TL
X1.type = X2.type
T → int
T.type = int
T →float
T.type = float
L → L1, id
X3.type = X4.type
addType(id.entry,
X5.type)
L → id
addType(id.entry,
X6.type)
Which one of the following are the appropriate choices
for X1, X2, X3 and X4?- (a)X1 = L, X2 = T, X3 = L1, X4 = L
- (b)X1 = T, X2 = L, X3 = L1, X4 = T
- (c)X1 = L, X2 = L, X3 = L1, X4 = T
- (d)X1 = T, X2 = L, X3 = T , X4 = L1
Consider
the
following
Syntax
Directed
Translation Scheme (SDTS), with non-terminals
{S, A} and terminals {a,b}.
S → aA { print 1 }
S → a { print 2 }
A → Sb { print 3 }
Using the above SDTS, the output printed by a
bottom-up parser, for the input aab is:- (a)1 3 2
- (b)2 2 3
- (c)2 3 1
- (d)syntax error
Consider the grammar
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-
sentential form of the reduction are- (a)n, E + n and E + n × n
- (b)n, E + n and E + E × n
- (c)n, n + n and n + n × n
- (d)n, E + n and E × n
Consider the following expression grammar. The
seman-tic rules for expression calculation are stated
next to each grammar production.
E → number
E.val = number. val
| E '+' E
E(1).val = E(2).val + E(3).val
| E '×' E
E(1).val = E(2).val × E(3).val
The above grammar and the semantic rules are fed to
a Yacc tool (which is an LALR (1) parser generator)
for parsing and evaluating arithmetic expressions.
Which one of the following is true about the action of
Yacc for the given grammar?- (a)It detects recursion and eliminates recursion
- (b)It detects reduce-reduce conflict, and resolves
- (c)It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
- (d)It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
Intermediate code generation
Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5? Note: All the variables are integers.
- (a)B4: { b + i } B5: { c + m }
- (b)B4: { g * k } B5: { c + m }
- (c)B4: { g * k, b + i } B5: { }
- (d)B4: { g * k } B5: { }
Consider the control flow graph given below. Which one of the following options is the set of live variables at the exit point of each basic block?
- (a)B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4:∅
- (b)B1:∅, B2:{d, e}, B3:{a, c, f}, B4:∅
- (c)B1:{a, b, c, e, f}, B2:{d, e}, B3:{c, e, f}, B4:∅
- (d)B1:∅, B2:{d, e, f}, B3:{a, b, c, e, f}, B4:∅
Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expressions in one pass. (II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?
- (a)Only (I) is correct.
- (b)Only (II) is correct.
- (c)Both (I) and (II) are correct.
- (d)Neither (I) nor (II) is correct. COMPILER DESIGN
Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is _________. 1001: i = 1 1002: j = 1 1003: t1 = 10*i 1004: t2 = t1+j 1005: t3 = 8*t2 1006: t4 = t3-88 1007: a[t4] = 0.0 1008: j = j+1 1009: if j <= 10 goto 1003 1010: i = i+1 1011: if i <= 10 goto 1002 1012: i = 1 1013: t5 = i-1 1014: t6 = 88*t5 1015: a[t6] = 1.0 1016: i = i+1 1017: if i <= 10 goto 1013
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- (a)Run-time function call management
- (b)Register assignment to variables
- (c)Strength reduction
- (d)Constant folding
Consider the following expression: x[i] = (p + r) *-s[i] + u/w (0) + p r (1) (2) uminus (1) (3) (4) / u w (5) + (3) (4) (6) (7) = (6) (5) Which one of the following options fills in the missing entries CORRECTLY?
- (a)(1) = []si, (3) *(0)(2), (6)[] = xi
- (b)(1)[] = si, (3) -(0)(2), (6) = []x(5)
- (c)(1) = []si, (3) *(0)(2), (6)[] = x(5)
- (d)(1)[] = si, (3) -(0)(2), (6) = []xi
Consider the following pseudo-code. L1 : t1 = -1 L2 : t2 = 0 L3 : t3 = 0 L4 : t4 = 4 * t3 L5 : t5 = 4 * t2 L6 : t6 = t5 * M L7 : t7 = t4 + t6 L8 : t8 = a[t7] L9 : if t8 <= max goto L11 L10 : t1 = t8 L11 : t3 = t3 + 1 L12 : if t3 < M goto L4 L13 : t2 = t2 + 1 L14 : if t2 < N goto L3 L15 : max = t1 Which of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively? COMPILER DESIGN
- (a)6 and 6
- (b)6 and 7
- (c)7 and 7
- (d)7 and 6
Consider the following statements regarding the front-end and back-end of a compiler: - S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are specific to the target hardware. S3: The back-end includes phases that are specific to the programming language used in the source code. Identify the CORRECT option.
- (a)Only S1 is TRUE.
- (b)Only S1 and S2 are TRUE.
- (c)S1, S2, and S3 are all TRUE.
- (d)Only S1 and S3 are TRUE.
For a statement S in a program, in the context of liveness analysis, the following sets are defined: USE (S) : the set of variables used in S IN (S) : the set of variables that are live at the entry of S OUT(S) : the set of variables that are live at the exit of S Consider a basic block that consists of two statements, S1 followed by S2. Which one of the following statements is correct?
- (a)OUT(S1) = IN(S1) ∪ USE(S1)
- (b)OUT(S1) = IN(S2) ∪ OUT(S2)
- (c)OUT(S1) = IN(S2)
- (d)OUT(S1) = USE(S1) ∪ IN(S2)
In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
- (a)Three address code
- (b)Control Flow Graph (CFG)
- (c)Abstract Syntax Tree (AST)
- (d)Symbol table
Consider the expression ( a-1)* (((b + c) / 3) + d) . Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture in which (i) only loads and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is _________.
Consider the following code segment. x = u - t; y = x * v; x = y + w; y = t - z; y = x * y; The minimum number of variables required to convert the above code segment to static single assignment form is ________.
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE? COMPILER DESIGN
- (a)In both AST and CFG, let node N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding in N1.
- (b)For any input program, neither AST nor CFG will contain a cycle
- (c)The maximum number of successors of a node in an AST and a CFG depends on the input program
- (d)Each node is AST and CFG corresponds to at most one statement in the input program.
Consider the intermediate code given below. (1) i = 1 (2) j = 1 (3) t1 = 5 * i (4) t2 = t1 + j (5) t3 = 4 * t2 (6) t4 = t3 (7) a[t4] = –1 (8) j = j + 1 (9) if j < = 5 goto (3) (10) i = i + 1 (11) if i < 5 goto (2) The number of nodes and edges in the control-flow- graph constructed for the above code, respectively, are:-
- (a)5 and 7
- (b)6 and 7
- (c)5 and 5
- (d)7 and 8
The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r/3 + s – t * 5 + u * v/w is _________.
One of the purposes of using intermediate code in compilers is to:-
- (a)make parsing and semantic analysis simpler.
- (b)improve error recovery and error reporting.
- (c)increases the chances of reusing the machine- independent code optimizer in other compilers.
- (d)improve the register allocation
Which one of the following is FALSE?
- (a)A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
- (b)Available expression analysis can be used for common subexpression elimination.
- (c)Live variable analysis can be used for dead code elimination.
- (d)x=4*5⇒x=20 is an example of common subexpression elimination
Which one of the following is NOT performed during compilation?
- (a)Dynamic memory allocation
- (b)Type checking
- (c)Symbol table management
- (d)Inline expansion
For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits. t0 = i * 1024 t1 = j * 32 t2 = k * 4 t3 = t1 + t0 COMPILER DESIGN t4 = t3 + t2 t5 = x[t4] Which one of the following statements about the source code for the C program is CORRECT?
- (a)X is declared as "int X[32][32][8]".
- (b)X is declared as "int X[4][1024][32]".
- (c)X is declared as "char X[4][32][8]".
- (d)X is declared as "char X[32][16][2]".
Which of the following statements are Correct? 1. Static allocation of all data areas by a compiler makes it impossible to implement recursion. 2. Automatic garbage collection is essential to implement recursion. 3. Dynamic allocation of activation records is essential to implement recursion. 4. Both heap and stack are essential to implement recursion.
- (a)1 and 2 only
- (b)2 and 3 only
- (c)3 and 4 only
- (d)1 and 3 only
Consider the basic block given below. a= b + c c =a + d d =b + c e =d - b a =e + b The minim um number of nodes and edges present in the DAG representation of the above basic block respectively are
- (a)6 and 6
- (b)8 and 10
- (c)9 and 12
- (d)4 and 4
The minimum number of arithmetic operations required to evaluate the polynomial P(x) = x5 + 4x3 + 6x + 5 for a given value of x, using only one temporary variable is ____ .
The following code segment is executed on a
processor which allows only register operands in its
instructions. Each instruction can have almost two
source operands and one destination operand.
Assume that all variables are dead after this code
segment.
c = a + b;
d = c *a;
e = c + a;
x = c *c;
if (x > a){
y = a*a;
}
else {
d = d * d;
e = e*e;
}
Suppose the instruction set architecture of the
processor has only two registers. The only allowed
compiler optimization is code motion, which
moves statements from one place to another while
preserving correctness. What is the minimum
number of spills to memory in the compiled code?- (a)0
- (b)1
- (c)2
- (d)3 COMPILER DESIGN
Consider the program given below, in a block-
structured pseudo-language with lexical scoping
and
nesting of procedures permitted.
Program main;
Var ...
Procedure A1;
Var ...
Call A2;
End A1
Procedure A2;
Var ...
Procedure A21;
Var
Call A1;
End A21
Call A21;
End A2
Call A1;
End main.
Consider the calling chain: Main → A1 → A2 →
A21 → A1
The correct set of activation records along with
their access links is given by- (a)
- (c)
- (d)
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e initially stored in memory. The binary operators used in this expression tree can be evaluate by the machine only when the operands are in registers. The instructions produce results only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression? (b) COMPILER DESIGN
- (a)2
- (b)9
- (c)5
- (d)3
The program below uses six temporary variables a, b, c, d, e, f. a = 1 b = 10 c = 20 d = a+b e = c+d f = c+e b = c+e e = b+f d = 5+e return d+f Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
- (a)2
- (b)3
- (c)4
- (d)6
Which languages necessarily need heap allocation in the runtime environment?
- (a)Those that support recursion
- (b)Those that use dynamic scoping
- (c)Those that allow dynamic data structures
- (d)Those that use global variables
Consider the following C code segment.
for (i = 0; < i< n; i++)
{
for (j=0; j< n; j++)
{
if (i%2)
{
x += (4*j + 5*i);
y += (7 + 4*j);
}
}
}
Which one is false?- (a)The code contains loop-in variant computation
- (b)There is scope of common sub-expression elimination in this code
- (c)There is scope strength reduction in this code
- (d)There is scope of dead code elimination in this code
Some code optimizations are carried out on the intermediate code because
- (a)They enhance the portability of the compiler to other target processors
- (b)Program analysis is more accurate on intermediate code than on machine code
- (c)The information from dataflow analysis cannot otherwise be used for optimization
- (d)The information from the front end cannot otherwise be used for optimization COMPILER DESIGN