«up»

Context Free Grammars

Abstract:
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.

Table of Contents

Context Free Grammars
Let's begin by going through some basic ideas about context-free grammars. We will start by using little grammars that generate simple formal languages. In the end of this section, we will see a somewhat larger grammar for a fragment of English we will work with later in this course.

DCGs
Now you have seen some examples of CFGs including a grammar for a fragment of English. Before we go about building parsers that use this grammar, let us pause for a moment and see what Prolog's built in ↗Definite Clause Grammar s (DCGs) can do for us. Although DCGs are formally more powerful than CFGs, we can easily use the DCG mechanism to deal with CFGs like the ones we have seen before.Note that what follows is not intended as a complete introduction (for that, see any decent Prolog textbook). It's simply meant to remind you of some basic aspects of DCG notation, and how DCGs can be used in our context.

DCGs for Long Distance Dependencies
Context free rules work locally. For example, the rule S→NPVP tells us how an S can be decomposed into two parts, and NP and a VP. But certain aspects of natural language seem to work in a non-local, long-distance way. Indeed, for a long time it was thought that such phenomena meant that grammar-based analyses had to be replaced by very powerful new mechanisms (such as the transformations used in transformational grammar). In fact, a surprising amount can be done by using grammars enriched in a fairly restricted way: namely, by the addition of features. Now, we've already discussed the use of features to deal with simple facts of case, but it turns out that features can do a lot more work for us. In particular, they do make it possible to give grammar-based analyses of many long distance phenomena. We're now going to discuss a central long distance phenomenon (namely, English relative clauses) and show that DCGs enable us to give a rather neat feature-based analysis of such phenomena. The technique we are going to use is called ↗threading . We will then use the same technique for an analysis of English wh-questions.

Pros and Cons of DCGs
How good are DCGs?

The Complete Code
Code Summary for this Chapter.


Exercise

  1. In the text (???» A Second DCG#13) we claimed that the DCG found in dCG4Gaps2.pl gives two distinct analyses of The witch gave the house-elf to Harry.
    1. Design a Prolog query to verify this observation.
    2. Explain why there are two analyses.
  2. Extend the gap-threading DCG (dCG4Gaps2.pl ) so that it handles the English relative pronouns that and which, adjectives, and subject-verb agreement.
  3. [This is a possible mid-term project.]
    Write a DCG that handles the basic facts of German relative clauses. Your DCG should correctly handle basic facts about agreement, case, and German word order in relative clauses.
«up»