9.2.2 Parsing with a chart

We now define the top level loop of the parsing function as follows:

<parser.oz>=

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% a passive chart parser for context free grammars
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
functor 
import 
   C(new:NewChart)        at 'chart.ozf' 
   E(make:MakeEdge)         at 'edge.ozf' 
   A(newStack:NewStack)   at 'x-ozlib://oz-kurs/Abstract.ozf' 
 
export 
   new:NewParser %% grammar x lexicon -> parser
 
   %% type word = atom
   %% type cat  = atom
   %%
   %% type rule = unit(left:cat right:list(cat))
   %% type grammar = list(rules)
   %% type lexicon = record(word:cat)
   %%
   %% type parser = list(word) -> chart(edge)    
 
define 
   fun{NewParser Rules Lexicon}
      fun{Parser Words}
         Chart = {NewChart Words}
         Agenda = {NewStack}
         <procedure Process> 
         <Words to Agenda> 
         <Process Edges> 
      in 
         Chart
      end 
   in 
      Parser
   end 
end 

We now an example for testing. We have to define a grammar, a lexicon, and sentences for testing.

<lexicon.oz>=

functor 
import 
export 
   toCat:WordToCat
define 
   LexList = [john#pn
              runs#v
              likes#v
              sees#v
              the#det
              man#n
              'with'#prep
              telescope#n]
   LexRec = {List.toRecord unit LexList}
   fun{WordToCat Word}
      LexRec.Word
   end  
end

<grammar.oz>=

functor 
import 
export 
   %% type cat = atom
   Rules %% unit(left:cat right:list(cat))
define 
   fun{MakeRule L R} unit(left:L right:R) end  
   fun{R1 C C1}    {MakeRule C [C1]}    end  
   fun{R2 C C1 C2} {MakeRule C [C1 C2]} end 
    
   Rules = [{R2 s np vp}
            {R2 np det n}
            {R2 np np pp}
            {R2 vp v np}
            {R2 vp vp pp}
            {R2 pp prep np}
            {R1 np pn}
            {R1 vp v}]
 
end 

Parse takes a list of words as input, initialises an agenda and a chart, adds lexical edges to the agenda ( Words to Agenda), process the agenda and when finished, displays the content of the resulting chart at position 1 that is, the list of edges starting in position 1.