9 Active Chart Parsing

This lecture consists of two parts. In the first part, we will:

1. Explain the basic ideas of active chart parsing: active edges, the fundamental rule, and the use of agendas.

2. Present a simple bottom-up active chart recognition algorithm.

3. Implement this algorithm in Prolog.

In the second part, we will:

1. Adapt the general active chart parsing algorithm introduced in the first part to work top-down.

2. Present an example of the top-down algorithm in action.

• 9.1 Active Edges

• 9.2 The Fundamental Rule

• 9.3 Using an Agenda

• 9.4 A General Algorithm for Active Chart Parsing

• 9.5 Bottom-up Active Chart Parsing
  • 9.5.1 An Example
  • 9.5.2 An Example (continued)
  • 9.5.3 Putting it into Prolog
    • findall/3
    • Representing the Arcs
    • Bottom Up Active Chart Recognition
    • Bottom Up Active Chart Recognition (continued)

• 9.6 The Code

• 9.7 Top-Down Active Chart Parsing
  • 9.7.1 Top-down rule selection
  • 9.7.2 Initializing Chart and Agenda
  • 9.7.3 An Example

• 9.8 Exercise