A+ Work

PART B

I. Evaluate

a) + * 5 + * 4 7 2 3

b) * + 3 + * 2 4 7 9

c) + * + * 7 2 8 6 2

III. Given the BNF rules:

<S> ::= <NP> <VP> <DO> | <NP> <VP> <DO>

<NP> ::= <ART> <ADJ> <N> | <ART> <N>

<DO> ::= <ART><DO> | <ADJ><DO> | <N>

<VP> ::= <V> | <ADVP> <VP>

<ADVP> ::= <ADV> | <ADV> <ADVP>

<ART> ::= the | a | an

<N> ::= girl | dog | man | truck

<ADJ> ::= big | short | hairy | red

<ADV> ::= sadly | quickly | slowly

<V> ::= ran | fled | sank

a) Draw a parse tree for a sentence in this grammar which only uses a terminal once.

b) Draw a second tree which uses different options for at least two nonterminals.

The differences between this parse tree and the preceding one are shown in red pencil.

VI. Write a LISP function COUNT that finds the number of times x occurs in a list of integers.

(COUNT 7 ‘(7 5 9 7 3 6 7)) returns 3.

VII.  Write a LISP function (DIFFERENCE X Y) that returns all the elements in Y that are not in X.  (DIFFERENCE ‘(3 5 7 9) ‘(1 3 5 6 8 9)) returns (1 6 8).