Chapter 4 : Review Question

Q6 : What is a state transition diagram?

A   : A state transition diagram, or just state diagram, is a directed graph.

Q7 : Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer?

A   : Suppose we need a lexical analyzer that recognizes only arithmetic expressions, including variable names and integer literals as operands. Assume that the variable names consist of strings of uppercase letters, lowercase letters, and digits but must begin with a letter. Names have no length limitation. The first thing to observe is that there are 52 different characters (any uppercase or lowercase letter) that can begin a name, which would require 52 transitions from the transition diagram’s initial state. However, a lexical analyzer is interested only in determining that it is a name and is not concerned with which specific name it happens to be. Therefore, we define a character class named LETTER for all 52 letters and use a single transition on the first letter of any name.

Q8 : What are the two distinct goals of syntax analysis?

A   : First, the syntax analyzer must check the input program to determine whether it is syntactically correct. The second goal of syntax analysis is to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input.

Q9 : Describe the differences between top-down and bottom-up parsers.

A   : Parsers are categorized according to the direction in which they build parse trees. The two broad classes of parsers are top-down, in which the tree is built from the root downward to the leaves, and bottom-up, in which the parse tree is built from the leaves upward to the root.

Q10 : Describe the parsing problem for a top-down parser.

A     :

1. Only judges grammaticality.

2. Stops when it finds a single derivation.

3. No semantic knowledge employed.

4. No way to rank the derivations.

5. Problems with left-recursive rules.

6. Problems with ungrammatical sentences.