LFG System in Prolog

Hideki YasukawaACL 1984

TL;DR

This paper presents a Prolog implementation of Lexical Functional Grammar (LFG), a powerful formalism for representing syntactic knowledge. By translating LFG into Definite Clause Grammars (DCGs) and leveraging Prolog's unification, the system efficiently generates functional structures (f-structures) during parsing, offering a robust and maintainable approach to syntactic analysis.

What Problem Does This Paper Address?

Designing and maintaining large-scale grammars for syntactic analysis presents a significant challenge. While formal systems like Lexical Functional Grammar (LFG) offer a powerful way to represent syntactic knowledge, their implementation can be complex. Traditional approaches using arbitrary Prolog programs embedded within DCGs can become difficult to understand, debug, and maintain. The authors aim to address this by providing a structured and efficient Prolog implementation of LFG that simplifies grammar development and enhances understandability.

Methods

The core of the paper describes a Prolog implementation of LFG. Key techniques include:

  • Translation to DCGs: LFG grammar rules are translated into Definite Clause Grammars (DCGs), a standard Prolog formalism for parsing.
  • Functional Equations: LFG's functional equations, which define the mapping between syntactic structures and functional structures (f-structures), are executed during the parsing process. This is achieved through Prolog's unification mechanism, extended to handle f-structure representations.
  • Ordered Binary Trees (OBTs) for F-structures: F-structures are represented using ordered binary trees (OBTs). This data structure is chosen for its efficiency in representing partially defined data and for enabling sharing of f-structures through a single unification operation using ID-variables.
  • ID-variables: Instead of LFG's meta-variables like ↑ and ⇓, the implementation uses ID-variables. These variables act as unique identifiers for f-structures associated with syntactic nodes, facilitating efficient sharing.
  • Macro Expander: A macro expander is used to translate LFG's descriptive primitives (like ↑ and ⇓) into Prolog code, making the grammar rules more readable and maintainable.

Datasets

Not discussed in the paper. The paper focuses on the implementation of the LFG formalism itself, using example sentences for illustration rather than formal datasets for training or evaluation.

Key Insights and Ideas

  • Prolog as a Suitable Tool for LFG: The paper strongly advocates for Prolog as an excellent tool for implementing LFG due to its unification capabilities, which naturally support the equational schema of LFG.
  • Efficiency of OBTs for F-structures: Representing f-structures as ordered binary trees with ID-variables significantly improves processing time and allows for efficient sharing of substructures through unification.
  • Maintainability through Macro Expansion: The use of macro notations for LFG primitives greatly enhances the writability and understandability of grammar rules, making them easier to develop and maintain.
  • LFG's Expressive Power: Despite the computational expense of the equational schema, LFG provides an expressive and natural account of linguistic phenomena.

Key Results

The paper demonstrates a functional LFG system implemented in Prolog. While specific quantitative results on large-scale corpora are not presented, the paper shows:

  • Successful Generation of F-structures: The system successfully generates f-structures for example sentences, as illustrated in Figures 1, 3, 4, and 6.
  • Efficiency Gains: The use of ordered binary trees for f-structures is reported to reduce processing time by approximately 30% compared to list-based representations.
  • Time Breakdown: For the example sentence "the girl persuaded the baby to go," the analysis time is broken down into parsing (972 ms), constraint checking (19 s), and completeness checking (41 ms).

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that the computational complexity of the equational schema is "very expensive."
  • Future Work: The authors suggest that introducing parallel or concurrent execution mechanisms could be a promising approach to overcome the inefficiency of the equational schema. Further research will involve analyzing a wider variety of utterances to extract more primitives and develop necessary schemata.

Summary updated

BibTeX
@inproceedings{yasukawa1984lfg,
  author = {Hideki Yasukawa},
  title = {{LFG System in Prolog}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1984},
}
Figure