Lexical Analysis Questions and Answers

Answer: A

Correct answer: group the input characters into lexemes and produce tokens

The scanner is the compiler’s first phase and its job is purely one of recognition: read the character stream, decide where one lexeme ends and the next begins, and hand the parser a stream of tokens with their attributes. Checking the grammar belongs to the parser, type checking to semantic analysis, and instruction selection to the back end.

Answer: B

Correct answer: A-2, B-4, C-1, D-3

The four terms name four different things and the distinction is worth fixing. A token is the category name the parser sees, such as id or number. A pattern is the rule describing what form a lexeme of that category may take. A lexeme is the actual run of characters matched. And the attribute is the extra information carried along with the token, such as a symbol table pointer.

Answer: C

Correct answer: five, counting each identifier, operator and literal separately

The lexemes are count, =, count, + and 1 - five in all. The identifier count appears twice and is counted twice, because a lexeme is an occurrence in the input rather than a distinct name; the two occurrences produce two tokens that happen to carry a pointer to the same symbol table entry.

Answer: D

Correct answer: a pointer to the symbol table entry for that identifier

The token itself carries only the category id, which is all the parser needs, and the attribute carries a pointer to the symbol table entry where the name, type, scope and everything else about the identifier is recorded. Storing the value or the address in the token would be impossible at this stage, since neither has yet been determined.

Answer: A

Correct answer: regular expressions

Token patterns are exactly the kind of thing regular expressions describe: identifiers, numbers, operators and keywords are all regular languages, and a regular expression can be turned mechanically into the automaton that recognises it. Context free grammars are needed for the nested structure the parser handles, and are more machinery than the scanner requires.

Answer: B

Correct answer: a sequence of named regular expressions where each may use earlier names

A regular definition lets a specification be built up in readable stages - define digit, then digits in terms of it, then number in terms of that. The restriction that a name may only use names defined earlier is what keeps the whole thing regular: allow a definition to refer to itself and you have a grammar, not a regular expression.

Answer: C

The closure matches any prefix over the alphabet and the literal abb must follow it. Any string ending in abb is therefore accepted, and any string not ending that way is rejected. This expression is the standard worked example in every treatment of the subject.

Answer: D

Correct answer: 4

The automaton must remember how much of abb has been seen so far, which gives four conditions: nothing yet, an a seen, ab seen, and abb seen. Those are the four states, the last being accepting. No two of them can be merged, because from each a different continuation is needed to reach acceptance, so four is also the minimum.

Answer: A

The star operator includes the empty string, since zero occurrences are permitted. The plus operator denotes one or more, so r plus is equivalent to r concatenated with r star. Both forms appear in specifications and the generator treats them interchangeably.

Answer: B

One or more occurrences means one occurrence followed by zero or more. The essential difference from r star is that r plus excludes the empty string. That distinction matters when a pattern must not be allowed to match nothing at all.