Principles and Implementation of Deductive Parsing

By Stuart M. Shieber, Yves Schabes, Fernando C Pereira. 1994

We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine can interpret such deduction systems so as to implement the corresponding parser. The method generalizes easily to parsers for augmented phrase structure formalisms, such as definite-clause grammars and other logic grammar formalisms, and has been used for rapid prototyping of parsing algorithms for a variety of formalisms including variants of tree-adjoining grammars, categorial grammars, and lexicalized context-free grammars.

Subfields: Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction (2022, methodology): “Following the standard deduction systems (Shieber et al., 1995; Nederhof, 2003), the reasoning process can be formulated in Figure 2.”
Squibs and Discussions: Weighted Deductive Parsing and Knuth’s Algorithm (2003, methodology): “The use of deduction systems for specifying parsers has been proposed by Shieber, Schabes, and Pereira (1995) and Sikkel (1997).”
Better k-best Parsing (2005, methodology): “…free indices i < j < k , we have a hyperarc h (( Y ; i ; k ) ; ( Z ; k ; j )) ; ( X ; i ; k ) ; f i corresponding to the instantiation of the inference rule C omplete in the deductive system of (Shieber et al. , 1995), and the weight function f is de(cid:2)ned as f ( a ; b ) = ab (cid:1) Pr( X !”
Algorithms for Deterministic Incremental Dependency Parsing (2008, background): “…as deﬁned here, can be seen as corresponding to the notions of soundness and completeness for grammar parsing algorithms, according to which an algorithm is sound if it only derives parses licensed by the grammar and complete if it derives all such parses (Shieber, Schabes, and Pereira 1995).”
Forest Rescoring: Faster Decoding with Integrated Language Models (2007, background): “Similarly, the decoding problem with SCFGs can also be cast as a deductive (parsing) system (Shieber et al., 1995).”
First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests (2009, background): “3 We assume that HG has already been built by deductive inference (Shieber et al., 1994).”
Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs (2014, methodology): “Dyna makes use of generalizations of parsing-asdeduction [29] and semi-ring parsing [10] to compile weighted logic programs into highly optimized dynamic programs.”
Hierarchical Phrase-Based Translation (2007, unknown): “In the following we present several parsers as deductive proof systems (Shieber, Schabes, and Pereira 1995; Goodman 1999).”