Publikation
Tabulation of Automata for Tree-Adjoining Languages
Miguel Alonso Pardo; Mark-Jan Nederhof; Eric Villemonte de la Clergerie
In: Grammars, Vol. 3, Pages 89-110, 2000.
Zusammenfassung
We propose a modular design of tabular parsing algorithms for tree-adjoining languages. The modularity is made possible by a separation of the parsing strategy from the mechanism of tabulation. The parsing strategy is expressed in terms of the construction of a nondeterministic automaton from a grammar; three distinct types of automaton will be discussed. The mechanism of tabulation leads to the simulation of these nondeterministic automata in polynomial time, independent of the parsing strategy. The proposed application of this work is the design of efficient parsing algorithms for tree-adjoining grammars and related formalisms.