5.3.4 Parse

The bottom up recognizer is implemented by function Parse which takes as arguments a sequence of (terminal) categories Cats and a list of Rules, and returns the list of (single) categories which have been recognized. Cats is in the language iff the returned list is non-empty. The implementation follows exactly our algorithm: the main loop is realized by the recursive local procedure Process.

<Bottom Up Recognizer>=
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 
   
<Bottom Up Infer> 
in 
   {Agenda.push Cats}
   {Process}
   {Bag.toList}
end

Infer is the function which given a sequence of categories Cats and a grammar rule Rule, produces all conclusions according to the first inference rule (see Section 5.2.1). Recall that the rule schema was:

STRING [A1 ... Ap C1 ... Cn B1 ... Bq]
RULE C -> C1 ... Cn
-------------------------------------- 
STRING [A1 ... Ap     C     B1 ... Bq]

Therefore, given a string of categories and a rule -> C1 ... Cn, we need to find all possible subsequences C1 ... Cn in our string in order to produce all possible conclusions. We do this by going through our string, and, at each step, checking if what follows matches the sequence C1 ... Cn. Therefore, at each step, our string is divided into a Prefix that we have already looked at, and a Suffix which is everything that follows and hasn't been looked at yet. For reasons of convenience and efficiency, Prefix is actually in reversed order: this is why we have {Reverse Prefix} in the code below. In order to check whether the rule is applicable to the Suffix, we simply check whether C1 ... Cn (i. e. the subcat list) is a prefix of Suffix.

<Bottom Up Infer>=
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|then {Infer H|Prefix T Rule}
   end 
end

In order to check whether Rule.subcat is a prefix of Suffix, we define the function IsPrefix. The Mozart library contains the function List.isPrefix which is exactly what we need, but, for didactic purposes, we will also ask you to implement this function in an exercise.

<declare IsPrefix>=
declare IsPrefix = List.isPrefix


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)