13.2.5 A Simplistic Example

For instance the lexicon of a simplistic unification-based grammar dealing with number agreement would look like this:

<PhonToCat >=

local 
   fun{W Phon AVM} Phon#AVM end 
   Lexicon =  
   [{W john fun {$} pn(nb:sg) end}
    {W runs fun {$} v(nb:sg) end}
    {W run fun {$} v(nb:_) end}
    {W likes fun {$} v(nb:sg) end}
    {W sees fun {$} v(nb:sg) end}
    {W saw fun {$} v(nb:_) end}
    {W the fun {$} det(nb:_) end}
    {W man fun {$} n(nb:sg) end}
    {W men fun {$} n(nb:pl) end}
    {W 'with' fun {$} prep end}
    {W telescope fun {$} n(nb:sg) end}]
   LexRec = {List.toRecord lex Lexicon}
in  
   fun{PhonToCat Phon}
      LexRec.Phon
   end 
end

Similarly, the rules are encapsulated into predicates too.

<UnifBinaryRules>=

BinaryRules =
[fun {$} X in rule(left:s(nb:X)  right:[np(nb:X) vp(nb:X)]) end  
 fun {$} X in rule(left:np(nb:X) right:[det(nb:X) n(nb:X)]) end 
 fun {$} X in rule(left:np(nb:X) right:[np(nb:X) pp(nb:_)]) end 
 fun {$} X in rule(left:vp(nb:X) right:[v(nb:X) np(nb:_)]) end 
 fun {$} X in rule(left:vp(nb:X) right:[vp(nb:X) pp(nb:_)]) end 
 fun {$} X in rule(left:pp(nb:X) right:[prep np(nb:X)]) end]

<UnifUnaryRules>=

UnaryRules =
[fun {$} X in rule(left:np(nb:pl) right:[n(nb:pl)]) end  
 fun {$} X in rule(left:np(nb:sg) right:[pn(nb:sg)]) end 
 fun {$} X in rule(left:vp(nb:X)  right:[v(nb:X)]) end]

We can then re-use the chart parser developed for context-free grammars and modify it to deal with feature terms. All that needs to be done is to modify rule applications so that they produce the correct copies of categories and the appropriate results.

<ProcessBinaryUnif>=

proc{ProcessBinary Edge}
   {ForAll BinaryRules
    proc{$ Rule}
       {ForAll {Chart.get Edge.'end'}
        proc{$ RE}
           proc{BR Result}  
              X = {Rule}
              C1 = {Edge.cat}
              C2 = {RE.cat}
              [C1 C2]= X.right
           in 
              Result=X.left
           end 
           Sol = {Search.allP BR 1 _}
        in 
           case Sol
           of nil then skip 
           [] [Pred] then 
              {Agenda.push
               {NewEdge Pred Edge.begin RE.'end'}}
           end 
        end}
    end}
end

<ProcessUnaryUnif>=

proc{ProcessUnary Edge}
   {ForAll UnaryRules
    proc{$ Rule}
       proc{UR Result}  
          X = {Rule}
          C = {Edge.cat}
          [C]= X.right
       in 
          Result=X.left
       end 
       Sol = {Search.allP UR 1 _}
    in 
       case Sol
       of nil then skip 
       [] [Pred] then 
          {Agenda.push
           {NewEdge Pred Edge.begin Edge.'end'}}
       end 
    end}
end

<Unification-based Chart Parser>=

declare 
local  
% functors have to be importet
%   <edge.oz> 
%   <chart.oz> 
%   Stack  = 'to be imported
%   <lexicon.oz> 
   <UnifBinaryRules> 
   <UnifUnaryRules> 
   in 
   fun{Parse Phons}
      Chart = {NewChart Phons}
      Agenda = {NewStack}
      <procedure Process> 
     local 
         <ProcessUnaryUnif> 
         <ProcessBinaryUnif> 
      in 
         proc{Process Edge}
            {ProcessUnary Edge}
            {ProcessBinary Edge}
         end 
      end 
        <procedure Process> 
        <Words to Agenda> 
        <Process Edges> 
         
   in 
      Chart
   end 
end 
fun{Result Chart}
   {Map
    {Filter {Chart.get Chart.min}
     fun{$ E} E.'end' == Chart.max end}
    fun{$ E} {E.cat} end}
end 
 
PhonList = phonlist([john sees the man 'with' the telescope]
                    [john runs]
                    [the men runs]
                    [the men saw john]
                    [john saw the men])
 
Phons = PhonList.4
Chart={Parse Phons}
 
/*
{Chart.browse}
{Browse 'categories recognized: '# {Result Chart}}
{Browse ['cats from pos 1 to n' {Chart.get 1}]}
 
*/