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).
