<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Hi John,<br>
<br>
There are a number of excellent implementations of LFG around
(including the one from Parc, of course), but that is not what you're
asking about.<br>
<br>
The main reason why there are no deductive parsers for LFG is that LFG
has always been thought of in terms of satisfiability of constraints,
rather than deductive inference from a set of axioms and inference
rules. As far as I know there's no principled reason why this should
not be possible (c.f. my comment about finite satisfiability being
equivalent to deduction below), but it just hasn't been done. <br>
<br>
There are technical issues to be solved, of course. Some are quite
theoretical: e.g. first-order deduction is Turing complete, while
first-order satisfiability is co-Turing complete (but LFG generally
requires the satisfying models to be finite, and first-order finite
satistfiability is Turing complete, just like deduction, see my "Two
Ways of Formalizing Grammars" in Linguistics and Philosophy 1994, which
actually discusses LFG parsing). <br>
<br>
And there are practical problems in implementing a deductive parser for
LFG which stem from the multiple levels of representation and diversity
of constraints in LFG; arranging to coordinate these in a moderately
efficient manner is complicated!<br>
<br>
Best,<br>
<br>
Mark Johnson<br>
<br>
John Colby wrote:
<blockquote cite="mid5F8C0678-664C-416D-9819-379A36F2942E@soe.ucsc.edu"
type="cite">Does anyone know of deductive parsers for LFG, whether
described as per Shieber et. al (1994, 1995) or as parsing schemata as
per Sikkel(1993, 1997)
<div><br class="khtml-block-placeholder">
</div>
<div>Thank you,</div>
<div>John</div>
<div><br>
<div>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 14px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><b>John
E. Colby</b></font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 14px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><b>Ph.D.
Candidate in Computer Science</b></font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 14px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><b>Baskin
School of Engineering</b></font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 12px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><span
class="Apple-converted-space"> </span>Baskin Engineering Building</font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 12px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><span
class="Apple-converted-space"> </span>University of California, Santa
Cruz</font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 12px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><span
class="Apple-converted-space"> </span>1156 High St.</font></p>
<p style="margin: 0px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 12px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><span
class="Apple-converted-space"> </span>Santa Cruz, CA 95064</font></p>
<p style="margin: 0px; min-height: 14px;"><font
style="font-family: Verdana; font-style: normal; font-variant: normal; font-weight: normal; font-size: 12px; line-height: normal; font-size-adjust: none; font-stretch: normal;"><span
class="Apple-converted-space"> </span></font></p>
</div>
<br>
</div>
</blockquote>
</body>
</html>