Parsing

The ATN network in the book can be written as a context free grammar:
S -> NP Aux VP
  -> NP VP
  -> Aux NP VP
NP -> Det Adjs N PPs
   -> NPR
VP -> V NP PPs
   -> V PPs
Adjs -> Adjs Adj
     -> epsilon
PPs -> PPs PP
  -> epsilon
An ATN that can't be written as a context free grammar is:
(S/
  (PUSH NP/ T
    (SETR NP *)
    (TO S/NP)))
(S/NP
  (PUSH VP/ T
    (SETR VP *)
    (TO S/NP-VP)))
(S/NP-VP T
  (POP (BUILDQ (S + +) NP VP) (EQ (THIRD (GETR NP))
                                  (THIRD (GETR VP)))))
(NP/
  (CAT N T
     (SETR NUMBER (GETP NUMBER))
     (SETR N *)
     (TO NP/POP)))
(NP/POP
  (POP (BUILDQ (NP + +) N NUMBER) T))
(VP/
  (CAT V T
    (SETR NUMBER (GETP NUMBER))
    (SETR V *)
    (TO VP/V)))
(VP/V
  (PUSH NP/ T
    (SETR VNP *)
    (TO VP/V-POP))
  (POP (BUILDQ (VP + +) V NUMBER) T))
(VP/V-POP
  (POP (BUILDQ (VP + + +) V NUMBER VNP) T))

97-05-13, 09:45:50 MEST