5 Context Free Grammars

This lecture has four goals:

1. To recapitulate some basic concepts of Context Free Grammars.

2. To review Prolog's built-in DCG mechanism and to show how Context Free Grammars can directly be formulated as DCGs.

3. To show that the inbuilt feature-passing mechanism of DCGs enables them to handle long distance dependencies. We first give a rather naive DCG for simple English relative clauses, and then show how the gap-threading technique can be used to improve it.

4. To discuss the good and bad points of DCGs, and set the stage for our later work with grammars and features.

• 5.1 Context Free Grammars
  • 5.1.1 The Basics
  • 5.1.2 The Tree Admissibility Interpretation
  • 5.1.3 A Little Grammar of English

• 5.2 DCGs
  • 5.2.1 DCGs are a natural notation for context free grammars
  • 5.2.2 DCGs are really Syntactic Sugar for Difference Lists
  • 5.2.3 DCGs give us a Natural Notation for Features

• 5.3 DCGs for Long Distance Dependencies
  • 5.3.1 Relative Clauses
  • 5.3.2 A First DCG
  • 5.3.3 A Second DCG
  • 5.3.4 Gap Threading
  • 5.3.5 Questions
  • 5.3.6 Occurs-Check

• 5.4 Pros and Cons of DCGs

• 5.5 The Complete Code

• 5.6 Exercises