Efficient techniques for parsing with tree automata
Jonas Groschwitz, Alexander Koller, Mark S. Johnson · 2016
Parsing for a wide variety of grammar formalisms can be performed by intersecting finite tree automata.However, naive implementations of parsing by intersection are very inefficient.We present techniques that speed up tree-automata-based parsing, to the point that it becomes practically feasible on realistic data when applied to context-free, TAG, and graph parsing.For graph parsing, we obtain the best runtimes in the literature.