Skip to content
Publications

Article · May 1, 2000

Practical aspects in compiling tabular TAG parsers

Miguel Á. Alonso, Djamé Seddah, Éric Villemonte de la Clergerie

Abstract

This paper describes the extension of the system DyALog to compile tabular parsers from Feature Tree Adjoining Grammars. The compilation process uses intermediary 2-stack automata to encode various parsing strategies and a dynamic programming interpretation to break automata derivations into tabulable fragments. 1. Introduction This paper describes the extension of the system DyALog in order to produce tabular parsers for Tree Adjoining Grammars [TAGs] and focuses on some practical aspects encountered during the process. By tabulation, we mean that traces of (sub)computations, called items, are tabulated in order to provide computation sharing and loop detection (as done in Chart Parsers). The system DyALog 1 handles logic programs and grammars (DCG). It has two main components, namely an abstract machine that implements a generic fix-point algorithm with subsumption checking on objects, and a bootstrapped compiler. The compilation process first compiles a grammar into a Push-Down ...

Natural Language Processing Techniquessemigroups and automata theorySyntax, Semantics, Linguistic Variationcompiler generationdynamic programmingparsing strategies

More by Miguel Alonso