6 Parsing: Bottom-Up and Top-Down

This lecture has two parts. In the first part, we

1. explain the basic idea underlying naive bottom-up parsing strategies for CFGs.

2. give a simple Prolog implementation of a naive bottom-up parser.

3. discuss the limits of this work, both implementational, and algorithmic.

In the second part, we

1. introduce two naive top-down parsing/recognition algorithms, one depth-first, the other breadth-first.

2. give the top-down depth-first recognition algorithm an efficient implementation in Prolog.

3. extend this recognizer to a parser.

Bottom-up and top-down parsing are in a way the most basic parsing strategies on the market. The more elaborate algorithms we will see later in this course can all be seen as improved versions of one of them (or a combination of both). Therefore you should make sure that you really understand how the algorithms to be presented now work. Although we sometimes stress their naivite.

• 6.1 Bottom-Up Parsing and Recognition

• 6.2 Bottom-Up Recognition in Prolog

• 6.3 An Example Run

• 6.4 How Well Have we Done?
  • 6.4.1 Implementation
  • 6.4.2 Algorithmic Problems
  • 6.4.3 [Sidetrack] Using a Chart

• 6.5 Top Down Parsing and Recognition
  • 6.5.1 The General Idea
  • 6.5.2 With Depth-First Search
  • 6.5.3 With Breadth-First Search

• 6.6 Top Down Recognition in Prolog
  • 6.6.1 The Code
  • 6.6.2 A Quick Evaluation

• 6.7 Top Down Parsing in Prolog

• 6.8 The Code

• 6.9 Practical Session
  • 6.9.1 Bottom Up
  • 6.9.2 Top Down

• 6.10 Exercises
  • 6.10.1 Bottom-Up
  • 6.10.2 Top-Down
  • 6.10.3 Midterm Project