ComputerScience,1970-2008-Computer Science-1993.jsonl.gz.gz
Computer Science
844a135ea8c50f148305917aa236e3542529fb4c
A Principle-based Parser for Foreign Language Training in German and Arabic

In this paper we discuss the design and implementation of a parser for German and Arabic, which is currently being used in a tutoring system for foreign language training. Computer-aided language tutoring is a good application for testing the robustness and flexibility of a parsing system, since the input is usually ungrammatical in some way. Efficiency is also a concern, as tutoring applications typically run on personal computers, with the parser sharing memory with other components of the system. Our system is principle-based, which ensures a compact representation, and improves portability, needed in order to extend the initial design from German to Arabic and (eventually) Spanish. Currently, the parser diagnoses agreement errors, case errors, selection errors, and some word order errors. The parser can handle simple and complex declaratives and questions, topicalisations, verb movement, relative clauses — broad enough coverage to be useful in the design of real exercises and dialogues.


Introduction
This paper describes the design and implementa tion of a parser for German and Arabic, which is currently being · used in a tutoring system for foreign language training. Computer-aided lan guage tutoring is a good application for testing the robustness and flexibility of a parsing system, since the input is usually ungrammatical in some way. The system is portable in that we extend the initial design for German to handle Arabic and (eventually) Spanish. Efficiency is also a concern, since tutoring applications typically run on per sonal computers, with the parser sharing memory with other components of the system. Our sys tem is principle-based, which ensures a compact representation.
Robustness is required because the system must be able to parse incorrect input. Since the user is not a native speaker · of the language, the system must handle spelling errors such as (la) as well as grammar errors, as in (lb).

{b) Der FluP ftieften au/ des
The river flow. pi to the Westen west.gen 'The river flows to the west' *The names of the authors are in alphabetical order. This paper is the result of cooperative work in all its stages. However, as far as legal requirements are concerned, Paola Merlo takes responsibility for sections 4 and 5.
(2) (a)  The system niust be flexible because it must · be able to handle different levels of ill-formedness.

