From Abstract Syntax to U niversal D ependencies (2016)

Abstract: Abstract syntax is a semantic tree representation that lies between parse trees and logical forms. It abstracts away from word order and lexical items, but contains enough information to generate both surface strings and logical forms. Abstract syntax is commonly used in compilers as an intermediate between source and target languages. Grammatical Framework (GF) is a grammar formalism that generalizes the idea to natural languages, to capture cross-lingual generalizations and perform interlingual translation. As one of the main results, the GF Resource Grammar Library (GF-RGL) has implemented a shared abstract syntax for over 30 languages. Each language has its own set of concrete syntax rules (morphology and syntax), by which it can be generated from the abstract syntax and parsed into it. This paper presents a conversion method from abstract syntax trees to dependency trees. The method is applied for converting GF-RGL trees to Universal Dependencies (UD), which uses a common set of labels for different languages. The correspondence between GF-RGL and UD turns out to be good, and the relatively few discrepancies give rise to interesting questions about universality. The conversion also has potential for practical applications: (1) it makes the GF parser usable as a rule-based dependency parser; (2) it enables bootstrapping UD treebanks from GF treebanks; (3) it defines formal criteria to assess the informal annotation schemes of UD; (4) it gives a method to check the consistency of manually annotated UD trees with respect to the annotation schemes; (5) it makes information from UD treebanks available.

