5.3.5 The Complete Program

<Bottom Up Recognizer Program>=

<declare NewAgenda> 
<declare NewBag> 
<declare IsPrefix> 
<Grammar Rules> 
<Bottom Up Recognizer> 
<TestSuite> 
<Parse TestSuite>

The complete program also contains a simple test suite:

<TestSuite>=

local  
   S1 = [john runs]
   S2 = [man runs]
   S3 = [john sees the man]
   %% the next two tests need more time to finish
   %% as you would like to happen.
   S4 = [the man 'with' the telescope sees john]
   S5 = [john sees the man 'with' the telescope]
in 
   TestSuite = [S1 S2 S3 S4 S5]
end            

The examples in the test suite can be parsed as follows. At first sight, the parser might seem to not come back for examples 3 and 4. This is not true: it returns but needs much more time you might expect (since the algorithm used is too stupid, see below).

<Parse TestSuite>=

for 
   Sentence in TestSuite
do  
   {Inspect {Parse Sentence RULES}}
end

Here is the complete code of the bottom up recognizer, also available in file Bottom_Up_Recognizer_Program.oz:

%% maybe you want to change this URL to  
%% the appropriate local filename
 
declare URL ='http://www.ps.uni-sb.de/~niehren/Web/Vorlesungen/Oz-NL-SS01' 
declare ADS_URL = URL#'/vorlesung/Functors/Version.3.2/Abstract.ozf' 
%% load the module with the abstract data structures
declare [ADS_Module] = {Module.link [ADS_URL]}
%% select the abstract data structure for the stack  
declare NewStack = ADS_Module.newStack
%% implement agendas through stacks
declare NewAgenda = NewStack
%% implement bags through stacks
declare NewBag = NewStack
declare IsPrefix = List.isPrefix
declare RULES = [o(cat:s  subcat:[np vp])
                 o(cat:np subcat:[det n])
                 o(cat:np subcat:[pn])
                 o(cat:np subcat:[np pp])
                 o(cat:vp subcat:[vi])
                 o(cat:vp subcat:[vt np])
                 o(cat:vp subcat:[vd np np])
                 o(cat:vp subcat:[vp pp])
                 o(cat:pp subcat:[prep np])
                 o(cat:pn   subcat:[john])
                 o(cat:pn   subcat:[mary])
                 o(cat:det  subcat:[the])
                 o(cat:n    subcat:[man])
                 o(cat:vi   subcat:[runs])
                 o(cat:vt   subcat:[likes])
                 o(cat:vt   subcat:[sees])
                 o(cat:prep subcat:['with'])
                 o(cat:n    subcat:[telescope])]
fun {Parse Cats Rules}
   Bag    = {NewBag}
   Agenda = {NewAgenda}
   proc {Process}
      if {Not {Agenda.isEmpty}} then 
         Cats = {Agenda.pop}
      in 
         %% recognition rule
         case Cats of [Cat] then {Bag.push Cat} else skip end 
         %% apply all rules
         for Rule in Rules do {Infer nil Cats Rule} end 
         %% iterate
         {Process}
      end 
   end 
   proc {Infer Prefix Suffix Rule}
      %% does the rule apply here?
      if {IsPrefix Rule.subcat Suffix} then 
         %% add the conclusion to the agenda
         {Agenda.push
          {Append {Reverse Prefix}
           Rule.cat|{List.drop Suffix {Length Rule.subcat}}}}
      end 
      %% rewritings for the rest of the sequence
      case Suffix
      of nil then skip 
      [] H|T then {Infer H|Prefix T Rule}
      end 
   end 
in 
   {Agenda.push Cats}
   {Process}
   {Bag.toList}
end 
local  
   S1 = [john runs]
   S2 = [man runs]
   S3 = [john sees the man]
   %% the next two tests need more time to finish
   %% as you would like to happen.
   S4 = [the man 'with' the telescope sees john]
   S5 = [john sees the man 'with' the telescope]
in 
   TestSuite = [S1 S2 S3 S4 S5]
end             
for 
   Sentence in TestSuite
do  
   {Inspect {Parse Sentence RULES}}
end