7 Definite Clause Grammars

This lecture has two main goals:

1. To introduce context free grammars (CFGs) and some related concepts.

2. To introduce definite clause grammars (DCGs), an in-built Prolog mechanism for working with context free grammars (and other kinds of grammar too).

• 7.1 Context free grammars
  • 7.1.1 CFG recognition using append
  • 7.1.2 CFG recognition using difference lists

• 7.2 Definite clause grammars
  • 7.2.1 A first example
  • 7.2.2 Adding recursive rules
  • 7.2.3 A DCG for a simple formal language

• 7.3 Exercises

• 7.4 Practical Session 7