Lexical Analysis Questions and Answers

Answer: C

All three are the standard justifications given in the literature. Simplicity, efficiency and portability together outweigh the small cost of defining an interface between the two phases. The interface is a single function call, which is about as cheap as a boundary can be.

Answer: D

The parser drives the process, requesting the next token whenever it needs one. This avoids building the entire token stream in memory and matches the way generated parsers are structured. The scanner therefore behaves as a coroutine supplying tokens on demand.

Answer: A

Precomputing the token list is a legitimate design and is used where the stream must be examined more than once. The only real cost is holding the whole list rather than one token at a time. Tools that examine a program more than once often prefer exactly this arrangement.

Answer: B

Correct answer: 156

The uncompressed table has one entry for each combination of state and input character: \[ 6 \times 26 = 156. \] The product form is why table compression matters in practice: a realistic scanner has hundreds of states over an alphabet of 128 or 256 characters, and character classes are used precisely to keep that product manageable.

Answer: C

Correct answer: 20

Thompson’s construction introduces at most two states for each symbol or operator in the expression, so an expression of 10 of them yields at most about 20 states: \[ 2 \times 10 = 20. \] The bound is linear, which is what makes the construction practical; the subsequent subset construction is what can, in the worst case, be exponential.

Answer: D

Correct answer: changes state without consuming any input character

An epsilon transition is a move the automaton may make for free, without reading anything. It is what makes Thompson’s construction so simple, since the pieces for union and closure can be joined without worrying about which character causes the join. The subset construction removes them again by working with epsilon closures.

Answer: A

Correct answer: all states reachable from them using epsilon transitions alone

The epsilon closure of a set is the set itself together with everything reachable from it by any number of epsilon moves. It is the key operation in the subset construction: since the automaton may take those moves for free at any time, it is effectively in all of those states at once, and the closure is what a single DFA state represents.

Answer: B

Each input character requires computing the moves and epsilon closure of a set of at most m states. Converting to a DFA first trades construction time for scanning that costs only order n. For a scanner run on every compilation that trade is almost always worth making.

Answer: C

The automaton makes exactly one transition per character, each a single table lookup. This linear behaviour is the reason scanners convert to a deterministic machine before scanning begins. Nondeterministic simulation would multiply that cost by the number of active states.

Answer: D

The progression trades construction effort for scanning speed and space. Scanner generators perform the whole chain once at build time so that scanning itself is as fast as possible. Construction time is paid once while scanning time is paid on every compilation.