Coordinated Morphological and Syntactic Analysis of Japanese Language

1 Introduction

In order to speed up natural language processing, ef­ ficient parallel processing methods must be developed. Recently, we have proposed an efficient parallel parsing algorithm for general context-free grammars which rec­ ognizes an input string of length n in O(n) time with O(n 2 ) processors and memory spaces [MiTa.Am90b ]. This algorithm is optimal in the sense that, in general, almost O(n 3 ) steps are required to recognize a context-free lan­ guage on a sequential machine [Ear70, Val75 ]. Our algo­ rithm is based on an LR parsing scheme [Knu65 ]. This scheme offers two advantages: high speed analysis due to the compiled Llt parsing table and the additional ca­ pacity of left-to-right on-line parsing[Tom87 ]. However, pure context-free grammars are not enough for natural language processing. It is often desirable for each symbol in the grammar rule to have attributes[Tom87] and for each grammar rule to allow an unrestricted word order. Particularly, in order to process a Japanese sentence, a parser must be able to handle an unrestricted word or­ der.

A morphological analysis, whose processes are them­ selves performed in parallel, must be performed in paral­ lel with a syntactic analysis, and both analyses must be coordinated, so that the syntactic analysis may work up to capacity and they may perform together lexical dis­ ambiguations using bits of information provided by the syntactic analysis.

In this paper, a coordinated, parallel, morphological and syntactic analysis method is proposed. The parallel syntactic analysis performs a shift and a reducing action in parallel by using an LR transition diagram[MiTa.Am90b] which is derived from a pure context-free grammar and controls unrestricted word order by using syntactic fea­ tures. The morphological analysis uses a finite state automaton called a morphological network. The mor­ phological grammar and the syntactic grammar are inte­ grated hierarchically. This integrated grammar is called a two-level grammar. By using this grammar, a terminal symbol of the syntactic grammar is used as a process­ ing unit for both analyses. Requests for constructing a terminal symbol are passed from a syntactic process to a morphological process, and constructed candidates of terminal symbols are returned to the syntactic process. The terminal symbol stands for a special set of words called bunsetsu in Japanese, which can be regarded as a minimal semantic element in a Japanese sentence.

Section 2 describes the two-level grammar and its con­ stituents: the syntactic grammar and the morphological grammar. Section 3 describes the parallel morphologi­ cal analysis method, and section 4 describes the parallel syntactic analysis method.

2 Two-Level Grammar

2.1 Notations of Features

• BS: BS stands for bunsetsu which can be re­ garded as a minimal semantic element in a Japanese sentence. BS is denoted as follows:

N stands for a noun and nouns, V for a verb, verbs and an adjective, P for a postpositional particle, AC for an adverb and a conjunction, and AX for an auxiliary verb. 'I' means 'or', and '*' means more than 0 iterations. BS denotes relations of structural dependency: renyou 'dependent of V', rentai 'dependent of N' and danshi 'governor of V'[Haga82 ].

• GR: GR stands for the grammatical relation of some of the post positional phrases. The main par­ ticle of the phrases is called kakujoshi 'post posi­ tions with a grammatical function'.
• S C: SC stands for su bcategorizations. Each SC features can take a set of GRs as its value. The value is a list of GRs for which the verbal particle subcategorizes.
• PS: PS stands for a part of speech.

2.2 Significance of the Two-Level Grammar

The construction of our two-level grammar is shown in figure 1.

A two-level grammar is a grammar whose constituents (a morphological grammar and a syntactic grammar) are integrated in hierarchical structures. The syntac­ tic grammar consists of context-free rules and the mor­ phological grammar consists of regular rules. A termi­ nal symbol of the syntactic grammar stands for BS and it is constructed by using the morphological grammar. Since a morphological analysis can be performed by us­ ing a finite state automaton[Ama78 ], without stacks, this hierarchical construction is significant from a computa­ tional viewpoint. Also, from a semantic viewpoint, this construction is important to describe and apply local constraints for each analysis.

2.3 Syntactic Grammar

The syntactic grammar consists of context-free rules. A terminal symbol in the grammar denotes a BS. The following is a subset of Japanese grammar:

The suffixes y, t and dare connective forms between N and V; y stands for renyou, t for rentai, d for danshi. v~, n~ and nv~ (x stands for y, tor d) mean BS. Figure 2 shows the LR otransition diagram derived from this syntactic grammar. si in the goto field of this diagram means 'shift and goto state i', and ri means 'reduce and go to the state i'. The rule field means a rule number of the syntactic grammar. The info field means information used by a shift or a reducing action.

Our LR transition diagram is similar to the LR pars­ ing table [AhUI72 ], but with two additional advantages:

it has a natural form as an automaton, and it can per­ form both a reducing action and a goto action as one action[MiTaAm90b ].

2.4 Morphological Grammar

