| << Prev | - Up - | Next >> |
oz-kurs-chart.pkg is a package containing the entire code for the passive chart parsing library. You can install this package as follows:
ozmake --install --package=oz-kurs-chart.pkg All functors in this library are made available at URI x-ozlib://oz-kurs/chart. For the exercise, you will also need the sources which you can extract from the package file as follows:
ozmake --extract --package=oz-kurs-chart.pkgFor your browsing convenience, here is the source of the parser:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% a passive chart parser for context free grammars
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
functor
import
C(new:NewChart) at 'chart.ozf'
E(make:MakeEdge) at 'edge.ozf'
A(newStack:NewStack) at 'x-ozlib://oz-kurs/Abstract.ozf'
export
new:NewParser %% grammar x lexicon -> parser
%% type word = atom
%% type cat = atom
%%
%% type rule = unit(left:cat right:list(cat))
%% type grammar = list(rules)
%% type lexicon = record(word:cat)
%%
%% type parser = list(word) -> chart(edge)
define
fun{NewParser Rules Lexicon}
fun{Parser Words}
Chart = {NewChart Words}
Agenda = {NewStack}
%% Match tests whether there exists a list of subsequent
%% edges [Edge E2 ... En] with categories matching those
%% in Rule.right.
%% If so, Match adds a new edge that starts at Begin, ends
%% at En.'end' and has category Rule.left.
proc{Match Edge Rule Begin}
Cat = Edge.cat
in
case Rule.right
of nil then
raise error('right hand sides of rules must be nonemty') end
[] [!Cat] then
{Agenda.push {MakeEdge Rule.left Begin Edge.'end'}}
[] !Cat|NextCats then
NextRule = unit(left:Rule.left right:NextCats)
in
for NextEdge in {Chart.get Edge.'end'} do
{Match NextEdge NextRule Begin}
end
else skip %% rule does not apply
end
end
%% Process addes all Edges to the Agenda
%% that start with the edge Edge
proc{Process Edge}
for Rule in Rules do
{Match Edge Rule Edge.begin}
end
end
%% create an edge for all words in the input sentence
%% and add it to the agenda.
for %% iterate in parallel
Word in Words
Pos in Chart.min..Chart.max
do
Edge = {MakeEdge {Lexicon.toCat Word} Pos Pos+1}
in
{Agenda.push Edge}
end
%% process the agenda
for break:Break do
if {Agenda.isEmpty}
then {Break}
else
Edge = {Agenda.pop}
in
{Process Edge}
{Chart.add Edge}
end
end
in
Chart
end
in
Parser
end
end
| << Prev | - Up - | Next >> |