Skip to content
Publications

Article

On Theoretical and Practical Complexity of TAG Parsers

Carlos Gómez‐Rodríguez, Miguel Á. Alonso, Jesús Vilares

Abstract

We present a system allowing the automatic transformation of parsing schemata to efficient executable implementations of their corresponding algorithms. This system can be used to easily prototype, test and compare different parsing algorithms. In this work, it has been used to generate several different parsers for Context Free Grammars and Tree Adjoining Grammars. By comparing their performance on different sized, artificially generated grammars, we can measure their empirical computational complexity. This allows us to evaluate the overhead caused by using Tree Adjoining Grammars to parse context-free languages, and the influence of string and grammar size on Tree Adjoining Grammars parsing.

semigroups and automata theoryNatural Language Processing TechniquesSyntax, Semantics, Linguistic Variationtree adjoining grammarscontext-free grammarsparsing algorithms

More by Miguel Alonso