Formal Grammars for Linguistic Treebank Queries

Proceedings of the Australasian Language Technology Workshop 2005, pages 96–104, Sydney, Australia, December 2005. Formal Grammars for Linguistic Treebank Queries Mark Dras Centre for Language Technology Macquarie University madras@ics.mq.edu.au Steve Cassidy Centre for Language Technology Macquarie University Steve.Cassidy@mq.edu.au Abstract There has been recent interest in looking at what is required for a tree query language for linguis- tic corpora. One approach is to start from exist- ing formal machinery, such as tree grammars and automata, to see what kind of machine is an ap- propriate underlying one for the query language. The goal of the paper is then to examine what is an appropriate machine for a linguistic tree query language, with a view to future work defining a query language based on it. In this paper we review work relating XPath to regular tree gram- mars, and as the paper’s first contribution show how regular tree grammars can also be a basis for extensions proposed for XPath for common lin- guistic corpus querying. As the paper’s second contribution we demonstrate that, on the other hand, regular tree grammars cannot describe a number of structures of interest; we then show that, instead, a slightly more powerful machine is appropriate, and indicate how linguistic tree query languages might be augmented to include this extra power. 1 Introduction There has been recent interest in looking at what is required for a query language for annotated linguistic corpora (Lai and Bird, 2004). These corpora are used in a range of areas of natural language processing (NLP)—parsing, machine translation, and so on—where they form the basis of training data for statistical methods; and also in lin- guistics, where they are used to extract ex- amples of particular phenomena for analy- sis and testing of hypotheses. As noted by Lai and Bird, the prototypical hierarchical linguistic annotation is the syntax tree, and consequently the type of query language that is of interest is a tree query language. One approach to deciding what is required in a tree query language, taken by Lai and Bird (2004), is to examine and compare a range of existing ones: for example, TGrep2 (Ro- hde, 2001), TIGERSearch (K¨onig and Lez- ius, 2001), or Emu (Cassidy and Harrington, 2001). One of their goals is to understand better the formal properties required of query languages. It has been noted in a number of places that treebank querying is in essence a spec- ification of a tree pattern, which matches against the desired trees in the treebank cor- pus (Abiteboul, 1997). These tree patterns can be described by existing formal machin- ery such as tree grammars and automata. An approach complementary to the one men- tioned above is thus to examine the extent to which this formal machinery is adequate for describing tree patterns relevant for the sorts of queries of interest in NLP or linguis- tics, and then to link this to a query lan- guage. A reason for being interested in this link between tree query languages and for- mal machinery …

Content truncated to 500 words