Compiling and Using Finite-State Syntactic Rules

Compiling and Using Finite-State Syntactic Rules Kimmo Koskenniemi, Pasi Tapanainen and Atro Voutilainen University of Helsinki Research Unit for ComputaHonal Linguistics HaUituskatu 11 SF-O0100 I..lelsinkJ F~and Abstract A language-independent framework for syntac- tic finlte-state parsing is discussed. The article presents a framework, a formalism, a compiler and a parser for grammars written in this for- realism. As a substantial example, fragments from a nontrivial finite-state grammar of Eng- lish are discussed. The linguistic framework of the present approach is based on a surface syntactic tag- ging scheme by F. Karlsson. This representa- tion is slightly less powerful than phrase structure tree notation, letUng some ambigu- ous constructions be described more concisely. The finite-state rule compiler implements what was briefly sketched by Koskenniemi (1990). It is based on the calculus of finite-state machines. The compiler transforms rules into rule-automata. The run-time parser exploits one of certain alternative strategies in perform- ing the effective intersection of the rule autom- ata and the sentence automaton. Fragments of a fairly comprehensive finite-state granmmr of English axe presented here, includ- ing samples from non-finite constructions as a demonstration of the capacity of the present formalism, which goes far beyond plain disam- blguation or part of speech tagging. The grammar itself is directly related to a parser and tagging system for English created as a part of project SIMPR I using Karlsson's CG (Constraint Grammar) formalism. 1. Introduction The present finite-state approach to syntax should not be confused with eg. attempts to characterize syntactic structures with regular 1. Esprit 11 project No. 2083, Structured information Management: Proceaalng and Retrieval. Afn'Es DE COLING-9Z NANTES, 23-28 Aou'r 1992 phrase structure grammars. Instead of using trees as a means of representlng structures, we use syntactic tags associated with words, and the finite-state rules constrain the choice of tags. This style of representaUon was adopted from Karlsson's CG approach and an earlier Finnish parser called FPARSE (Karlsson 1985, 1990). The current approach employs a shallow sur- face oriented syntax. We expect it to be useful in syntactic tagging of large text corpora. Infer- mat/on retrieval, and as a starting point for more elaborate syntactic or semantic analysis. 1.1 Representation of sentences We represent the sentences as regu/ar expres- sions, or equivalently, asfinite-state networks, which list all combinatory possibilities to inter- pret them. Consider the sentence: the program runs. A (simplified) representation for the morpholog- ically processed but syntactically unanalyzed sentence as a regular expression could be roughly as follows: 0@ the DEF ART [8 I @/ I 8< I 8>] [ [program N NOM SG [eSUBJ [ 8OBJ I 8PREDC} ] 1 [Drogram V PRES NON-SG3 8FINV 8MAINV] i [program V INF]] [8 I 8/ I 8< I @>] [ [run V PRES SG3 @FINV 8MAINV] I [run N NOM PL [eSUBJ I 8OBJ I 8PREDC]]] 88 Here 8S represents a sentence boundary, @ a word boundary, 8/ an ordinary clause hound- amy, @< a begi,Lrflng of a center embedded clause, and @> the end of such an embedding. Square …

Content truncated to 500 words