Recursive Descent Parser for Natural Language

Input: A sentence Q and a grammar G.


The lexicon is just a list for each word of its possible parts of speech.


rdParser(in S: sentence; G: grammar; L: lexicon;
         out P: set of parse trees)
{ var T: partially complete tree;

  T = a tree with one node marked "S";
  P = null set;

rdParser1(in S: sentence; G: grammar; L: lexicon, T: partial parse tree;
          out P: set of parse trees)
{ /* Base cases of the recursion */
   if  (every leaf of T is connected to a word in S) 
      /* Note: If it reaches here, then every word in S is connected to T */
    then  { add copy(T) to P;
   if (every leaf of T is connected to a word of S, but there are words in
         S not connected to T)
      then return;
   if (there are more leaves in T than words in S) then return;

   /* Recursive case */

  N = the leftmost leaf of T not connected to a word in S;
   if  (N is a part of speech (terminal symbol))
     then { W = the leftmost unattached word in S;
            if (L marks N as a possible p.o.s for W)
              then { attach W to N in T);
              else return; 
     else  /* N is a non-terminal */
       for each  rule N -> S1 ... Sk in G
         { make S1 ... Sk the children of N in T  


S -> NP VP
NP -> Name
NP -> Noun
VP -> VG
VG -> Verb
VG -> Modal Verb

ate -- Verb
can -- Modal, Verb, Noun
fish -- Noun, Verb
John -- Name.

Sentence: John ate fish.

Trace of execution.

The trace shows the structure of the recursive calls, marked by the value of T.