## introduction computational syntax can work on different levels of abstraction. the lowest level normally used when processing written text is strings of tokens ("words"). but it is often useful to work with more abstract structures: part-of-speech (pos) tagged lemma sequences, phrase structure trees, dependency trees, or some kind of logical forms. raising the level of abstraction often gives new ways to relate different languages to each other. thus tagged lemmas enable the separation of surface strings from word senses, which can be useful, for instance, in factored machine translation. logical forms ideally ignore all languagerelated features, and express just the pure propositional meaning. but what about syntax trees? traditional phrase structure trees preserve surface words and constituent order and are hence language-dependent. dependency trees are often a bit more abstract, treating the word order as irrelevant and lemmatizing the words. sharing the pos tags and dependency labels between languages increases this potential to abstract over languages. universal dependencies (ud, de marneffe et al. ( 2014 )) is a recent approach to dependency parsing that tries to maximize the sharing of structures between languages. ud has a set of dependency labels and pos tags that are designed to fit many languages, and a series of annotation manuals that guide treebank builders to use the labels and tags in a uniform way. the expected gain is that efforts can be shared among languages. for instance, searching for semantic roles in sentences can be defined uniformly for different languages, and parsers for new languages can be bootstrapped by using treebanks for other languages. as suggested by @xcite , ud can be seen as a modern approach to universal grammar. the originally mediaeval idea of a universal grammar has many times been rejected by linguists, often with good reasons. but much of it can be saved if we think of it as an abstraction: on a proper level of abstraction, languages have much in common, so why not try to find out what is common? universality should be seen as a working hypothesis rather than an a priori truth. in ud, the working hypothesis is that languages have a common set of parts of speech @xcite as well as grammatical functions @xcite . some languages don't have all of these features, and individual languages may have features that are not universal. the annotation manuals for treebank builders have recommendations that maximize the use of common features, but give room to diversity. this approach has proved successful, and as a result, ud has presented treebanks for over 30 languages. an older but nonetheless computational approach to universal grammar is curry's notion of tectogrammatical structure @xcite . the tectogrammatical representations are function applications 1 . they are trees that describe pure constituency: what the constituents are and how they are put together, but ignoring what word strings are ultimately used and what their linear order is. to give an example, subject-verb-object predication could be presented by a tectogrammatical function pred, pred : tv -> np -> np -> s that takes a transitive verb and two noun phrases as its arguments and produces a sentence. the constituent order (svo, sov, etc) is specified separately for each language in their phenogrammatical rules. these rules may look as follows: pred verb subj @xmath0, respectively (with ++ marking concatenation). curry's tectogrammar inspired the prague school of dependency parsing @xcite . the grammars, however, are different, since the prague school is based on the roles of words (similar to what is traditionally called "grammatical functions"), whereas curry's tectogrammatical functions are functions that combine words. grammatical framework @xcite ) is a grammar formalism that is more directly based on curry's architecture. gf grammars are similar to grammars used in compiler construction, where tectogrammar is called abstract syntax and phenogrammar is called concrete syntax or linearization @xcite . 2 the most comprehensive multilingual grammar in gf is the resource grammar library, gf-rgl @xcite , which by the time of writing has concrete syntaxes for over 30 languages, ranging from european through finno-ugric and semitic to east asian languages. 3 when the ud approach appeared, it became immediately interesting to see how it relates to gf-rgl. the formal correspondence was obvious: once we have a gf abstract syntax tree, we can easily derive a dependency tree. for instance, a rule of the form pred verb subj obj gives rise to a dependency tree where the first argument produces the head, the second argument produces a dependent with label subj and the third argument a dependent with label obj. as we will show more formally in section 2.2, a simple recursive function can convert abstract trees to dependency trees in this way. however, there are details that remain to be worked out: the purpose of this paper is to answer these questions. while doing so, we will often discuss the differences in analyses between gf-rgl and ud, and in many cases argue for the gf-rgl decisions. but in a bigger picture, we have been surprised to see how much the approaches have in common. that so similar structures of "universal grammar" have been found in two independent ways can be seen as confirming evidence for both of them. our work is also expected to have practical uses: bootstrapping ud treebanks from gf; using ud treebanks to help gf parsing (in particular, statistical disambiguation); assessing ud annotation schemes and treebanks from a formal perspective. our conversion moreover makes the gf-rgl parser usable as a rule-based ud parser, although a rather slow one. perhaps more interestingly, generation from ud trees becomes possible (including translations to other languages), because gf grammars are reversible (and generation is fast, as opposed to parsing). the structure of the paper is as follows: section 2 prepares the discussion with a concise introduction to gf and a mathematical definition of the correspondence between abstract syntax trees and dependency trees. section 3 gives an overview of gf-rgl and ud; parts of it can be skipped by the reader who already knows the approaches, and many of the details are given in an appendix. section 4 goes through the great majority of structures, where gf-rgl and ud are similar enough to 3 the current status of gf-rgl can be seen in http://www . grammaticalframework.org/lib/doc/synopsis.html which also gives access to the source code. ## an overview of gf-rgl and ud this section provides readers with an overview of gf-rgl and the ud annotation project. readers familiar with gf can skip section 3.1 and readers familiar with ud can skip section 3.2. ## experiments in our experiments, we focus on evaluating two things: the mapping proposed in this paper to convert gf trees into ud dependency trees and subsequently how much the abstract syntax in gf-rgl and the mapping is useful in bootstrapping treebanks. we carry out experiments to evaluate the correctness of our mapping and to understand the systematic similarities between gf-rgl and the ud annotation scheme. in the first set of experiments, using mappings defined on the abstract syntax alone (both local and non-local rules), we bootstrap dependency trees for 31 languages from a treebank of asts. analyses of these bootstrapped treebanks give insights about the ud scheme and the gf-rgl. the lack of concrete local and non-local rules for a specific language result in trees that resemble collapsed dependency trees (de @xcite by deleting the dummy dep labels. due to the lack of concrete rules so far, the bootstrapped treebanks for languages other than english do not contain labels for syncategorematic words, and these dep labels are collapsed. figure 17 shows examples of bootstrapped and "collapsed" ud trees for swedish and bulgarian in the context of this work. when defined, the concrete rules "decollapse" these trees by introducing the right ud labels for syncategorematic words. ## conclusion in this paper, we investigate the similarities and differences between gf-rgl and universal dependencies (uds). our main result is a conversion from gf-rgl abstract syntax trees to ud dependency trees. the conversion from abstract syntax trees in gf to ud trees is parameterized by a mapping defined on functions in the abstract syntax, to encode the notion of "head" and the grammatical relation of other modifiers with respect to the head. the mapping described in this work has has two levels -rules defined on the abstract syntax and rules defined on the concrete syntax. rules defined on the abstract syntax are by definition language-independent and "shared". however, rules defined on concrete syntax are defined for each language separately, even if the ud labels for these may be shared across languages. furthermore, both abstract and concrete rules have two types -"local" and "non-local". in the case of "local" rules, the mapping between function and its arguments and their ud annotations (both the identity of head and the ud labels) is determined using only the function, unlike "non-local" rules where a mapping applies only in certain contexts. the mapping from gf-rgl to uds showed that a large part of the gf-rgl and ud annotation scheme is language-independent. about 30 of the 40 ud labels are mapped using the abstract "local" and "nonlocal" rules in our experiments. these parts of both gf-rgl and ud scheme can be said to be language-independent. the parts of the mapping defined on the concrete syntax interestingly falls into two taxons within the ud annotation scheme (clausal dependents such as aux, auxpass, cop, mark, expl and compounding labels compound, mwe). one application of the conversion detailed in this paper is to automatically create ud treebanks from gf treebanks. our experiments using a small treebank showed that about 80% of ud treebank annotations can be ported using the abstract syntax in gf-rgl. the remaining annotations can also be derived from gf, provided a small effort is put into defining concrete rules in the mapping for languages of interest. other plausible applications and future directions of our work include multilingual consistency checking in the ud annotated treebanks and using these treebanks to estimate probabilistic ranking of gf abstract syntax trees.