This set covers the structure of a compiler and the first phase that every source program passes through: lexical analysis. You will practise counting tokens, separating tokens from lexemes and patterns, reasoning about regular expressions and finite automata, and recalling how LEX resolves matches. The questions suit GATE CSE aspirants, university semester exams in compiler construction and placement interviews that test core computer science fundamentals.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Analysis and synthesis phases of a compiler
- Tokens, lexemes and patterns
- Counting tokens and maximal munch
- Regular expressions for lexical patterns
- NFA, DFA and subset construction
- Input buffering with sentinels
- LEX conventions and conflict rules
Compiler Design MCQs with answers and explanations
Q1. Checking that the operands of the % operator in C are both integers is the responsibility of which compiler phase?
a) Lexical analysis
b) Syntax analysis
c) Semantic analysis
d) Code optimisation
Q2. How many tokens does the lexical analyser produce for the following C statement?
printf("x = %d", ++y);
a) 7
b) 9
c) 10
d) 8
Q3. Using the longest-match (maximal munch) rule of a C lexer, how many tokens are produced for the line below?
x+++y; /* add */
a) 4
b) 6
c) 7
d) 5
Q4. Which machine model is normally used to implement the token recogniser of a lexical analyser?
a) Pushdown automaton
b) Turing machine
c) Deterministic finite automaton
d) Linear bounded automaton
Q5. Which of the following errors is most naturally reported by the lexical analyser?
a) A character such as @ appearing outside a string or comment in C source
b) A missing semicolon at the end of a statement
c) Use of a variable that was never declared
d) Assigning a string to an int variable
Q6. What is the minimum number of states in a DFA over {0, 1} that accepts exactly the strings ending in 01?
a) 3
b) 2
c) 4
d) 5
Q7. Which regular expression describes all strings over {a, b} that contain at least one a?
a) a*b*
b) (a|b)*a(a|b)*
c) b*ab*
d) (ab)*
Q8. In the statement count = count + 1; the character sequence count is best described as a
a) token
b) lexeme
c) pattern
d) grammar symbol
Q9. When an NFA with n states is converted to a DFA by subset construction, what is the worst-case number of DFA states?
a) 2^n
b) n
c) n^2
d) n!
Q10. What is the main purpose of placing a sentinel character (such as eof) at the end of each buffer half in a lexical analyser?
a) To mark the end of each token in the buffer
b) To store the length of the current lexeme
c) To separate the symbol table from the input buffer
d) To combine the end-of-buffer check with the character test so most characters need only one comparison
Q11. In a LEX specification, if two rules match the same longest prefix of the input, which rule is applied?
a) The rule written later in the specification
b) The rule written earlier in the specification
c) The rule with the shorter regular expression
d) LEX reports an ambiguity error
Q12. Which LEX variable holds the number of characters in the lexeme just matched?
a) yyleng
b) yytext
c) yylval
d) yyin
Q13. Which of the following phases depends most directly on the target machine architecture?
a) Lexical analysis
b) Target code generation
c) Semantic analysis
d) Intermediate code generation
Q14. Which compiler data structure is consulted and updated by almost every phase, from lexical analysis to code generation?
a) Parse stack
b) Activation record
c) Symbol table
d) Input buffer
Q15. In Thompson's construction, building the NFA for r* from the NFA for r adds how many new epsilon transitions?
a) 4
b) 2
c) 3
d) 5
Q16. Which regular expression over {0, 1} denotes exactly the strings in which every 0 is immediately followed by a 1?
a) (01)*
b) 1*01*
c) (0|1)*01
d) (1|01)*
Q17. A compiler that runs on an x86 laptop but produces executable code for an ARM microcontroller is called a
a) decompiler
b) source-to-source translator
c) cross compiler
d) just-in-time compiler
Q18. Why is checking that parentheses are properly balanced not done by the lexical analyser?
a) Parentheses are removed during preprocessing
b) Balanced nesting needs unbounded counting, which no finite automaton can perform
c) Parentheses are not tokens
d) The lexer cannot read special characters
Quick revision notes
- Phases: lexical -> syntax -> semantic analysis -> intermediate code -> optimisation -> code generation; symbol table and error handler serve all phases.
- Token = category (id, num, relop); lexeme = actual character sequence; pattern = rule describing the lexemes of a token.
- Lexers use the longest match (maximal munch); ties go to the rule listed first in LEX.
- Comments and whitespace are discarded by the lexer and are not tokens.
- Subset construction: an n-state NFA may need up to 2^n DFA states.
- Thompson's construction adds 2 states for union and for star; star adds 4 epsilon edges.
- LEX variables: yytext (lexeme), yyleng (its length), yylval (token attribute), yyin (input file).
- Finite automata cannot count unboundedly, so nesting checks belong to the parser.
Frequently asked questions
What is the difference between a token and a lexeme?
A token is an abstract category such as identifier or number that the parser works with. A lexeme is the actual sequence of characters in the source, such as count or 42, that matches the pattern of that token.
Why is lexical analysis separated from parsing?
Separating them keeps the parser simpler, because it sees a clean stream of tokens without whitespace or comments. It also allows the lexer to use fast finite-automaton techniques and specialised buffering, which improves overall compiler speed.
Which phases of a compiler are machine dependent?
The front end (lexical, syntax and semantic analysis and intermediate code generation) is largely machine independent. Target code generation, and machine-specific optimisations such as register allocation and instruction selection, depend on the target architecture.
Comments
Post a Comment