Draw trees to show the derivations of the following

Chapter 10, Problem 2E

(choose chapter or problem)

Problem 2E

Draw trees to show the derivations of the following sentences from the rules given in Example.

a. The young ball caught the man.

b. The man caught the young ball.

Example

A Parse Tree

In the last 30 years, Noam Chomsky and others have developed new ways to describe the syntax (or grammatical structure) of natural languages such as English. This work has proved useful in constructing compilers for high-level computer languages. In the study of grammars, trees are often used to show the derivation of grammatically correct sentences from certain basic rules. Such trees are called syntactic derivation trees or parse trees.

A very small subset of English grammar, for example, specifies that

1. a sentence can be produced by writing first a noun phrase and then a verb phrase;

2. a noun phrase can be produced by writing an article and then a noun;

3. a noun phrase can also be produced by writing an article, then an adjective, and then a noun;

4. a verb phrase can be produced by writing a verb and then a noun phrase;

5. one article is “the”;

6. one adjective is “young”;

7. one verb is “caught”;

8. one noun is “man”;

9. one (other) noun is “ball.”

The rules of a grammar are called productions. It is customary to express them using the shorthand notation illustrated below. This notation, introduced by John Backus in 1959 and modified by Peter Naur in 1960, was used to describe the computer language Algol and is called the Backus-Naur notation. In the notation, the symbol | represents the word or, and angle brackets  are used to enclose terms to be defined (such as a sentence or noun phrase).

1. (sentence) → (noun phrase) (verb phrase)

2., 3. (noun phrase) → (article) (noun) | (article) (adjective) (noun)

4. (verb phrase) → (verb) (noun phrase)

5. (article) → (the)

6. (adjective) → (young)

7, 8. (Noun) → man | ball

9. (verb) → caught

The derivation of the sentence “The young man caught the ball” from the above rules is described by the tree shown below.

In the study of linguistics, syntax refers to the grammatical structure of sentences, and semantics refers to the meanings of words and their interrelations. A sentence can be syntactically correct but semantically incorrect, as in the nonsensical sentence “The young ball caught the man,” which can be derived from the rules given above. Or a sentence can contain syntactic errors but not semantic ones, as, for instance, when a two-year-old child says, “Me hungry!”