Analysing Constraint Grammars with a SAT-solver

Analysing Constraint Grammars with a SAT-solver Inari Listenmaa, Koen Claessen University of Gothenburg, Chalmers University of Technology Gothenburg, Sweden inari@chalmers.se, koen@chalmers.se Abstract We describe a method for analysing Constraint Grammars (CG) that can detect internal conflicts and redundancies in a given grammar, without the need for a corpus. The aim is for grammar writers to be able to automatically diagnose, and then manually improve their grammars. Our method works by translating the given grammar into logical constraints that are analysed by a SAT-solver. We have evaluated our analysis on a number of non-trivial grammars and found inconsistencies. Keywords: Constraint Grammar, SAT, Grammar Analysis 1. Introduction Constraint Grammar (CG, Karlsson et al. (1995)) is a formalism used to disambiguate morphologically analysed text. A grammar consists of rules that target specific read- ings for selection or removal, based on contextual tests. For example, the following rule REMOVE verb IF (-1 det) ; removes all verb readings from a word which is preceded by a determiner. Given the following text, "<the>" "<wish>""the" det def "wish" noun sg "wish" verb pl "wish" verb inf the rule will match to the word wish, and remove the read- ings "wish" verb pl and "wish" verb inf. Note that if the target word has only one remaining reading, then the rule will not apply, even if the condition is met. CGs are valuable resources for rule-based NLP, especially for lesser resourced languages. They are robust and can be written without large corpora—only a morphological anal- yser is needed. The formalism is lightweight and language- independent, and resources can be shared between related languages (Bick, 2006; Antonsen et al., 2010). Mature CGs contain some thousands of rules, but even small CGs are shown to be effective (Antonsen and Trosterud, 2011). By design, CG is a shallow and robust formalism. There is no particular hierarchy between lexical, morphological, syntactic or even semantic tags: individual rules can be written to address any property, such as “verb”, “copula verb in first person singular”, or “the word form sailor, pre- ceded by drunken anywhere in the sentence”. This makes it possible to treat very particular edge cases without touching the more general rule: we would simply write the narrow rule first (“if noun AND sailor”), and introduce the general rule (“if noun”) later. However, this design is not without problems. As CGs grow larger, it gets harder to keep track of all the rules and their interaction. Our tool will help grammar writers and users to find conflicting rules, diagnose problems and SELECT Inf IF (-1 Para OR De) (0C V) ; SELECT Inf IF (-1 Prep) (0C V) ; SELECT Inf IF (-1C Vai) ; SELECT Inf IF (-1C Vbmod) (0C V) ; SELECT Inf IF (-1C Ter/de) ; SELECT Inf IF (-1C Vbmod) (0 Ser) ; Figure 1: Rules to select infinitive in Portuguese. improve their grammars. We expect two major use cases: first, to test the effect of new rules while writing a grammar, and second, to take a …

Content truncated to 500 words