The Loom-LAG for Syntax Analysis : Adding a Language-independent Level to LAG

The Loom-LAG for syntax analysis Adding a language-independent level to LAG Markus Schulze University of Erlangen-Nurnberg Department of Computational Linguistics Bismarckstr. 6 91054 Erlangen Germany schulze@linguistik.uni-erlangen.de Abstract The left-associative grammar model (LAG) has been applied successfully to the mor- phologic and syntactic analysis of various european and asian languages. The algebraic definition of the LAG is very well suited for the application to natural language pro- cessing as it inherently obeys de Saussure's second law (de Saussure, 1913, p. 103) on the linear nature of language, which phrase-structure grammar (PSG) and categorial grammar (CG) do not. This paper describes the so-called Loom-LAGs (LLAG) —a specialisation of LAGs for the analysis of natural language. Whereas the only means of language-independent ab- straction in ordinary LAG is the principle of possible continuations, LLAGs introduce a set of more detailed language-independent generalisations that form the so-called loom of a Loom-LAG. Every LLAG uses the very same loom and adds the language-specific information in the form of a declarative description of the language —much like an ancient mechanised Jacquard-loom would take a program-card providing the specific pattern for the cloth to be woven. The linguistic information is formulated declara- tively in so-called syntax plans that describe the sequential structure of clauses and phrases. This approach introduces the explicit notion of phrases and sentence structure to LAG without violating de Saussure's second law and without leaving the ground of the orig- inal algebraic definition of LAG. LLAGs can in fact be shown to be just a notational variant of LAG —but one that is much better suited for the manual development of syntax grammars for the robust analysis of free texts. 1 Background — The Left-Associative Grammar Model (LAG) As the reader may not be familiar with the model of left-associative grammar (LAG), this section starts with a brief introduction to LAG', which the reader familiar with LAG may well skip. Most attempts at grammar acquisition and grammar coding are based on variants of PS- grammar. For reasons of complexity, these PS-grammars must be context-free (CF). It is widely agreed, however, that the class of context-free languages is not sufficient for the description of natural language. Hence these approaches suffer from an inherent empirical restriction. The approach presented in this paper is based on the formalism of Left Associative Grammar (LAG, (Hausser, 1989)). While PS-grammar is based on the principle of possible substitutions, LA-grammar uses the principle of possible continuations. This difference results in a complexity hierarchy which is orthogonal to the well-known Chomsky hierarchy. 'For an in-depth discussion see (Hausser, 1989), and (Hausser, 2001). 411 lexical lookup analysis In LA-grammars, the degree of complexity depends on the degree of ambiguity. 2 Of particular interest in the LA-hierarchy is the class of C1-languages, which parses in linear time and intersects with the class of CF- and CS-languages of the Chomsky hierarchy.3 The principle of possible continuations can be seen in the rule scheme of LAG: ri : cats x catnw --+ catss ► , rpi …

Content truncated to 500 words