<< Prev | - Up - | Next >> |
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
.
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 C -> 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
.
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|T 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 = List.isPrefix
<< Prev | - Up - | Next >> |