The morphological grammar consists of a set of regu­ lar rules producing BS. The grammar is transformed into a finite state automaton called a morphological network. A state of a morphological network denotes either a part of speech or a word itself. A link stands for a connec­ tive relation between words. The morphological network consists of two networks: a nominal network, which con­ structs n~ and a verbal network, which constructs v~ and nv.,. The following is an example of production rules for n~, v~ and nv~:

( Pca·el: ga, wo, ni, de ... ) ( Poddl: no, dake, bakari ... ) ( ppre: ha, mo, sae, koso ... ) ( Pcaae2: to, ni, ya, ka, no ... ) ( Padd2: dano, yara, nari ... ) ( Pconj: ga, kara, to . . . )

n and v~ stands for a noun and a verb, respectively. Both Pca .. l and Pca··2 stands for a postpositional parti­ cle with a grammatical function. A Pca··l is a dependent of V. A Pcaae2 is a dependent of N.

A syntactical grammar (Context-free Grammar) An LR transition diagram A morphological grammar (Regular Grammar) A morphological network

Figure 1: The construction of a two-level grammar

3 Parallel Morphological Analysis

The morphological analysis corresponds to a shift ac­ tion of a syntactic analysis. In the morphological analy­ sis, a process is created by a construction-request for BS issued from a parsing process. The request has the form < N, i >, where N is a state name of an LR transition diagram, and i is a pointer to an input symbol called an input pointer for short. Extracting BS is performed simply by a process moving from the initial state to a final state in a morphological network. Since a morpho­ logical network is, in general, a non-deterministic finite state automaton, when a morphological process arrives at a final state, but it can still go on to to other fi­ nal states, then, it creates a new process that resumes the syntactic analysis and returns BS information to the parsing process which had requested the production of the BS. So, the morphological process proceeds from one final state to another. BS information has the form: < N,PS, word,gr,sem, i,j >, where word is a BS ex­ tracted from a given input string. gr is a GR. sem is an item of semantic information. Both i and j are posi­ tions of the word in the input string. In order to avoid duplicated analysis, each word, which is extracted during the morphological analysis, is stored in a table, and its morphological information is accessed directly by using an input pointer.

The coordination mechanism for morphological and syntactic analyses is shown in figure 3. Both processes with < N3 , 4 > and < N2 , 4 > access 4, then a morpho­ logical process is created and the morphological analysis begins, because the BS information has not been held as an entry, namely, the tag of the table is off.

4 Parallel Syntactic Analysis

4.1 Parallel Parsing Model

Our parallel parsing model is called a DAG(Directed Acyclic Graph) array parsing model[MiTaAm90b ]. This model has a CREW(Concurrent-Read Exclusive-Write) type three dimensional shared memory, called a DAG memory. A cell of the DAG memory denotes an element of DAG called a DAG node. The DAG node has the form:< N,PS,i,j >. Each cell of a DAG memory can be directly accessed by a DAG node name used as an index. A processor is assigned to each DAG node. All processors act asynchronously. The DAG array parsing model is shown in figure 4.

4.2 Parallel Parsing for Context-free Grammars

Our parallel parsing method[MiTaAm90b] is called a generalized parallel LR parsing scheme. It extends an LR parsing method for general context-free grammars by using a DAG which allows multiple stack entries in­ stead of a conventional stack [MiTaAm89, MiTaAm90b ]. Similar parallel parsing schemes have been pro­ posed by Tomita[Tom87 ], Yasutome[YaAo88 ], and Numazaki[NuTaTa89, NuTa90 ].

In our parsing method, parallel shift-reducing actions are controlled by means of an LR transition diagram [MiTaAm90b ]. A DAG node is produced by ~ sh~ft or a reducing action, and then the processor, wh1ch 1s as­ signed to a newly produced DAG node, is activated. The DAG node is held as an entry in a DAG memory cell to avoid producing the same DAG nodes. If there are several conflicts between shift and reducing actions at any state, all those actions are performed in parallel, be­ cause one different processor is activated for each action. Thus, all actions which can be performed at any state, do not have to be synchronized with an input symbol. In order to inhibit the exponential increase of activated processors, and to avoid redundant actions, we use the following strategy:

• Only processors assigned to a DAG node, which has not been held in an DAG memory entry, are activated.

• The results of shift/reducing actions performed by any processors are stored, so they can be shared by processors about to perform those actions.

