Introduction
In the early 1980s, a research team at Hewlett-Packard undertook a landmark project to bridge the gap between theoretical linguistics and practical computational implementation. At a time when the prevailing consensus suggested that natural language was too complex for simple mathematical models, the HP team demonstrated that a "context-free" approach could effectively handle the intricacies of English. Their work resulted in a portable, computationally efficient system capable of translating complex English sentences into first-order logic queries for a relational database.
Theoretical Framework: GPSG and Metarules
The system is based on Generalized Phrase Structure Grammar (GPSG). In the late 70s, researchers often relied on complex "transformational" grammars or Augmented Transition Networks (ATNs). While powerful, these were often computationally expensive and difficult to maintain. The HP team challenged this by utilizing a context-free framework that remained computationally tractable while being theoretically grounded.
To manage the complexity of natural language without an explosion of manual rules, the authors employed Rule Schemata and Metarules. Metarules act as "rules that generate rules." For example, a single metarule can automatically generate passive-voice versions of every active-voice verb rule. This approach allowed the team to expand a base of 40 rules into 283 grammar rules, significantly compressing the effort required for grammar development.
Additionally, the system utilized Slash Categories ($A/B$) to handle "gaps" in sentences (e.g., in the question "Which employee did you hire?", where "employee" is missing from its standard position after "hire"). This allowed the grammar to track missing constituents while remaining strictly context-free.
Semantic Interpretation
Following the work of Richard Montague, the system employs Rule-to-Rule Semantics. Every syntactic rule is paired with a specific semantic translation rule. As the parser constructs a syntactic tree, it simultaneously builds a logical representation using lambda calculus.
To handle the ambiguity of quantifier scope (e.g., the different interpretations of "Every student saw a movie"), the system uses Cooper Storage. This technique allows the system to store quantifier representations and apply them at different levels of the logical structure without requiring multiple syntactic parses. As shown in Figure 1, the top-level node (S) maintains a tuple that includes both the core predicate logic and the stored quantifier for "every applicant."
System Architecture and Implementation
The architecture functions as a pipeline moving from raw text to database results:
- The Metagrammar: Generates the full rule set from base rules and metarules.
- The Parser: A top-down parser that builds the syntactic tree.
- Semantic Translation: Simultaneously generates logical forms using the rule-to-rule approach.
- The Disambiguator: Acts as a bridge to the domain. It uses "sortal information" (types) to map general linguistic roles (like "Agent" or "Location") to specific relations in the HIRE relational database.
Results and Evaluation
The system was evaluated against a "large fragment of English" defined by the authors. The implementation successfully processed a wide array of phenomena, including noun-noun compounds, genitives, questions, passives, and existential sentences ("There is a..."). By reducing second-order Montague semantics into extensional first-order logic, the system achieved compatibility with standard relational database technologies of the era.
Conclusion and Legacy
While the system was limited by its lack of discourse context (it processed isolated sentences only) and required manual effort to map new lexicons to specific databases, it proved that context-free grammars were a viable and efficient tool for NLP. By separating linguistic knowledge from domain-specific database logic, the HP team created a model for portable, theoretically-informed natural language interfaces.
Summary updated