Overgeneration is the main source of computational complexity in previous principle-based parsers. This paper presents a message passing algorithm for principle-based parsing that avoids the overgeneration problem. This algorithm has been implemented in C + + and successfully tested with example sentences from (van Riemsdijk and Williams, 1986). 1. I n t r o d u c t i o n Unlike rule-based grammars that use a large number of rules to describe patterns in a language, Government-Binding (GB) Theory (Chomsky, 1981; Haegeman, 1991; van Riemsdijk and Williams, 1986) ezplains these patterns in terms of more foundmental and universal.
