A Wide-Coverage Context-Free Grammar for Icelandic and an Accompanying Parsing System

Proceedings of Recent Advances in Natural Language Processing, pages 1397–1404, Varna, Bulgaria, Sep 2–4, 2019. https://doi.org/10.26615/978-954-452-056-4_160 1397 A Wide-Coverage Context-Free Grammar for Icelandic and an Accompanying Parsing System Vilhjálmur Þorsteinsson, Hulda Óladóttir Miðeind ehf. Reykjavik Iceland vt@extrada.com, holado@gmail.com Hrafn Loftsson Department of Computer Science Reykjavik University Iceland hrafn@ru.is Abstract We present an open-source, wide- coverage context-free grammar (CFG) for Icelandic, and an accompanying parsing system. The grammar has over 5,600 nonterminals, 4,600 terminals and 19,000 productions in fully expanded form, with feature agreement constraints for case, gender, number and person. The parsing system consists of an enhanced Earley-based parser and a mechanism to select best-scoring parse trees from shared packed parse forests. Our parsing system is able to parse about 90% of all sentences in articles published on the main Icelandic news websites. Preliminary evaluation with evalb shows an F-measure of 71.90% on parsed sentences. Our system demon- strates that parsing a morphologically rich language using a wide-coverage CFG can be practical. 1 Introduction A CFG consists of a set of production rules that re- cursively describe how the strings of the underly- ing language can be derived. A parser for a natural language CFG checks whether a sentence can be derived by the CFG, and if so, assigns a syntactic structure (one or more parse trees) to the sentence. Well-known general parsing algorithms for CFGs include the (bottom-up) CYK algorithm (Younger, 1967) and the (top-down) Earley algorithm (Ear- ley, 1970). Various textbooks on Natural Language Pro- cessing (NLP) contain toy CFGs (for English, in most cases, e.g. (Jurafsky and Martin, 2009; Ljunglöf and Wirén, 2010)), but very few pa- pers in recent literature describe hand-crafted nat- ural language CFGs and parsers for them (we dis- cuss a couple of them in Section 2). The reason is that the development of wide-coverage hand- crafted CFGs has been viewed as a challenging and time-consuming task (Briscoe et al., 1987; Hindle, 1989; Kinyon and Prolo, 2002), and that common phenomena, like agreement and inflec- tion, have been considered complicated to de- scribe using a CFG (Ljunglöf and Wirén, 2010). The processor and memory requirements of fully general parsing algorithms that can handle am- biguous grammars, being of worst-case cubic or- der (Younger, 1967; Scott, 2008), have also been seen as prohibitive. Beyond parsing, hand-crafted CFGs can be used inter alia to check and correct grammar in text (see Section 3). Several treebanks have been developed for var- ious languages during the past 25 years or so, e.g. (Marcus et al., 1993; Brants et al., 2004; Rögn- valdsson et al., 2012). Thus, instead of developing a CFG for a given language and a parser for the grammar, the more common approach has been to induce a probabilistic CFG (PCFG) from a tree- bank, and to train a probabilistic parser on the PCFG (Cahill, 2008). However, creating a high- quality treebank is a labor-intensive task, and, in- deed, in many aspects similar to the process of manually crafting a grammar (Xia, 2001). More- over, …

Content truncated to 500 words