Compilers
Question 1 |
Which one of the following statements is FALSE?
Context-free grammar can be used to specify both lexical and syntax rules. | |
Type checking is done before parsing. | |
High-level language programs can be translated to different Intermediate Representations. | |
Arguments to a function can be passed using the program stack. |
Question 1 Explanation:
Type checking is done in semantic analysis phase after syntax analysis phase (i.e., after parsing).
Question 2 |
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.
1: a?(b∣c)*aT
2: b?(a∣c)*bT
3: 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 processes by the analyzer, which one of the following is the sequence of tokens it outputs?
1: a?(b∣c)*aT
2: b?(a∣c)*bT
3: 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 processes by the analyzer, which one of the following is the sequence of tokens it outputs?
T1T2T3 | |
T1T1T3 | |
T2T1T3 | |
T3T3 |
Question 2 Explanation:
a? means either 0 or 1 occurrence of “a”, so we can write T1, T2 and T3 as:
T1 : (b+c)*a + a(b+c)*a
T2 : (a+c)*b + b(a+c)*b
T3 : (b+a)*c + c(b+a)*c
Now the string is: bbaacabc
Please NOTE:
Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T3.
After prefix we left with “abc” which is again generated by T3 (as longest possible prefix).
So, answer is T3T3.
T1 : (b+c)*a + a(b+c)*a
T2 : (a+c)*b + b(a+c)*b
T3 : (b+a)*c + c(b+a)*c
Now the string is: bbaacabc
Please NOTE:
Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T3.
After prefix we left with “abc” which is again generated by T3 (as longest possible prefix).
So, answer is T3T3.
Question 3 |
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:
P→(ii), Q→(iii), R→(iv), S→(i) | |
P→(ii), Q→(i), R→(iii), S→(iv) | |
P→(iii), Q→(iv), R→(i), S→(ii) | |
P→(i), Q→(iv), R→(ii), S→(iii) |
Question 3 Explanation:
Character stream is input to lexical analyzer which produces tokens as output. So Q → (iv).
Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, S → (ii).
Syntax tree is the input for the semantic analyzer, So P → (iii).
Intermediate representation is input for Code generator. So R → (i).
Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, S → (ii).
Syntax tree is the input for the semantic analyzer, So P → (iii).
Intermediate representation is input for Code generator. So R → (i).
Question 4 |
Match the following:
(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
P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii | |
P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv | |
P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv | |
P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii |
Question 4 Explanation:
Regular expressions are used in lexical analysis.
Top down parsing has left most derivation of any string.
Type checking is done in semantic analysis.
Activation records are loaded into memory at runtime.
Top down parsing has left most derivation of any string.
Type checking is done in semantic analysis.
Activation records are loaded into memory at runtime.
Question 5 |
Match the following:
(P) Lexical analysis (1) Graph coloring (Q) Parsing (2) DFA minimization (R) Register allocation (3) Post-order traversal (S) Expression evaluation (4) Production tree
P-2, Q-3, R-1, S-4 | |
P-2, Q-1, R-4, S-3 | |
P-2, Q-4, R-1, S-3 | |
P-2, Q-3, R-4, S-1 |
Question 5 Explanation:
P) Lexical analysis is related with FA and Regular expressions.
Q) Expression can be evaluated with postfix traversals.
R) Register allocation can be done by graph colouring.
S) The parser constructs a production tree.
Hence, answer is ( C ).
Q) Expression can be evaluated with postfix traversals.
R) Register allocation can be done by graph colouring.
S) The parser constructs a production tree.
Hence, answer is ( C ).
Question 6 |
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?
Finite state automata | |
Deterministic pushdown automata | |
Non-Deterministic pushdown automata | |
Turing machine |
Question 6 Explanation:
Lexical Analysis is implemented by finite automata.
Question 7 |
In a compiler, keywords of a language are recognized during
parsing of the program | |
the code generation | |
the lexical analysis of the program | |
dataflow analysis |
Question 7 Explanation:
Any identifier is also a token so it is recognized in lexical Analysis.
Question 8 |
Which data structure in a compiler is used for managing information about variables and their attributes?
Abstract syntax tree | |
Symbol table | |
Semantic stack | |
Parse Table |
Question 8 Explanation:
Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the analysis phases of a compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its character string (or lexeme) , its type, its position in storage, and any other relevant information.
Question 9 |
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
P-4, Q-1, R-2, S-3
| |
P-3, Q-1, R-4, S-2 | |
P-3, Q-4, R-1, S-2 | |
P-2, Q-1, R-4, S-3
|
Question 9 Explanation:
Lexical analysis phase uses regular expression to identify the pattern of tokens, PDA is used in CFG and hence syntax analysis phase is related to PDA. Data flow analysis is done in code optimization phase and register allocation is related to code generation phase.
Question 10 |
Some code optimizations are carried out on the intermediate code because
They enhance the portability of the compiler to other target processors | |
Program analysis is more accurate on intermediate code than on machine code
| |
The information from dataflow analysis cannot otherwise be used for optimization | |
The information from the front end cannot otherwise be used for optimization |
Question 10 Explanation:
The code-optimization on intermediate code generation will always enhance the portability of the compiler to target processors. The main reason behind this is, as the intermediate code is independent of the target processor on which the code will be executed, so the compiler is able to optimize the intermediate code more conveniently without bothering the underlying architecture of target processor.
Question 11 |
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:
No compilation error
| |
Only a lexical error | |
Only syntactic errors | |
Both lexical and syntactic errors |
Question 11 Explanation:
There is no error in the above code. Actually it is a link error. Here compiler fro is a function which is not declared. Hence, it will not produce any error. It will only throw a warning in C.
There are 11 questions to complete.