TL;DR
This paper presents a system that translates Lexical Functional Grammar (LFG) into a Prolog-based parser. It tackles the challenge of making sophisticated linguistic theories computationally accessible for linguists without deep programming knowledge, demonstrating how LFG's f-structures and constraints can be effectively implemented using Prolog's unification and DCG capabilities.
What Problem Does This Paper Address?
Linguists often use formalisms like Lexical Functional Grammar (LFG) to describe language structure. However, these formalisms can be abstract and difficult to test computationally without significant programming expertise. The authors aim to bridge this gap by creating a system that automatically transforms an LFG grammar into a working parser. This allows linguists to write and test grammars using a familiar, high-level description language (LFG) while benefiting from the computational power of Prolog and Definite Clause Grammars (DCGs) for parsing. A key challenge addressed is the inherent prohibition of left-recursive rules in standard DCG parsers, which is problematic for natural language phenomena that are naturally described using such structures.
Methods
The core of the system is a PROLOG implementation that translates LFG grammar rules and lexical entries into DCG-style PROLOG clauses.
- LFG to DCG Transformation: Grammar rules are converted into PROLOG clauses, enabling top-down parsing.
- F-structure Representation and Unification: LFG's f-structures (which represent grammatical information) are represented in PROLOG as "open-ended" lists of attribute-value pairs. The system implements a
mergepredicate that performs unification on these f-structures, mirroring LFG's unification-based approach. This unification handles feature sharing and can detect contradictions. - Constraint Handling: Equations and constraints associated with grammar rules are evaluated during parsing, allowing for early rejection of incorrect parses. Completeness, coherence, and existential constraints are managed, with mechanisms for checking them after parsing is complete.
- Long-Distance Dependencies: The system handles long-distance dependencies using metavariables, inspired by ATN formalisms but adapted for LFG and PROLOG. This involves managing controller lists threaded through the parse.
- Left Recursion Resolution: A crucial aspect is overcoming the DCG limitation on left recursion. The paper mentions a conversion to right-recursive rules that preserves the semantics of the functional description, though the specific details of this conversion for locally left-recursive rules are referenced in another work.
Datasets
Not discussed in the paper. The paper focuses on the grammar transformation system itself and uses examples from linguistic theory (e.g., Kaplan/Bresnan's work) and a specific English sentence for demonstration.
Key Insights and Ideas
- Bridging the Theory-Practice Divide: The system effectively demonstrates that sophisticated linguistic formalisms like LFG can be made computationally tractable for linguists without extensive programming backgrounds.
- Prolog as a Natural Fit for LFG: The paper highlights how Prolog's unification mechanism is well-suited for implementing LFG's f-structure unification, despite differences in attribute identification (labels vs. position).
- Handling LFG Constraints in Prolog: The methods for representing and checking LFG's various constraints (existential, coherence, completeness) within a PROLOG framework are a significant contribution.
- Overcoming DCG Limitations: The approach to resolving left recursion in DCGs while maintaining LFG semantics is a key technical achievement for building practical parsers.
- Reentrancy in F-structures: The paper emphasizes how the unification process, by extending structures and sharing tails, naturally handles reentrant structures (where a substructure can be reached via multiple paths).
Key Results
The paper describes the implementation of two versions of the LFG system in Prolog.
- Performance: For a simple English sentence ("I wondered which violin the sonata is tough for her to play on") using a grammar from Kaplan/Bresnan, parsing took approximately 2.3 seconds on a VAX 11/780 with a C-PROLOG interpreter.
- Grammar Development: The system proved useful for developing and testing grammars for fragments of English, German, and French. A French grammar with about 50 rules and over 200 lexical entries was successfully implemented.
- Qualitative: The system successfully handles LFG's core principles, including f-structure representation, constraints, and long-distance dependencies, while addressing the left-recursion issue.
Limitations and Future Work
The authors acknowledge several limitations and suggest future directions:
- Performance for Complex Grammars: The system's performance is good for simple grammars but is expected to degrade for grammars with significant nondeterminism.
- NP-Completeness: The inherent complexity of LFG recognition (known to be NP-complete) is a fundamental challenge.
- Backtracking Inefficiency: The reliance on simple backtracking for nondeterminism can lead to redundant parsing actions.
- Future Work Suggestions:
- Chart Parsing: Implementing chart parsing could avoid re-parsing identical constituents and improve error analysis.
- Explicit Ambiguity Representation: Representing ambiguities explicitly in f-structures (rather than chronologically) could help manage local ambiguity.
- More Complex Unification: These improvements might require a more complex unification definition, potentially moving away from Prolog's direct structure-sharing benefits.
- Further Research on Left Recursion: The paper references further work on handling locally left-recursive rules.
Summary updated