Chapter 4

Question 1

When analyzing a program for syntactical correctness, what are the two major steps?

Answer 1

• Lexical analysis
• Syntactical analysis

Question 2

Why are these two steps usually separated?

Answer 2

• Reduce complexity
• Increase efficiency
• Allow for reuse (functions)

Question 3

What are the two major approaches to syntax analysis?

Answer 3

• Top-down parsing
• Bottom-up parsing

Question 4

What is the most common top-down parsing method? What is the short-coming of this approach?

Answer 4

Recursive descent. Limitation of leftmost recursion (A → A | B).

Question 5

What is the most common bottom-up parsing algorithm?

Answer 5

The LR (left-to-right, rightmost derivation) algorithm.