Techniques for Accelerating a Grammar-Checker

Techniques for Accelerating a Grammar-Checker Karel Oliva Computa,tiona,1 Linguistics University of Saa,rla,nd Postfach 15 11 50 D - 66 041 Sa.arbr(icken Germany ema,il: olivaOcoli .uni-sb. de Abstract The paper describes several possibilities of using finite-state automata a~s means for speeding up the performance of a grammar- and-parsing-based (as opposed to pattern- matching-based) grammar-checker able to detect errors from a predefined set. The ideas contained have been successflfily im- plemented in a grammar-checker for Czech, a free-word-order language from the Slavic group. 1 Introduction This paper describes an efficiency-supporting tool for one of the two grarnmar-checker technologies de- veloped in the fi'amework of the PECO2824 Joint Research Project sponsored by the European Union. The project, covering Bulgarian and Czech, two ti'ee- word-order languages from the Slavic t~rnily, was performed between January 1993 and mid 1996 by a consortium consisting of both academic and indu- strial partners. The basic philosophy of the technology discussed in this paper 1 is that of linguistic-theoretically smmd grammar-and-parsing-based machinery able to de- tect, by constraint relaxation, errors from a predefi- ned set (as opposed to pattern-matching approaches, which do not seem promising for a free word-order language). The core of the system (broad-coverage HPSG-based grammars of Bulgarian and Czech, and a single language-independent parser) was developed m the first three years of the project and was then passed to the industrial partners Bulgarian Business System IMC Sofia. and Macron Prague, Ltd. While the Bulgarian system remained in more or less a de- monstrator stage only, the Czech one satisfied Ma- cron's requirements as to syntactic coverage. Ho- wever, Macron expressed serious worries about the speed of the system, should this be really introdu- ced to the market. Following this, severa.1 possibili- IAs for the alterna.tive technology, cf. (Hola.n, Kubol't, a.ztd Pl/Ltek, 1997) ties of using finite-state automata (FSA) as means for speeding up the performance of the system were designed, developed and implemented, in particular: • for detecting sentences where none of the prede- fined errors can occur (tiros ruling out such sent- ences from the procedure of error-search proper) • for detecting which one(s) of tile predefined er- ror types might possibly occur in a particular sentence (hence, cutting clown the search space of the error-search proper) • for detecting errors which are of such a nature that their occurrence might be discovered by a machinery simpler than full-fledged parsing with constraint relaxation • for splitting (certain cases of) complex sent- ences into independent clauses, a,llowing thus for the error-detection to be performed on shor- t, er strings. 2 Lexicalization of Error Search Very many of the errors to be discovered by the sy- stem can be traced down to mismatches of (vMues of) features projected into the synta.ctic structure from the lexicon. Even though the error searching capabilities of the systern are not lirnited m princi- ple to these lexicMly induced errors, ibr a practicM implementation it turned out to be useful to narrow down the error search of the system to ahnost only …

Content truncated to 500 words