According to this strategy, first, all parsing trees with the same top vertex are packed, and their vertices are unified into one vertex. This strategy is controlled by checking whether a DAG node has been held as an entry in the DAG memory or not. Then, only one symbol for each grammar rule is assigned to each reducing action, which is therefore called a one-symbol reduction. The one symbol reduction consists of two actions: a reducel and a reduce2 action. A reduce! action is a one-symbol reduction for the rightmost symbol in a grammar rule, and a reduce2 action is for the other symbols, i.e., for a reduction by A -+ B C, a reduce! action performs a one-symbol reduction for C, making a rule-with-marker [A -+ B · C). A reduce2 action performs for B and completes the reduction. The result of each one-symbol reduction is called reduced information which has the form< [A -+ a·.BJ, i, N >. [A -+ a·.BJ stands for reductions of {3 from [A -+ a.B·]. i is an input pointer. N is a state where the reduction by A -+ a,B was executed. A table in which reduced information is stored is called a reducing table. Each consists of 2 tables: a reference table and an entry table, which are both CREW type shared memories. A reference table has a field, which is used to check whether reduced information has been held as an entry or not. An entry table has a field used to store reduced information, which is written in the field from top to bottom. A reducing table is assigned to each DAG node produced by a shift action. Reduced information is passed through a reducing table between DAG nodes. Reduced information is then processed in pipeline-like processing through reducing tables. Our parallel parsing method is described as follows:

[Parallel Parsing Methodjl

1. Start: A processor assigned to the DAG node < No, nil, 0, 0 > starts a shift action.
2. Activate a processor: If a processor produces, in a shift or a reducing (reducel/reduce2) action, a DAG node dn, for which no entry exists, then the processor makes an entry dn and activates a new processor assigned to dn.
3. Execute a shift/reduce! action: a newly activated processor performs shift and reduce! actions.
4. Execute a reduce2 action: After performing a shift action, a processor P executes a reduce2 action. If there is no reduced information in a field accessed by P, P waits until some reduced information is put to an entry. Then P reads it and performs a further one-symbol reduction according to it. P also activates a new processor P', which is newly reassigned to the same DAG node previously as­ signed to P and reads the next reduced informa­ tion2.

1 For brevity's sake, the linkage of a DAG node to reduced infor­ mation, which is actually required, is not described. This linkage is performed by reducel/reduce2 actions.

2 This newly activated processor is necessary to link a DAG node to reduced information.

1. Accept/Reject: If the processor assigned to < No, S, 0, n >(No and S are a start state and a start symbol, respectively.) is activated by a reduce! or reduce2 action, and this processor reads the ter­ minal symbol '$'{the end mark), by a shift action, then the input string is accepted. If there are no processors performing a shift and a reduce! action, the input string is rejected.

4.3 Handling Syntactic Features

In order to extend the syntactic analysis method of 4.2 so that it can handle syntactic features, reduced infor­ mation is improved as follows:

[Definition 1] reduced information: Reduced infor­ mation is defined as < [A -+ a· {3], sc, i, N >, where sc means a list of SC features which has the form:( { sbj, objl, ... }).

The reducing table is also extended for the newly de­ fined reduced information. Table 1 shows the extended reducing table. By handling these syntactic features, a reduce2 action follows the constraints:

Constraints for a reduce2 action

• Inhibition of duplicated reference: In per­ forming reduce2 actions, if an element of SC in reduced information is in agreement with the GR component of a DAG node, the element is marked with '*'· If, during a reduce2 action, a GR com­ ponent, which matches a marked element is found, the reduce2 action aborts.
• Inhibition of wrong type reference: If, dur­ ing a reduce2 action, a GR component does not match any element of SC in reduced information, the reduce2 action aborts.

As mentioned above, the syntactic analysis is allowed to handle an unrestricted word order by using SC fea­ tures as a list, since GR is not attached to PS. This method is also adopted by JPSG[Gun87 ].

In figure 5, the parsing of Japanese sentence Watashi ha Kare ni Australia ni lieu to Itta(I told him that I would go to Australia.) is shown as an example. The form of the DAG node used in this example is < N, PS,fs >. The fs has the form [GR][{SC}], where "[ ]"means optional. No marked SC feature means a gap(missing constituent). In the figure, sbj which is a SC feature of the verb Iku, stands for a gap. The reduc­ tion by Vd-+ N 11 Vd with both < 5, N 11 , obj2 > and < 5, V)d, { sbj, objl, obj3*, { sbj, obj2}} > failed because obj2 is not in agreement with any subcategorization el­ ements in the list{sbj, objl, obj3*}.

5 Conclusion

We proposed a coordinated parallel processing method for morphological and syntactic analyses of Japanese lan­ guage. The proposed parallel parser is extended from the previous parser[MiTa.Am90b] so that it can handle syn­ tactic features. From the computational viewpoint, it is significant to use a two-level grammar with a morpholog­ ical and a syntactic grammar integrated hierarchically, using bunsetsu as a processing unit for both analyses. We are now implementing this method on Sequent Sym­ metry S-2000, a 20-CPU multi-processor system.

It must be noted that this method is not complete in the sense that it does not handle semantic features. This method, however, can be extended to include a semantic processing component, which performs, in coordination with morphological and syntactic analyses components, parallel semantic and pragmatic analyses on a semantic network, based on the situation semantics theory.