8.7.3 NaiveParser.ozf: Grammatical Processing

The naïve recognizer processes sequences of categories and a rule replaces a subsequence by a single category. The naïve parser processes sequences of parser trees and replaces a subsequence of parse tree by a new parse tree constructed using the elements of this subsequence. In terms of processing, the recognizer and the parser differ in only two operations:

• First, in the way a rule determines whether it matches a subsequence. We will abstract this operation as the function IsPrefix.

• Second, in the function that maps a subsequence to its replacement. We will abstract this operation as the function MakeTree.

The standard technique for abstracting away from specific operations is to pass them as arguments. Functor NaiveParser.oz exports function MakeParser which takes 3 arguments: IsPrefix and MakeTree as described above, and Rules which is a list of grammar rules in the format:

o(cat:s subcat:[np vp])

MakeParser returns a parser, i. e. a function which takes a list of Words (a sequence of terminal categories) as input and returns the categories or parse trees (depending on MakeTree) that have been recognized.

<NaiveParser.oz>=

functor 
export MakeParser
import 
   CLO(closure:Closure) at 'x-ozlib://oz-kurs/naive/NaiveClosure.ozf' 
   ABS(newBag :NewBag ) at 'x-ozlib://oz-kurs/Abstract.ozf' 
define 
   fun {MakeParser IsPrefix MakeTree Rules}
      <NaiveParser Infer> 
      <NaiveParser MakeInferenceRule> 
      <NaiveParser Parse> 
   in 
      Parse
   end 
end

First, the Rules are converted into inference RULES appropriate for module NaiveClosure.ozf. Then Parse computes the infential closure of the initial literal Words under this set of RULES. The result of Parse is the list of conclusions which are sequences consisting of a single element (a category for the recognizer, a parser tree for the parser).

<NaiveParser Parse>=

RULES = {Map Rules MakeInferenceRule}
fun {Parse Words}
   for Cats in {Closure [Words] RULES} collect:Collect do 
      case Cats of [C] then {Collect C} else skip end 
   end 
end

Now, we must transform a grammar Rule of the form rule(cat:s subcat:[np vp]) into an inference rule, i. e., a function that takes a sequence of Cats as input and returns a list where subsequences matching the Rule.subcat list have been replaced according to Rule.cat. This list will be accumulated in a Bag and the job of recognizing matching subsequences is performed by the auxiliary procedure Infer. Notice that Infer is passed Bag.put in order to accumulate new conclusions.

<NaiveParser MakeInferenceRule>=

fun {MakeInferenceRule Rule}
   fun {$ Cats}
      Bag={NewBag}
   in 
      {Infer nil Cats Rule Bag.put}
      {Bag.toList}
   end 
end

Finally, Infer is exactly as we defined it in Section 5.4.2, except that we invoke the more abstract MakeTree rather than the specific List.toTuple.

<NaiveParser Infer>=

proc {Infer Prefix Suffix Rule PutConclusion}
   if {IsPrefix Rule.subcat Suffix} then Args Rest Tree in 
      {List.takeDrop Suffix {Length Rule.subcat} Args Rest}
      Tree = {MakeTree Rule Args}
      {PutConclusion {Append {Reverse Prefix} Tree|Rest}}
   end 
   case Suffix
   of nil then skip 
   [] H|T then {Infer H|Prefix T Rule PutConclusion}
   end 
end