Parsing with Tree Des riptions

Parsing with Tree Des riptions: a onstraint{based approa h Denys Du hier Stefan Thater du hierps.uni-sb.de stth oli.uni-sb.de Abstra t In previous work [7, 8? it was shown that a onstraint-based treatment of tree- des riptions results in a simple and tra table implementation. However, that ap- proa h treated only the onjun tive fragment. Therefore it ould not be dire tly applied to parsing with tree des ription-based grammars where lexi al ambiguity gives rise to disjun tion. In this paper, we extend the previous approa h in two ways. First, we intro- du e the formalism of ele trostati tree des riptions', whi h ombines dominan e logi with a notion of polarities and permits a onvenient hara terization of ad- missible synta ti stru tures. Se ond, we extend this idea to disjun tive systems of des riptions suÆ ient to a ount for lexi al ambiguities. Finally, we exhibit an en oding that turns parsing into a onstraint satisfa tion problem (CSP) solvable by onstraint programming. 1 Introdu tion Traditionally, syntax is about trees: phrase stru ture trees. In omputational syntax however, it has variously been argued that des riptions of trees oer an alternative with signi ant advantages.

• missible synta


• tion


• grammar


• lexi al


• ti stru


• based approa


• alized tree


• tures


• onstraints whi