For example, it must be.able to detect the differ-. ence between (la) and (lb): · In the former the verb ftieftt is incorrectly typed, while in the sec ond sentence the verb is incorrectly inflected and th� wrong case is selected for the prepositional phrase, which should be auf Westen. The sen tences in (2) illustrate a similar pair from Arabic. In (2a) the word for road should have an emphatic consonant (signified by a capital letter). In (2b), there is an· agreement error (the subject is third feminine singular, while the verbis third feminine plural) .. The former type of mistake must be cor. rected for the parser to succeed. '.!'his correction is done by an interaction with the user. The latter type of error is bypassed by a special mechanism of defaults that enable the parser to analyse some kinds of incorrect · input. , · Portability in a language processor means that th� design can be reused for different languages without fundamental changes. The dictionaries and some of the grammatical information will be different · , but it is desirable to desigri the Nat-. ural Language Processing (NLP) component in the most general way. 1 Arabic and German are good bounding cases to test the portability of . the design. The languages are similar . in having rich inflectional_ morphology and in having vari ous forms of grammatical agreement. They are · different enough to �onstitute a · fair test of the · portability of the system. For instance, they . have different word orders: German is basically verb final, with movement of the verb in second posi tion in main clauses, while Arabic has SVO word · order, with VSO occurring frequently in surface order. · Grammatical subjects are usually dropped . in Arabic and expressed by agreement with the verb, while in German null-subject sentences are not grammatical. Small clauses are . extremely common in Arabic, . and usually copular verbs are not expressed, while German sentences present a clear distinction . between predicate� (verbs) and
· GARMAN·-_ MARTIN -MERLO -WEINBERG arguments (nouns) .. Thus, for a parser to be ap plicable to both languages, it must make use of very abstract properties of the grammar. Finally, the system must be effi, cient. Ideally, ·it.must be able to parse a sentence, detect the er rors arid produce an output in the same amount of tinie it would take a human tutor to perform the same task, otherwise the time lag would decrease the student's attention and motjvation. Compu tational efficiency must not be bought_ at the ex pense of space . compactness thougij, because the • system must fit on a PG with many other pro "'. grams running at the same time. . The principle-based approach to parsing al lowed us to meet all of these requirements. Pre vious formalisms, for example, the ·EST -version of generative grammar (Chomsky 1965(Chomsky , 1973 evaluate the performance of the parser. The part of this research which addresses issues related to foreign language training and tutoring systems is mentioned only in discussing the constraints on parsing design imposed by the application. Sec tion 2 provides an overview of the NLP system, while sections 3, 4, and 5 illustrate the routines for the recovery of phrase structure, feature an notation, and error detection, respectively. Eval uation and illustration of coverage are presented in section 6, followed by concluding remarks in section 7.

Overview
The Input/Output The input to the parser is an unannotated German or Arabic sentence. Currently the Arabic is in phonetic transcrip tion, but an interface allowing the use of Arabic script is being developed. The output consists of a parse tree which encodes the hierarchical and linear relations between the elements of the sen tence (which is passed to a semantic analyser), and a (possibly empty) list of errors in the sen tence, which is passed to the tutor. The follow ing examples show sentences with various errors which illustrate the input/output of the parser ( omitting the parse trees).
(3) There is a case selection error between "geblieben" and "in des berges". The verb "geblieben" is a state verb and takes dative case . (4) Wrong auxiliary : "hat" . The verb "geblieben" takes sein . (5) The subj ect "das frauen" does not agree with the verb "hat " in person or number .
Errors : (1) Spelling error : emphat ic/non-em phat ic substitution in "mintaqat i" (2) Case error between "minTaqat i" and "d-dibdibbatu" (3) Verb/Subj ect agreement error between "aqa9u" and "minTaqati d-dibdibbatu" These examples show a simple Prolog inter face; the tutor interface on the PC is written in an authoring language which is not discussed here. The parse trees are not displayed to the student.

The Components
The main components of the parser are a morphological analyser, a syn tactic parser, and an error handling facility. The general overview of the system is shown in Figure  1. The parser receives the input sentence and it sends it to an interactive preprocessor which ex pands possible contractions, such as zum into zu dem, and checks if the input is correctly typed. 2 Parsing and morphological analysis perform a single pass on an input sentence. The parser calls the morphological analyser to place words on the parser's buffer stack. Each call to the morpho logical analyser returns a set containing all the analyses of the next input word, as it may not be possible to determine which among them is cor rect at the point where the morphological anal yser is called. If only one analysis is selected, it may cause the parser to fail in a later state, and require backtracking. The morphological analy sers for German and Arabic are somewhat differ ent owing to the differing morphological features of the two languages.
When the morphemes are correctly identified, the word is passed to the syntactic processor. Be fore entering this stage, each token is projected to its categorial node; for instance, the verb form fiiejlt is projected to V. The shift-reduce parsing algorithm operates on a small set of context-free rules, which store only a very limited amount of hierarchical information. Other kinds of informa tion to build the right parse tree and annotate it correctly are stored in a set of constraints that must be satisfied before a rule can apply. We discuss the rules and constraints in the next two sections.

The Recovery of Phrase Structure
The parser builds structure by using an aug mented shift-reduce method (Aho and Ullman 1972) modified to be more suitable for natural language parsing. Two main modifications are used. First, the X system of our grammar frame work is minimal. Most of the work in parsing consists in constraint checking rather than ma nipulating X rules. Thus, these rules constitute a context-free backbone anchor:ing a set of grammar constraints, similar to implementations based on unification grammars, such as PATR-II (Shieber 1986) . To separate constraints from phrase struc ture, we use rules of the following form: The lefthand side is an X production, while the predicate f ( X, Y, Z) on the righthand side represents a conjunction of-grammar constraints on the features of the nonterminals which must be satisfied to license the production: The form of these constraints and the way they are applied is discussed in the section on constraints.
Second, it is necessary to express movement rules, which relate overt categories to empty cat egories (also called gaps) in a different position. Our design separates movement rules from X rules. For this purpose a move-x operation is introduced in the parse cycle. The use of gaps achieves a greater degree of generalisations in the treatment of superficially different constructions, for instance relative clauses and questions. In order to maintain a limited number of X rules, however, the computation of gaps is performed on-line, by specific routines, rather than precom piled into the rules. These two features of the parser are presented in more detail below.

The X Rules
X theory is intended to capture universal proper ties of phrase structure by means of a very small set of rules, which define the phrasal projections and their parts, distinguishing heads from non heads, the latter including complements, speci fiers, modifiers, and adjuncts. The X rules re fer only to the bar level of the phrase; they do not refer to other grammatical features ( Chom sky 1970, Jackendoff 1977. X rules are maximally binary in our system (Kayne 1984). Although they refer to phrases of a specific level, they do not refer to the specific category or features of the phrases. The complete X system employed by the German parser is given by the set of Prolog clauses in (6). The rules for Ara bic are given in (7). It is evident from (6) and (7)  A term x(Level, Category) represents a phrasal projection, where Level is the X level taking the values {0,1,2}, and Category takes as its value an atomic category symbol from the set {N,V,A,P,Adv,Det ,Infl,Comp,Conj}. For exam ple,x(N ,2) is an NP, and x(V, 1) is the first pro-jection of V. In X theory, the non terminal do main is restricted to projections of the atomic category symbols. This restriction holds in (6) and in (7) since the category of a projection is not instantiated in any of the clauses; all catego rial information in the system comes from lexical entries themselves. Each righthand side contains a head, which shares the category variable with the lefthand side; a label, which is used to index constraints and tree-building predicates; and pos sibly a satellite, which is a specifier, complement, adjunct, or modifier.
This design allows no compilation of bar level and category type, at this stage. Berwick (1991) suggests that this organisation slows down the parser, as found experimentally by Dorr (1987). However, we differ from Dorr in two main re spects: the rule set we use is much smaller, and the flow of control is serial. Assuming that the average number of conflicts in a compiled gram mar is a good indicator of the amount of non determinism that a shift-reduce parser has to face, Merlo (1992) reports comparisons of LR ta bles derived from grammars which differ only in the instantiation of the X rules. Rules like those in (6) and (7)

The Shift-Reduce Algorithm
The parser uses three primary data structures: a main stack, a buffer stack, and a hold store which contains copies of moved phrases. In addition, it takes a token stream ( the input) and outputs an annotated tree. The recursive parse procedure thus has five arguments: (8) parse(Stack, Buffer, Hold, Tree, Stream) A parse configuration consists of a 4-tuple (Stack, Bu J fer, Hold, Stream). Since the tree is used only for output, it is not included in the configuration. Various operations including re ductions, movement rules, shift, and accept, are used to go from one configu· ration to the next. It is common in shift-reduce parsing to enter a configuration from which several operations are possible. Our algorithm chooses one operation among those available by giving priority to some operations over others. To choose which opera tion to apply in a given configuration, the algo rithm uses Prolog's control strategy ( depth-first search) to select the first operation that matches the configuration. Each operation is implemented by a Prolog clause, and the clauses are ordered as in (9).
(9) 1. morphological analysis 2. accept 3. attention shift 4. move-x 5. reduce X = Y Z (binary reductions) 6. reduce X = Y (unary reductions) 7. pop 8. shift 9. fail Nondeterminism caused by lexical and struc tural ambiguity is handled in the current system . by backtracking. Despite the worst case time complexity, we have found that this approach gives gqod performance in practice. We are cur rently experimenting with the use of a graph structured stack (Tomita 1985), which allows all parser operations to be computed in parallel.
The parser accepts sentence fragments (NP's, VP's, PP's, and so forth) as well as full sentences. 4 The movement clause determines whether a movement rule should apply in a con figuration. This operation is discussed in more GARMAN -MARTIN --· ·-MERLO --WEINBERG detail in the next subsection. Binary reductions are performed by the clause in ( 10). In this clause, the parser attempts to match the top two elements on the stack with the righthand side of a binary rule of the form: The name of a rule, here indicated by the pa rameter Rule, is used to index the constraints which must apply to the feature sets of the el ements on the stack if the rule is to succeed. If a rule matches but the constraints for that rule fail, then ali attempt is made to match other rules. If the constraint succeeds, tree-building actions are performed and the parse continues with the reduced phrase on top of the stack. An uncon ditional shift simply moves the top element from the buffer onto the main stack.

The Move-x Component
Two basic types of movement rules are imple mented. The first involves movement of a max imal projection. The most common instance of this type is movement of a question phrase to the sentence-initial position, as in the German example (lla), and in the Arabic example (llb), where the question word ( ayna) is also moved to the front of the sentence. This type of movement can also generate topicalisations, clefts, and some relative clauses in both Arabic and German. The second type of movement involves move ment of a level 0 phrase (a head), which occurs in the yes/no question in (12) Thiersch ( 1978), the underlying po sition of the verb in German is the sentence-final position. This is the position occupied by the verb in a subordinate clause, as in (13) (14).

To form a yes-no question, the verb is first moved to second position, and from there to the clause-initial position. This type of movement is also used frequently in Arabic, where along with the standard Subject Verb Object word order, the Verb Subject Object order is obtained by moving the verb to the front of the sentence. An example is given in
• Stack-to-Hold Rules: put a trace of the antecedent onto the hold store • Hold-to-Stack Rules: move a trace from the hold store onto the stack.
Each type of movement rule uses a data struc ture called the Hold Store (Wanner and Marat sos 1978), which is used for temporary storage of the moved element. The Hold Store contains two cells, one for level 2 phrases (X2HOLD) and one for level 0 phrases (X0HOLD). The use of a Hold store has been criticised from a psycholinguistic and linguistic point of view (Berwick and Wein berg 1984, among others). However, recent work on the connectivity of natural languages (Sta bler 1993) suggests that allocating a (small) finite number of memory registers to each type of lin guistic entity that undergoes long-distance rela tions captures a wide-spread generalisation, both in syntax ( questions, causatives) and morphology ( applicatives, datives).
For the Stack-to-Hold operation, we must identify when a phrase is not in its underlying po sition; i.e. we must locate the antecedent. Since the type of positions to which a phrase may move is limited and predictable, the parser consults a table of move-x configurations to determine that a phrase is not in its underlying position.

For instance, the rule applies in a configu ration where the stack contains the single wh phrase in welcher Richtung ('in what direction') and where the buffer contains the verb ftieflt ('flows'). In such a configuration, a trace of in welcher Richtung is placed on the X2 hold store. The trace is identical to the antecedent in all fea tures except the spelling, since the trace does not appear in the surface form.
For the Hold-to-Stack operation, we must find the underlying position of the trace on the hold stack. Again the parser consults a table of con figurations which determines whether the trace should be moved from the buffer to the stack. For instance, this rule would apply in a configu ration where the verb ftieflt is on top of the stack, and the trace of the phrase in welcher Richtung is in the X2 hold store. There is a condition on the rule which requires that the moved phrase be a possible complement of the verb. In this in stance, the condition on the rule is satisfied, since in welcher Richtung is a possible complement of the verb ftieflen. In this configuration, the trace is moved from the hold store to the second posi tion on the stack. It is moved to second position because corn plements in German occur on the left of the verb.
We should underline once again that we have adopted a direct implementation of the princi ples of the grammar. Other approaches (Dorr 1993, Fo ng 1991 precompile the possible posi tions where an empty category can occur. Using slash rules ( Gazdar et al. 1985), in the X schema would amount to the same compilation. Clearly, our approach can lead to frequent postulation of empty categories in many positions that are not licensed by the grammar. 5 Thus, this method of recovering phrase structure information must be coupled with filtering constraints that weed out incorrect derivations as soon as possible. We il lustrate the solution adopted for this problem of interleaving the principles in the next section.

Constraints
As a result of using an X backbone to parse, most of the feature percolation and feature annotation that could be encoded in the nonterminals is per formed in this system by constraints on attribute annotation associated with each X rule. The set of constraints is partitioned into (non disjoint) subsets that are indexed to each rule, and must be satisfied for the rule to apply. For instance, the following rule is indexed into the set of con straints by the index postcomplement.

(16) x(1,C)==> [x (O,C) ,x(2,C1) ,postcomplement] .
The index postcomplement selects a subset of the pool of constraints that can apply to X rules, some of which are shown in Figure 2,   Constraints can be divided logically into two groups depending on their function in the parser. Some constraints can affect the way the parser at taches nodes to the already built structure, i.e. they can affect the shape of the tree. Other con straints do not: they simply annotate the nodes of a tree already built. Categorial restrictions on the cooccurence of phrases can affect the shape of the phrase marker. On the other hand, mor phological feature annotation and feature perco lation from the head of the phrase to its maximal projection do not really affect structure-building . decisions during the parse. We take advantage of this fact by disas�ociating feature checking that affects structure-building operations from feature percolation.
On one hand, the separation of rules from con straints has two main advantages. Firstly, it en genders a succinct grammar, because it reduces the number of X rules. We obtain the multiplica tive effect of several interacting principles, while only using memory resources which correspond to the sum of the sizes of the principles. Moreover, this design achieves language-independence, since it uses highly abstract rules. The same system of constraints, appropriately modified, is used in the Arabic parser as well. For instance, Arabic also has a rich agreement system and the parser uses the same agreement checking mechanism.
On the other hand, since category-neutral rules are used, the parser can generate many structural hypotheses which need to be filtered out. This ap proach raises the so-called interleaving problem, for both Arabic and German: how are the con straints and the phrase structure rules going to be coupled? There are three possible options: 1. All possible phrase structure rules are used, constraints are applied to a forest of trees. This approach is adequate, but it is · very space intensive, a forest of hundreds of trees can be built for even small grammars, and it is not very explanatory, in that the entire search space is visited.
2. All constraints apply at every reduction. This approach is also adequate, but it is not explanatory or efficient, because it applies many constraints in configurations where they are vacuously true.
3. Only a subset of the constraints applies to every rule.
In this system we have adopted the third ap proach. We have implemented a linking mech anism based on the syntactic configuration. In our system, configurations are partitioned into four main types (following Kornai and Pullum 1990) : complement, specifier, adj unct and modi fier. Each configuration can appear in two linear orders. A subset of the constraints is indexed to each rule, and must be satisfied for the rule to apply.
While this approach has the problem of not being sufficiently general, since careful tailoring of the interleaving of structure, category and other principles was needed, it is of interest because we found that it eliminates non-determinism more than other approaches. For example, our algo rithm to insert empty categories, which relies on structural licensing and theta assignment, is able to eliminate incorrect empty categories as soon as RULE CONSTRAINT prespecifier categorial selection agreement 0-marking feature percolation postcomplement categorial selection lexical/functional selection conjunction of likes 0-marking feature percolation precomplement categorial selection 0-marking feature percolation premodifier categorial selection feature percolation postmodifier categorial selection feature percolation preadjunct categorial selection feature percolation postadj unct categorial selection feature percolation Table 1: Interleaving of Rules and Constraints they are postulated, thus it never incurs the ex plosion, found for example, in principle-based parsers which use functional determination of empty categories (Fong 1991). Also, this ap proach does not reach the level of specificity that would confine its applicability to only one lan guage. Although we are not able to propose an algorithm to compile automatically the interleav ing of principles and rules, we propose a schema that works for such different languages as German and Arabic.
To illustrate, the complete set of X rules and the main constraints indexed into each rule are shown in Table 1. Table 2 shows what features are manipulated by each constraint. Finally, the entire pool of constraints is shown in Table 3.

Error Handling
Since the parser described so far is to be used for tutoring, one very important module of the system is the error handler which detects and di agnoses mistakes. Error tolerance is important to avoid aggravating situations in which the stu dent interacts with a system which is not suffi ciently flexible, since the typical user of this sys tem is likely to produce ill-formed input of sev eral kinds: misspellings, agreement errors, (such as wrong declension for nouns and adj ectives or wrong conj ugation for verbs), syntactic mistakes, (such as putting words in the wrong order, in Ger-  man, e.g. failing to put the verb at the end of an embedded clause) and also incorrect choice of words semantically, using for instance a move ment verb like legen instead of the static verb liegen to mean being located. The parser must also detect and identify the . error, while being able to proceed with the analysis. Because error detec tion is used to build a model of the student and to determine the sequence of learning activities, the diagnostic messages must be accurate, rather than generic. Accuracy is furthermore crucial in choosing the correct default substitute value for a piece of information, which is missing because the input is incorrect. Finally, the system must be flexible, namely detect and diagnose errors at different levels of restrictiveness.
To meet these criteria we have built an er ror handling facility which is constituted of three logical components. One component performs er-

GARMAN -MARTIN -MERLO -WEINBERG
ror detection and produces default values for the mother node if feature matching fails. Upon re duction of a rule, some constraints must be met. One of the tasks of these constraints is to com pute the feature set to be assigned to the node that results from the reduction. For example, upon reducing the rule prespecifier shown in (17) a constraint on agreement must be satisfied. The constraint states that when reducing a verb and a subject, they must agree in person and number and the subject is assigned nomina tive case. If agreement succeeds then the re�ult of the unification is used to annotate the mother node, while the error list is empty. If it does not succeed, then the feature to annotate the mother node are determined by default ( usually the fea tures of the head are simply copied), and the er ror list will contain an error code used to diagnose what kinds of errors have occurred .
A second component of the error handler pro duces messages, based on the code passed by the parser, and retrieves the lexical items which caused the error, by traversing the subtrees in the tree stack. If the error list contains more than one error code then more than one message is gener ated.
The third component is a set of control switches, which determine how restrictive the parser is going to be in diagnosing errors and reporting them to the tutoring module. Upon detection of a mistake, the error handler checks whether the switch for that particular kind of er ror is on; if it is, an error message is produced, otherwise the parse proceeds silently.
The use of constraints which are separate from phrase structure rules is crucial in supporting er ror tolerance. As discussed above, some of the constraints for feature assignment are not needed to determine the shape of the tree.

Evaluation
In this section we assess how the initial design goals of robustness, flexibility, portability, and ef ficiency have been met. There are two sides to the definition of how robust the system is. First, how wide the linguis tic coverage of the natural language processing system is, and second, how tolerant the system is to incorrect input. We have already discussed the error handling ability in some detail.
As far as coverage is concerned, the Ger man parser handles declarative, imperative, and subordinate clauses, wh-questions and yes-no questions, topicalizations, inversions, conjunc tions, constructions with multiple verbs and with modals.
The Arabic parser handles simple · declara tive sentences with differing word orders, imper atives, subjectless sentences, wh-questions and yes/no questions, simple relative clauses, noun construct constructions, clitic constructions, sim ple embeddings, and sentences with unexpressed verbs, which are very common in Arabic, and must be distinguished from fragments. Flexibility is a different way of looking at the features that support robustness. Our parsing system is flexible in the sense that it is modu lar and that some modules ( the feature annota tion constraints) may or may not be incorporated in the parser. For example, we can support two versions of this NLP system: a restrictive and a permissive version. In the latter, feature agree ments may be ignored, thus partly ill-formed sen tences can still be produced by the student with out penalty, while in the former version all the errors are detected.
Thirdly, the portability of the design is very satisfactory. Because we make use of a modu lar design and a theory of grammar that encodes universal principles, we believe that many parts of this implementation could be used for other languages. Of course, the stored words would be different, but the same design and indeed entire pieces of software could be simply incorporated in the parser for a new language. Merlo ( 1992) has kept several features of this design in an LR parser for English. The adaptation of the entire system to two very different language, German and Arabic, is done. Work is underway to adapt the system to Spanish.
The system is very compact: the German lex icon contains 5000 roots and the Arabic lexicon contains 500 roots. Since both languages have very productive morphological system, this cor responds to sufficiently large vocabularies. The German parser amounts to 1632 lines of Prolog code, while the Arabic parser to 1736 lines. The system fits on a PC platform with all the soft ware necessary to run the lesson, i.e. the tutor ing system and the software for the multi-media interface, which includes some very large audio files. The system is able to provide feed-back to the student at the same speed of a human tutor. 6 We have discussed the issues related to in-

Conclusions
This paper has presented the design and imple mentation of a parser for German and Arabic, currently used in a tutoring system for computer aided foreign language training. This is a good application to test the robustness and :flexibility of a parsing sytem, since the input is often ill formed. Moreover, reusability for different lan guages imposes a portable design. We have illus trated how to adopt a principle-based approach, where linguistic theory is used as directly as pos sible.
teraction of principles, recovery of phrase struc ture using X theory, and recovery of long dis tance dependencies, showing that a principle based approach provides an interesting experi mental answer. We have illustrated the differ ent design choices by several linguistic examples, which cover an interesting range of constructions in German and Arabic.