15.9.2 Non-deterministic parsing

Complete the following context--free parser by defining Reduce using either predefined choice or your own version of it. Reduce takes a list of categories and non-deterministically reduces it to a new list where reduction can result from one of 3 non-exclusive possibilities:

• The first two categories in the list can be reduced to one through application of a binary rule,

• The first category in the list can be reduced to some other category through application of a unary rule,

• The tail of the list can be reduced using one of these 3 possibilies (i.e. reduce the first two elements; reduce the first element; or reduce the tail).

 declare 
 
 fun{MakeCategory P C}
    c(phon:P cat:C)
 end 
 
 fun {BRules D1 D2}
    {Show [brules D1 D2]}
    {Browse [brules D1 D2]}
    C = case [D1.cat D2.cat]
        of [np vp] then s
        [] [det n] then np
        [] [np pp] then np
        [] [v np] then vp
        [] [vp pp] then vp
        [] [prep np] then pp
        else 
           fail unit 
        end 
 in 
   {MakeCategory {Append D1^phon D2^phon} C}  
 end 
 
 fun {URules D}
    {Show [urules D.cat]}
    {Browse [urules D.cat]}
    C= case D.cat
       of pn then np
       []  v then vp
       else 
          fail unit 
       end 
 in 
    {MakeCategory D.phon C}
 end 
 
 fun {PhonToCat Phon}
    {Show [Phon phon]}
    {Browse [Phon phon]}
    C=  case Phon
        of john then pn
        [] runs then v
        [] likes then v
        [] the then det
        [] man then n
        [] 'with' then prep
        [] telescope then n
        end 
 in 
    {MakeCategory [Phon] C}
 end 
 
 % for each word W in the input list, select corresponding lexical entries
 % Feed resulting list of lexical entries to Parse1
 
 fun {Parse Phons}
    {Parse1 {Map Phons PhonToCat}}
 end 
 
 fun {Parse1 Fs}
 %   {Browse parse1(Fs)}
    case Fs of [F] then F
    else {Parse1 {Reduce Fs}} end 
 end 
 
 proc {SParse Phon}
    {Explorer.one fun {$} {Parse Phon} end}
 end