Abstract
This paper describes a novel approach to parsing languages characterized by high inflection and free word order, with a specific focus on Finnish. Moving away from traditional phrase-structure grammars, the authors propose a blackboard architecture that treats parsing as a non-deterministic search. By utilizing independent knowledge sources to incrementally construct partial dependency trees on a shared data structure, the system effectively manages long-distance dependencies and syntactic ambiguities.
Introduction
In the late 1980s, computational linguistics faced significant hurdles when applying English-centric parsing models to languages like Finnish. Finnish is a non-configurational language where grammatical relationships are primarily signaled by rich morphology (inflections) rather than rigid word order. Traditional phrase-structure grammars often result in an explosion of rules when attempting to account for every possible permutation of a sentence. This paper introduces the Augmented Dependency Parser (AOP), which leverages Dependency Grammar to focus on functional relationships between words, regardless of their linear position.
The Blackboard Architecture
The core of the AOP is its blackboard architecture, a design pattern that facilitates collaborative problem-solving among independent modules. The system is composed of three primary elements: the blackboard, knowledge sources, and a scheduler.
The Blackboard serves as a global data structure storing the current state of the parse, including partial dependency trees. Knowledge Sources (KS) are modular rulesets; "Functional Schemata" describe the expected environments for specific words (regents), while "Binary Dependency Relations" provide boolean tests to validate relationships based on morphology. Finally, the Scheduler acts as a controller, determining which KS to trigger based on updates to the blackboard. This decoupling of knowledge from control allows for a highly modular and extensible system.
Parsing as a State Machine
A key innovation in this model is treating the parsing of each individual word as a transition through a state machine. Rather than a simple linear scan, each word in a sentence acts as an agent seeking to fulfill its grammatical requirements.
As shown in the state diagram, a word moves from an initial "activated" state (S1) through various phases of searching for left and right dependents (S2, S3, S4) until it reaches a "completed" state (S5). This state-based approach allows the parser to handle long-distance dependencies naturally: a verb can remain in a waiting state until its required object appears elsewhere in the sentence, at which point a binary relation test confirms the link.
Implementation and Results
The AOP was implemented in FranzLisp on a VAX-11/751. The system's linguistic knowledge was derived from a custom lexicon of 1,800 entries and a morphological analyzer covering 35,000 word forms. Evaluation showed that the parser could process a typical six-word Finnish sentence in under 2.0 seconds. The grammar utilized 66 binary relations and 188 functional schemata, demonstrating robust coverage of complex Finnish syntactic structures.
Conclusion
The blackboard-based dependency parser offers a flexible and modular solution for the challenges of free-word-order languages. By viewing parsing as a search in a forest of partial trees and decoupling linguistic rules from execution logic, the AOP provides a framework that is both linguistically sound and computationally viable. Future work suggests that this architecture is inherently parallelizable, as each word's state machine could theoretically be processed by a dedicated agent in a multi-processor environment.
Summary updated