1.
Introduction to Compiler
Q1. A compiler translates a high-level language program into machine code in 4 passes. If each pass takes 2 ms to
process 1000 lines, how much time will it take to compile a 5000-line program?
a) 20 ms
b) 40 ms
c) 80 ms
d) 100 ms
Answer: c) 80 ms
(Explanation: 5000 lines = 5 × 1000, time = 5 × 2 × 4 = 40 ms → Actually each pass = 10 ms, so 40 ms. Correct
answer: b) 40 ms)
2. Structure of Compiler
Q2. If lexical analysis takes 20% of compilation time, syntax analysis 30%, semantic analysis 25%, and code
generation 25%, how long will the compilation of a program take if the total compilation time is 200 ms?
a) 40 ms
b) 60 ms
c) 50 ms
d) 200 ms
Answer: d) 200 ms
(Breakdown: Lexical = 40, Syntax = 60, Semantic = 50, Code gen = 50 → Total = 200 ms)
3. Lexical Analysis
Q3. If a lexical analyzer processes 100 characters per ms, how much time will it take to scan a file of 50,000
characters?
a) 0.5 s
b) 5 s
c) 50 ms
d) 500 ms
Answer: a) 0.5 s (50,000 ÷ 100 = 500 ms = 0.5 s)
4. Role of Lexical Analyzer
Q4. Suppose a lexical analyzer generates 120 tokens from a program of 300 lexemes. What percentage of lexemes
are recognized as tokens?
a) 20%
b) 40%
c) 50%
d) 60%
Answer: b) 40% (120 ÷ 300 × 100 = 40% → correction: Answer = b) 40%)
5. Input Buffering
Q5. A buffer has size 1024 bytes. If two buffers are used in sentinel method, how many bytes can be processed in
one cycle before refill?
a) 1024
b) 512
c) 2048
d) 4096
Answer: c) 2048
6. Specification of Tokens
Q6. A programming language allows 26 keywords, 52 identifiers, and 10 operators. How many unique tokens can
be defined?
a) 62
b) 78
c) 88
d) 100
Answer: c) 88 (26 + 52 + 10 = 88)
Q1. Consider the statement:
int x = a + b * 5;
Output of lexical analyzer is
Set of regular expressions
Syntax tree
Set of tokens
Set of characters
How many tokens are present?
a) 5
b) 7
c) 8
d) 9
Answer: d) 9
*(Tokens: int, x, =, a, +, b, , 5, ; → actually 9. Correct answer: d) 9)
2.
Q2. Consider the code:
float area = 3.14 * r * r;
How many tokens are generated?
a) 7
b) 8
c) 9
d) 10
Answer: c) 9
*(Tokens: float, area, =, 3.14, *, r, , r, ;)
Which of the following error can a compiler check?
a) Syntax Error
b) Logical Error
c) Both Logical and Syntax Error
d) Compiler cannot check errors
Q3. For the statement:
if(x>=10 && y!=20) z = x + y;
How many tokens are there?
a) 10
b) 11
c) 16
d) 12
Answer: c) 16
(Tokens: if, (, x, >=, 10, &&, y, !=, 20, ), z, =, x, +, y, ; → actually 15. Correct answer: 16, not in given options.
If we adjust: correct should be d) 13 if if & brackets are considered single?)
Q4. In the program:
int main() {
int a = 5, b = 10;
int c = a + b;
return c;
}
How many tokens in total?
a) 15
b) 20
c) 22
d) 25
Answer: c) 22
(Breakdown: int, main, (, ), {, int, a, =, 5, ,, b, =, 10, ;, int, c, =, a, +, b, ;, return, c, ;, } = 24 → Correction:
actually 24 tokens. Closest = d) 25)
🔹 Numerical Compiler Questions with Token Angle
5.
Q5. If a program has 300 lexemes and lexical analyzer identifies 250 tokens, what percentage of lexemes are
recognized as tokens?
a) 60%
b) 70%
c) 80%
d) 90%
Answer: c) 80% (250 ÷ 300 × 100 = 83.3%)
6.
Q6. A Lex analyzer scans 10,000 characters and produces 1800 tokens. On average, how many characters per
token?
a) 4.5
b) 5.5
c) 6.0
d) 7.0
Answer: b) 5.5 (10000 ÷ 1800 ≈ 5.56)
7.
Q7. In a program, there are 20 keywords, 40 identifiers, 30 operators, and 10 constants. How many tokens in total?
a) 90
b) 95
c) 100
d) 110
Answer: c) 100
8.
Q8. A function contains 5 statements, each having 8 tokens. If 3 such functions exist, how many tokens in total?
a) 80
b) 100
c) 120
d) 150
Answer: c) 120 (5 × 8 × 3 = 120)
Which of the following is not a phase of a compiler?
a) Lexical Analysis
b) Code Optimization
c) Syntax Analysis
d) Assembler
Answer: d) Assembler
7. Recognition of Tokens
Q7. If a DFA has 6 states and 2 input symbols, what is the maximum number of transitions possible?
a) 6
b) 12
c) 36
d) 72
Answer: c) 36 (states × input symbols = 6 × 2 = 12 transitions/state × 3? Actually → Each state × input = 6 × 2 =
12 total transitions, not 36. Correct answer: b) 12)
8. Lex Tool
Q8. If a Lex specification file contains 8 regular expressions and each generates 3 states on average in NFA, what
will be the approximate total number of NFA states generated?
a) 11
b) 24
c) 32
d) 40
Answer: c) 24 (8 × 3 = 24)
9. Finite Automata
Q9. A DFA has 5 states. How many strings of length 2 can it accept over a binary alphabet (Σ = {0,1}), assuming
all states are accepting?
a) 4
b) 8
c) 16
d) 20
Answer: c) 4 (For length 2: 2² = 4 possible strings, all states accept → 4) Correction: Actually number of distinct
strings possible = 2² = 4, independent of DFA states. Correct answer: a) 4
An NFA has transitions:
● q0 → q1 on a
● q0 → q2 on a
● q1 → qf on b
● q2 → qf on c
Which of the following strings are accepted?
a) ab only
b) ac only
c) ab and ac
d) abc
Answer: c) ab and ac
Which is the correct order of phases in a compiler?
a) Lexical → Syntax → Semantic → Code Optimization → Code Generation
b) Syntax → Lexical → Semantic → Code Generation → Optimization
c) Semantic → Lexical → Syntax → Code Generation → Optimization
d) Lexical → Semantic → Syntax → Code Optimization → Code Generation
Answer: a) Lexical → Syntax → Semantic → Code Optimization → Code Generation
10. Minimizing DFA
Q10. A DFA has 8 states. After minimization, the number of states is reduced to 5. What percentage of states are
eliminated?
a) 20%
b) 25%
c) 37.5%
d) 50%
Answer: c) 37.5% (Eliminated = 3, 3/8 × 100 = 37.5%)
Token recognition in lexical analysis is typically implemented using:
a) Regular expressions → NFA → DFA
b) CFG → PDA
c) Turing machine
d) Syntax-directed translation
Answer: a) Regular expressions → NFA → DFA
Which of the following is NOT true about the state elimination method?
a) It can be applied to DFA, NFA, and ε-NFA.
b) Intermediate states can be eliminated in any order.
c) The final state must not have outgoing edges.
d) It can only be applied when the DFA has exactly 2 states.
Answer: d
In Lex tool, the section that contains regular expressions and actions is enclosed in:
a) %{ … %}
b) %% … %%
c) <> … <>
d) {} … {}
Answer: b) %% … %%
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 table 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.
Correct answer: C
Unit 2
1. Basics of Parsing
1. A grammar with production rules:
S → aS | b
How many leftmost derivation steps are required to derive string aaab?
a) 3
b) 4
c) 5
d) 2
Answer: b
2. If a grammar has n terminals, m non-terminals, and p productions, the maximum number of entries in a
parsing table is:
a) n × ms
b) (n+1) × m
c) (n+m) × p
d) n × p
Answer: b
3. A parser checks the syntax of a string of length n in O(n³) time. Which parser is this?
a) LL(1)
b) LR(1)
c) CYK (Cocke–Younger–Kasami)
d) Operator-precedence parser
Answer: c
Finite Automata used in lexical analysis is:
a) Non-deterministic
b) Deterministic
c) Both (converted to DFA finally)
d) Turing machine equivalent
2. Context-Free Grammars
4. Given grammar:
E → E + E | E * E | id
How many parse trees exist for input id + id * id?
a) 1
b) 2
c) 3
d) 4
Answer: b
5. For grammar S → aS | bS | ε, how many strings of length 3 can be generated?
a) 2
b) 6
c) 8
d) 9
Answer: c
6. For CFG:
S → 0S1 | 01
What is the length of the shortest string generated?
a) 1
b) 2
c) 3
d) 4
Answer: b
3. FIRST & FOLLOW Sets
7. Consider grammar:
S → AB, A → aA | ε, B → b
What is FIRST(S)?
a) {a, b}
b) {a, ε}
c) {a}
d) {a, b, ε}
Answer: a
8. For grammar:
S → aA | b, A → c | ε
FOLLOW(A) = ?
a) {a}
b) {b}
c) {$}
d) {$, b}
Answer: d
9. If grammar has 3 non-terminals and 2 terminals, the maximum number of entries in FIRST sets is:
a) 3
b) 6
c) 5
d) 8
Answer: b
4. Top-Down Parsing
10. For a predictive parser with 5 non-terminals and 6 terminals, the parsing table has:
a) 30 cells
b) 35 cells
c) 25 cells
d) 11 cells
Answer: b
11. How many table entries are filled in the LL(1) parsing table of grammar:
S → aA | b, A → c | ε ?
a) 2
b) 3
c) 4
d) 5
Answer: c
12. Given LL(1) grammar, what is time complexity of parsing a string of length n?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n³)
Answer: b
5. Bottom-Up Parsing (LR Family)
13. How many LR(0) items are possible for grammar:
S → E, E → E+T | T, T → id ?
a) 6
b) 8
c) 10
d) 12
Answer: c
14. A grammar has 2 non-terminals, 3 terminals, and 4 productions. The maximum number of items in
canonical LR(0) collection is:
a) 7
b) 9
c) 10
d) 11
Answer: b
15. Number of states in an SLR parsing table depends on:
a) Terminals only
b) Non-terminals only
c) Items in canonical collection
d) FIRST sets only
Answer: c
16. For a DFA of 6 states (in LR item construction), the ACTION and GOTO table sizes are:
a) 6 × (T+NT)
b) 12 × (T+NT)
c) 6 × T + 6 × NT
d) 6 × (T+NT+1)
Answer: a
17. A grammar has 8 LR(0) items in canonical collection and 3 terminals, 2 non-terminals. Maximum table
entries in SLR parsing table are:
a) 40
b) 50
c) 48
d) 45
Answer: a
6. LALR & Ambiguity
18. If canonical LR(1) parser has 12 states, how many states will its LALR parser have (max)?
a) 6
b) 12
c) 24
d) 8
Answer: b
19. Ambiguity in CFG means:
a) Multiple parse trees for the same string
b) No parse tree exists
c) Exactly 1 parse tree
d) Grammar is left-recursive only
Answer: a
20. In shift-reduce parsing, a reduce action replaces:
a) A non-terminal by terminal
b) RHS of production by LHS
c) Start symbol by ε
d) A non-terminal by ε
Answer: b
7. Error Handling
21. A parser detecting error at earliest is:
a) Top-down parser
b) Bottom-up parser
c) Operator precedence parser
d) CYK parser
Answer: a
22. If a string of length 6 has an error at position 3, how many shifts occur before error is detected in LR
parsing?
a) 2
b) 3
c) 6
d) 5
Answer: b
23. Panic-mode error recovery discards input symbols until:
a) End of file
b) Synchronization token
c) Start symbol appears
d) Stack is empty
Answer: b
8. YACC & Practical
24. In YACC, the number of parsing states depends on:
a) Number of productions
b) Number of tokens
c) LR item sets
d) FIRST/FOLLOW sets
Answer: c
25. If YACC grammar has 20 productions, the number of rules in [Link].c is approximately:
a) 20
b) 21
c) 40
d) 19
Answer: b
26. In YACC, shift-reduce conflict arises when:
a) Both shift and reduce actions possible
b) Both reduce actions possible
c) Grammar is unambiguous
d) Stack is empty
Answer: a
27. YACC uses which parsing algorithm?
a) LL(1)
b) LR(1)
c) Recursive descent
d) Operator precedence
Answer: b
28. If a YACC-generated parser has 30 states and 5 terminals, the ACTION table size = ?
a) 30 × 5
b) 35 × 30
c) 30 × 6
d) 150 × 2
Answer: a
29. In YACC, precedence declarations reduce:
a) Table size
b) Ambiguity
c) Shift actions only
d) Stack depth
Answer: b
30. If a grammar has 4 productions and input length is 10, maximum number of reductions in shift-reduce
parsing is:
a) 4
b) 10
c) 9
d) 11
31. Consider the following context-free grammar 𝐺, where 𝑆, 𝐴, and 𝐵 are the variables (non-terminals), 𝑎
Answer: d
and 𝑏 are the terminal symbols, 𝑆 is the start variable, and the rules of 𝐺 are described as:
𝑆 → 𝑎𝑎𝐵 | 𝐴𝑏𝑏
𝐴 → 𝑎 | 𝑎𝐴
𝐵 → 𝑏 | 𝑏𝐵
Which ONE of the languages (𝐺) is accepted by 𝐺?
𝐿(𝐺) = {𝑎2𝑏𝑛 | 𝑛 ≥ 1} ∪ {𝑎𝑛𝑏2 | 𝑛 ≥ 1}
𝐿(𝐺) = {𝑎𝑛𝑏2n | 𝑛 ≥ 1} ∪ {𝑎2𝑛𝑏𝑛 | 𝑛 ≥ 1}
A.
𝐿(𝐺) = {𝑎𝑛𝑏𝑛 | 𝑛 ≥ 1}
B.
𝐿(𝐺) = {𝑎2𝑛𝑏2𝑛 | 𝑛 ≥ 1}
C.
D.
Answer: A.
Reason:
● From S → aaB and B → b | bB we get strings aa b^n with n ≥ 1, i.e. {a^2 b^n | n ≥ 1}.
● So the language is the union: {a^2 b^n | n ≥ 1} ∪ {a^n b^2 | n ≥ 1}, which is option A.
● From S → A bb and A → a | aA we get a^m bb with m ≥ 1, i.e. {a^n b^2 | n ≥ 1}.
Consider the following deterministic finite automaton (DFA) defined over the alphabet, Σ = {𝑎, 𝑏}. Identify
which of the following language(s) is/are accepted by the given DFA.
The set of all strings containing an even number of 𝑏’s.
The set of all strings containing the pattern 𝑏𝑎𝑏.
The set of all strings ending with the pattern 𝑏𝑎𝑏.
The set of all strings not containing the pattern 𝑎𝑏𝑎.
Explanation (brief): the DFA has four states that act like a 3-symbol suffix detector:
● From the start state q0q_0q0 you go to q1q_1q1 on a b and stay on q0q_0q0 on a — so q0q_0q0 means
“no useful suffix seen”.
● q1q_1q1 means “last symbol was b”, and on a it goes to q2q_2q2 (now we have suffix ba).
● q2q_2q2 means “last two symbols are ba”, and on b it goes to the accepting state q3q_3q3 (we have suffix
bab).
● From q3q_3q3 the transitions continue so the machine always reflects the last up-to-three symbols (e.g. on
a it goes to the state for suffix ba, on b it goes to the state for suffix b), so the machine accepts exactly
those strings whose last three characters are bab.
Hence it does not accept “all strings containing bab” (a string may contain bab earlier but end with a different
suffix), and it does not characterize even number of b's or “not containing aba.”
Q32. Which of the following pairs correctly matches the tool with its purpose?
a) Lex → Syntax analysis
b) Yacc → Lexical analysis
c) Lex → Token generation
d) Yacc → Code generation
Answer: c) Lex → Token generation
Q33. In input buffering with the sentinel method, what is the advantage?
a) No need to check for buffer overflow
b) Eliminates the need for explicit end-of-buffer tests
c) Reduces token size
d) Avoids DFA construction
Answer: b) Eliminates the need for explicit end-of-buffer tests
Q34. A parser that expands the start symbol and matches input left-to-right is:
a) Bottom-up parser
b) Top-down parser
c) Shift-reduce parser
d) LR(1) parser
Answer: b) Top-down parser
Q35. Which of the following grammars is NOT context-free?
a) L = { aⁿ bⁿ | n ≥ 1 }
b) L = { aⁿ bᵐ | n,m ≥ 1 }
c) L = { aⁿ bⁿ cⁿ | n ≥ 1 }
d) L = { aⁿ bᵐ cᵏ | n,m,k ≥ 1 }
Answer: c) L = { aⁿ bⁿ cⁿ | n ≥ 1 } (requires context-sensitive grammar)
Q36. Consider grammar:
S → aA | b, A → c | ε
FIRST(S) = ?
a) {a, b}
b) {c, ε}
c) {a, b, c}
d) {a, b, c, ε}
Answer: a) {a, b}
Q37. For the same grammar above, FOLLOW(A) = ?
a) {a}
b) {b}
c) {$, b}
d) {c}
Answer: c) {$, b}
Q38. An LL(1) grammar cannot have:
a) Left recursion
b) Ambiguity
c) Left factoring problems
d) All of the above
Answer: d) All of the above
Q39. Shift-reduce parsing conflicts occur when:
a) Parser can both shift and reduce
b) Parser can reduce using two productions
c) Both (a) and (b)
d) None of these
Answer: c) Both (a) and (b)
Q40. Which parser uses items and states to build ACTION and GOTO tables?
a) LL(1) parser
b) Operator-precedence parser
c) LR parser
d) Recursive descent parser
Answer: c) LR parser
Q41. The number of LR(0) items in a grammar depends on:
a) FIRST set only
b) FOLLOW set only
c) Productions and non-terminals
d) DFA of items
Answer: d) DFA of items
Q42. In panic-mode error recovery, the parser:
a) Immediately stops compilation
b) Discards input until synchronization symbol
c) Rewrites grammar rules
d) Re-parses from the start
Answer: b) Discards input until synchronization symbol
Q43. Which type of parser detects an error earliest?
a) LL(1) parser
b) LR parser
c) Operator-precedence parser
d) CYK parser
Answer: a) LL(1) parser
Q44. Which of the following is the correct definition of a compiler?
a) A program that converts assembly to machine code
b) A program that converts source code into object code
c) A program that converts high-level language to low-level code
d) Both (b) and (c)
✅ Answer: d) Both (b) and (c)
Explanation: A compiler translates high-level programs into equivalent machine or object code. Assemblers, not
compilers, convert assembly to machine code.
Q45. The compiler phase responsible for removing left recursion belongs to:
a) Lexical Analysis
b) Syntax Analysis
c) Semantic Analysis
d) Code Optimization
✅ Answer: b) Syntax Analysis
Explanation: Left recursion is a grammar issue, handled in parsing (syntax analysis), not in lexical scanning.
Q46. Lexical analysis uses which automata?
a) PDA (Pushdown Automaton)
b) DFA (Deterministic Finite Automaton)
c) Turing Machine
d) LALR Parser
✅ Answer: b) DFA
Explanation: Regular expressions → NFA → DFA are used in lexical analyzers to recognize tokens.
Q47. In input buffering with two-buffer scheme, each buffer size = N. How many characters can be stored before
refill?
a) N
b) 2N
c) N–1
d) N+1
✅ Answer: b) 2N
Explanation: Two buffers allow sentinel technique. While one buffer is processed, the other is filled →
effectively doubles storage before refill.
Q48. Tokens are defined using:
a) Context-free grammar
b) Context-sensitive grammar
c) Regular expressions
d) Pushdown automata
✅ Answer: c) Regular expressions
Explanation: Tokens like identifiers, numbers, keywords are described by regular expressions. CFGs are used at
syntax analysis stage.
Q49. Which tool is widely used for lexical analysis?
a) YACC
b) LEX
c) GCC
d) BISON
✅ Answer: b) LEX
Explanation: LEX (or Flex) is a lexical analyzer generator that takes regular expressions as input and produces
DFA-based scanners.
Q50. Minimization of DFA reduces:
a) Tokens
b) Number of accepting states only
c) Number of states while preserving language
d) Complexity of grammar
✅ Answer: c) Number of states while preserving language
Explanation: DFA minimization merges equivalent states, ensuring the DFA remains language-equivalent but
optimized.
Q51. Syntax analysis is also called:
a) Tokenization
b) Parsing
c) Code Generation
d) Interpretation
✅ Answer: b) Parsing
Explanation: Parsing checks whether the sequence of tokens forms a syntactically valid structure (derivation
tree).
Q52. Which parser is a top-down parser?
a) LL(1) parser
b) LR parser
c) SLR parser
d) LALR parser
✅ Answer: a) LL(1) parser
Explanation: LL(1) works left-to-right, leftmost derivation. LR-based parsers are bottom-up parsers.
Q53. Which parsing technique is most powerful (can handle larger class of grammars)?
a) LL(1)
b) SLR
c) LR(0)
d) LR(1)
✅ Answer: d) LR(1)
Explanation: LR(1) parsers can recognize all deterministic context-free languages, making them more powerful
than SLR or LL(1).
Q54. In recursive descent parsing, backtracking is needed when:
a) Grammar is left-factored
b) Grammar is ambiguous
c) FIRST sets of productions overlap
d) FOLLOW set is empty
✅ Answer: c) FIRST sets of productions overlap
Explanation: If two productions for a non-terminal start with the same token, parser may need to backtrack to
decide which rule applies.
Q55. In shift-reduce parsing, reduce action means:
a) Replace LHS with RHS
b) Replace RHS with LHS
c) Shift a symbol from stack
d) Discard an input
✅ Answer: b) Replace RHS with LHS
Explanation: Reduce operation replaces the handle (RHS) of a production with its LHS non-terminal.
Q56. A grammar is ambiguous if:
a) It has more than one terminal
b) It has multiple parse trees for the same string
c) It has left recursion
d) It cannot be converted into DFA
✅ Answer: b) It has multiple parse trees for the same string
Explanation: Ambiguity means the same string can be derived in different ways (different parse trees).
Q57. Which parser is used by YACC?
a) LL(1)
b) Recursive descent
c) LR(1)
d) Operator precedence
✅ Answer: c) LR(1)
Explanation: YACC (Yet Another Compiler Compiler) generates LR(1)-based parsers.
Q58. Error handling strategy where parser skips input symbols until a synchronization point is found is called:
a) Phrase-level recovery
b) Panic-mode recovery
c) Error productions
d) Global correction
✅ Answer: b) Panic-mode recovery
Explanation: Panic mode is simple and widely used – it discards symbols until a synchronizing token (like ; or })
is reached.
Q59. Which one is not a phase of a compiler?
a) Lexical Analysis
b) Syntax Analysis
c) Assembler
d) Semantic Analysis
✅ Answer: c) Assembler
Explanation: Assembler is a separate program, not a compiler phase.
Q60. The output of the lexical analyzer is:
a) Syntax tree
b) Tokens
c) Machine code
d) Assembly code
✅ Answer: b) Tokens
Explanation: Lexical analyzer scans source code and produces tokens as output.
Q61. Which of the following is true about compiler?
a) Works line by line like interpreter
b) Translates entire program at once
c) Only checks logical errors
d) Only checks semantic errors
✅ Answer: b) Translates entire program at once
Explanation: Compiler translates full code into machine language before execution.
Q62. The phase that checks operator precedence and associativity is:
a) Lexical analysis
b) Syntax analysis
c) Semantic analysis
d) Code optimization
✅ Answer: b) Syntax analysis
Explanation: Parser ensures tokens follow grammar including precedence rules.
Q63. In compiler structure, symbol table is used to:
a) Store keywords only
b) Store identifiers, types, scope
c) Store only constants
d) Store parse tree
✅ Answer: b) Store identifiers, types, scope
Explanation: Symbol table manages all program symbols.
Q64. Input buffering improves:
a) Compilation time
b) DFA size
c) Error recovery
d) Semantic checking
✅ Answer: a) Compilation time
Explanation: Double buffering + sentinels avoid frequent I/O calls.
Q65. The smallest unit of a program recognized by a compiler is:
a) Character
b) Lexeme
c) Token
d) Statement
✅ Answer: c) Token
Explanation: Token is a meaningful unit like keyword, operator, identifier.
Q66. Regular expressions are used in compiler to specify:
a) Grammar rules
b) Tokens
c) Semantic checks
d) Code optimization
✅ Answer: b) Tokens
Explanation: Tokens are specified via regular expressions.
Q67. Which cannot be expressed by regular expressions?
a) Identifiers
b) Floating-point numbers
c) Balanced parentheses
d) Keywords
✅ Answer: c) Balanced parentheses
Explanation: Parentheses balancing requires stack → context-free grammar.
Q68. Which automata is used internally by Lex?
a) NFA
b) DFA
c) PDA
d) Turing machine
✅ Answer: b) DFA
Explanation: Lex converts regex → NFA → DFA → minimal DFA for efficiency.
Q69. The role of lexical analyzer is not:
a) Removing comments/whitespace
b) Token generation
c) Error reporting
d) Checking grammar rules
✅ Answer: d) Checking grammar rules
Explanation: Grammar checking is done in syntax analysis, not lexical.
Q70. DFA minimization ensures:
a) Same number of states as NFA
b) Smaller but equivalent DFA
c) More transitions
d) Syntax check
✅ Answer: b) Smaller but equivalent DFA
Explanation: DFA minimization merges equivalent states → compact automata.
Q71. End of file in input buffering is handled by:
a) Error recovery
b) Sentinel character
c) Null token
d) Lookahead
✅ Answer: b) Sentinel character
Explanation: Sentinel marks buffer end to avoid explicit EOF checks.
Q72. Which of the following cannot be a token?
a) Identifier
b) Keyword
c) Expression
d) Constant
✅ Answer: c) Expression
Explanation: Tokens are atomic units, not full expressions.
Q73. Which of these is not a valid compiler construction tool?
a) Lex
b) Yacc
c) GCC
d) Flex
✅ Answer: c) GCC
Explanation: GCC is a compiler, not a tool for compiler construction.
Q74. A regular expression a* generates:
a) Zero or more a’s
b) One or more a’s
c) Exactly one a
d) At least two a’s
✅ Answer: a) Zero or more a’s
Explanation: Kleene star allows empty string too.
Q75. Which is the fastest phase of a compiler?
a) Lexical analysis
b) Syntax analysis
c) Code optimization
d) Code generation
✅ Answer: a) Lexical analysis
Explanation: Token scanning is linear and very fast compared to parsing.
Q76. Tokens are divided into:
a) Keywords, identifiers, operators, literals
b) Expressions, statements, blocks
c) Declarations, loops, functions
d) None of these
✅ Answer: a) Keywords, identifiers, operators, literals
Explanation: These are the main token categories.
Q77. Which grammar type is used in lexical analysis?
a) Context-free
b) Context-sensitive
c) Regular grammar
d) Unrestricted grammar
✅ Answer: c) Regular grammar
Explanation: Tokens are described by regular grammars.
Q78. Lexical analyzer interacts with:
a) Parser
b) Symbol table
c) Error handler
d) All of the above
✅ Answer: d) All of the above
Explanation: Lexer works with parser, updates symbol table, and reports errors.
Q79. Which of the following is output of DFA minimization?
a) New tokens
b) Fewer states automata
c) Error-free grammar
d) Syntax tree
✅ Answer: b) Fewer states automata
Explanation: DFA minimization reduces states without changing language.
Q80. Syntax analysis ensures:
a) Tokens form valid grammar structure
b) Type matching
c) Runtime errors
d) Machine code generation
✅ Answer: a) Tokens form valid grammar structure
Explanation: Parser builds parse tree according to CFG.
Q81. Which is a bottom-up parser?
a) Recursive descent
b) LL(1)
c) LR(1)
d) Predictive parser
✅ Answer: c) LR(1)
Explanation: LR family works bottom-up (shift-reduce parsing).
Q82. LL(1) parser uses:
a) One lookahead symbol
b) Two lookahead symbols
c) Stack + NFA
d) DFA only
✅ Answer: a) One lookahead symbol
Explanation: LL(1) = Left to right, Leftmost derivation, 1 lookahead.
Q83. A grammar is left-recursive if it has production:
a) A → aA
b) A → Ab
c) A → aB
d) A → bA
✅ Answer: b) A → Ab
Explanation: Left recursion means non-terminal appears on LHS and first on RHS.
Q84. Recursive descent parser suffers from:
a) Ambiguity
b) Left recursion
c) DFA minimization
d) None of these
✅ Answer: b) Left recursion
Explanation: Recursive descent cannot handle left recursion.
Q85. Predictive parser requires:
a) Left factoring grammar
b) Ambiguous grammar
c) Left recursive grammar
d) Context-sensitive grammar
✅ Answer: a) Left factoring grammar
Explanation: Predictive parsing table requires distinct FIRST sets.
Q86. In shift-reduce parsing, a handle is:
a) Left-hand side of production
b) Substring matching RHS of a production
c) Rightmost non-terminal
d) None
✅ Answer: b) Substring matching RHS of a production
Explanation: Handle is reduced to LHS in shift-reduce parsing.
Q87. LR parsers are superior to LL parsers because:
a) Detect errors earlier
b) Can parse larger class of grammars
c) Need no left factoring
d) All of the above
✅ Answer: d) All of the above
Explanation: LR parsers are more powerful and error-resistant.
Q88. In SLR parsing, conflicts arise due to:
a) Large parsing table
b) FOLLOW set approximation
c) NFA conversion
d) Regular grammar
✅ Answer: b) FOLLOW set approximation
Explanation: SLR uses FOLLOW sets which sometimes cause conflicts.
Q89. LALR parser is obtained by merging states of:
a) SLR parser
b) Canonical LR(1) parser
c) Recursive descent parser
d) Operator precedence parser
✅ Answer: b) Canonical LR(1) parser
Explanation: LALR merges LR(1) states with identical cores.
Q90. YACC generates:
a) Lexical analyzer
b) LR parser
c) NFA
d) Symbol table
✅ Answer: b) LR parser
Explanation: YACC builds LALR(1) parsers from grammar rules.
Q91. Error recovery in parsers aims to:
a) Stop compilation immediately
b) Skip tokens and continue parsing
c) Generate optimized code
d) Improve semantic checks
✅ Answer: b) Skip tokens and continue parsing
Explanation: Error recovery ensures parsing continues after errors.
Q92. Panic mode is preferred because:
a) Simple and guarantees progress
b) Detects all errors
c) Produces best correction
d) Always faster than predictive parsing
✅ Answer: a) Simple and guarantees progress
Explanation: Though crude, panic mode ensures parsing does not loop forever.
Q93. A grammar is ambiguous when:
a) Tokens cannot be recognized
b) More than one parse tree for a string
c) Syntax tree is always unique
d) Parser cannot reduce
✅ Answer: b) More than one parse tree for a string
Explanation: Ambiguity = multiple parse trees possible.
Q94. Operator precedence parsing cannot handle:
a) Arithmetic operators
b) Nested parentheses
c) Non-operator grammar rules
d) Ambiguity
✅ Answer: d) Ambiguity
Explanation: Ambiguity requires grammar rewriting, not precedence.
Q95. The parsing table of LL(1) parser has dimensions:
a) Non-terminals × Terminals
b) Tokens × Productions
c) States × Tokens
d) None
✅ Answer: a) Non-terminals × Terminals
Explanation: Each non-terminal + terminal pair has a table entry.
Q96. The parsing table of LR(1) parser has dimensions:
a) Non-terminals × Terminals
b) States × (Terminals + Non-terminals)
c) States × Productions
d) None
✅ Answer: b) States × (Terminals + Non-terminals)
Explanation: LR table = ACTION (states × terminals) + GOTO (states × non-terminals).
Q97. Which parser is most commonly used in practice?
a) LL(1)
b) SLR
c) LALR(1)
d) Canonical LR(1)
✅ Answer: c) LALR(1)
Explanation: LALR(1) is efficient and powerful → used by YACC, Bison.
Q98. Which parser type is table-driven?
a) Recursive descent
b) LL(1)
c) LR
d) Both b & c
✅ Answer: d) Both b & c
Explanation: Predictive parsing (LL(1)) and LR parsing are table-driven.
Q99. Global correction error handling tries to:
a) Fix all errors automatically
b) Find closest correct program
c) Skip symbols only
d) None
✅ Answer: b) Find closest correct program
Explanation: Global correction makes minimum changes to input.
Q100. Which of the following is true about parsing?
a) Top-down starts from root, bottom-up starts from leaves
b) Both construct parse trees
c) Both work on tokens
d) All of the above
✅ Answer: d) All of the above
Explanation: Both approaches differ in strategy but achieve same goal → parse tree.