Theory Of Computation And Compiler Design Set 3

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Theory of Computation and Compiler Design Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation And Compiler Design Set 3

Q1 | 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
Answer: the lexical analysis of the program
Q2 | 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
Answer: Finite state automata
Q3 | Consider the following statements:(I) The output of a lexical analyzer is groups of characters.(II) Total number of tokens in printf("i=%d, &i=%x", i, &i); are 11.(III) Symbol table can be implementation by using array and hash table but not tree.Which of the following statement(s) is/are correct?
  • Only (I)
  • Only (II) and (III)
  • All (I), (II), and (III)
  • None of these
Answer: None of these
Q4 | 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.
Answer: Type checking is done before parsing.
Q5 | 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 processes by the analyzer, which one of the following is the sequence of tokens it outputs?
  • T1T2T3
  • T1T1T3
  • T2T1T3
  • T3T3
Answer: T3T3
Q6 | Consider the following statements related to compiler construction :I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct?
  • Only I
  • Only II
  • Both I and II
  • Neither I nor II
Answer: Neither I nor II
Q7 | Which of the following statement(s) regarding a linker software is/are true?I. A function of a linker is to combine several object modules into a single load module.II. A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.
  • Only I
  • Only II
  • Both I and II
  • Neither I nor II
Answer: Only I
Q8 | From the given data below : a b b a a b b a a b which one of the following is not aword in the dictionary created by LZ-coding (the initial words are a, b)?
  • a b
  • b b
  • b a
  • b a a b
Answer: b a a b
Q9 | The number of tokens in the following C statement is printf("i=%d, &i=%x",i&i);
  • 13
  • 6
  • 10
  • 9
Answer: 9
Q10 | In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction?
  • Replace P + P by 2 * P or Replace 3 + 4 by 7.
  • Replace P * 32 by P < < 5
  • Replace P * 0 by 0
  • Replace (P < <4) – P by P * 15
Answer: Replace P * 32 by P < < 5
Q11 | Debugger is a program that
  • allows to examine and modify the contents of registers
  • does not allow execution of a segment of program
  • allows to set breakpoints, execute a segment of program and display contents of register
  • All of the above
Answer: allows to set breakpoints, execute a segment of program and display contents of register
Q12 | Consider the following two sets of LR(1) items of an LR(1) grammar.X -> c.X, c/dX -> .cX, c/dX -> .d, c/dX -> c.X, $X -> .cX, $X -> .d, $Which of the following statements related to merging of the two sets in thecorresponding LALR parser is/are FALSE?1. Cannot be merged since look aheads are different.2. Can be merged but will result in S-R conflict.3. Can be merged but will result in R-R conflict.4. Cannot be merged since goto on c will lead to two different sets.
  • 1 only
  • 2 only
  • 1 and 4 only
  • 1, 2, 3, and 4
Answer: 1, 2, 3, and 4
Q13 | The grammar S ? aSa | bS | c is
  • LL(1) but not LR(1)
  • LR(1)but not LR(1)
  • Both LL(1)and LR(1)
  • Neither LL(1)nor LR(1)
Answer: Both LL(1)and LR(1)
Q14 | Which of the following statements are TRUE?I. There exist parsing algorithms for some programming languages whose complexities are less than O(n3).II. A programming language which allows recursion can be implemented with static storage allocation.III. No L-attributed definition can be evaluated in the framework of bottom-up parsing.IV. Code improving transformations can be performed at both source language and intermediate code level.
  • I and II
  • I and IV
  • III and IV
  • I, III and IV
Answer: I and IV
Q15 | Which of the following describes a handle (as applicable to LR-parsing) appropriately?
  • It is the position in a sentential form where the next shift or reduce operation will occur
  • It is non-terminal whose production will be used for reduction in the next step
  • 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
  • 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
Answer: 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
Q16 | An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if andonly if
  • the SLR(1) parser for G has S-R conflicts
  • the LR(1) parser for G has S-R conflicts
  • the LR(0) parser for G has S-R conflicts
  • the LALR(1) parser for G has reduce-reduce conflicts
Answer: the LR(1) parser for G has S-R conflicts
Q17 | Consider the following two statements:P: Every regular grammar is LL(1)Q: Every regular set has a LR(1) grammarWhich of the following is TRUE?
  • Both P and Q are true
  • P is true and Q is false
  • P is false and Q is true
  • Both P and Q are false
Answer: P is false and Q is true
Q18 | Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .EGiven the items above, which two of them will appear in the same set in the canonicalsets-of-items for the grammar?
  • (i) and (ii)
  • (ii) and (iii)
  • (i) and (iii)
  • None of the above
Answer: None of the above
Q19 | A canonical set of items is given belowS --> L. > RQ --> R.On input symbol < the set has
  • a shift-reduce conflict and a reduce-reduce conflict.
  • a shift-reduce conflict but not a reduce-reduce conflict.
  • a reduce-reduce conflict but not a shift-reduce conflict.
  • neither a shift-reduce nor a reduce-reduce conflict.
Answer: neither a shift-reduce nor a reduce-reduce conflict.
Q20 | Consider the grammar defined by the following production rules, with twooperators ? and +S --> T * PT --> U | T * UP --> Q + P | QQ --> IdU --> IdWhich one of the following is TRUE?
  • + is left associative, while ? is right associative
  • + is right associative, while ? is left associative
  • Both + and ? are right associative
  • Both + and ? are left associative
Answer: + is right associative, while ? is left associative
Q21 | Consider the following grammar:S ? FRR ? S | ?F ? idIn the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $]respectively.
  • {S ? FR} and {R ? ? }
  • {S ? FR} and { }
  • {S ? FR} and {R ? *S}
  • {F ? id} and {R ? ?}
Answer: {S ? FR} and {R ? ? }
Q22 | Consider the following translation scheme. S ? ER R ? *E{print("*");}R | ? E? F + E {print("+");} | F F ? (S) | id {print(id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints
  • 2 * 3 + 4
  • 2 * +3 4
  • 2 3 * 4 +
  • 2 3 4+*
Answer: 2 3 4+*
Q23 | The grammar A ? AA | (A) | ? is not suitable for predictive-parsing because thegrammar is
  • ambiguous
  • left-recursive
  • right-recursive
  • an operator-grammar
Answer: ambiguous
Q24 | 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
  • n1 < n2 < n3
  • n1 = n3 < n2
  • n1 = n2 = n3
  • n1 ? n3 ? n2
Answer: n1 = n3 < n2
Q25 | Consider the following expression grammar. The seman-tic rules for expressioncalculation 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).valThe 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 thefollowing is true about the action of yacc for the given grammar?
  • It detects recursion and eliminates recursion
  • It detects reduce-reduce conflict, and resolves
  • It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
  • It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
Answer: It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
Previous Next