JPS6033663A - Analysis system of sentence structure - Google Patents

Abstract

PURPOSE:To attain a sentence structure analysis system which can perform the continuous analysis by analyzing repetitively the transition of state with reference to a sentence structure rule table and then skipping words in case the transition conditions have no correspondence owing to word errors, etc. CONSTITUTION:A word analysis part 1 separates an input sentence into words and sends them to a sentence analysis part 2. The part 2 refers to a sentence structure rule table 3 and at the same time repeats the transition of state. If an error is detected, the part 2 refers to a continuation condition table 4 and skips properly the input. The table 3 contains the conditions of transition, the state of the transit destination and the normal transition/cut in response to the present state. The ''cut'' means that a back track is suppressed with a special transition of state. Thus an input error is recognized and furthermore the input is skipped until the continuation conditions are satisfied after an error is detected. Then the subsequent analyses are continued. The table 4 contains the information on the continuation conditions produced in response to each state. In such a way, it is possible to obtain a sentence structure analysis system which can recognize the errors of input sentences and then continue the subsequent processes.

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention relates to sentence analysis of an input sentence, and in particular, to a syntax that non-deterministically interprets an input sentence by backtracking syntactic rules. It concerns the analysis method.

[Prior art and problems]

Conventional parsing methods include deterministic parsing methods and non-deterministic parsing methods. In the former method, for example, when a noun phrase is analyzed in a synopsis-CM' analysis, if there is actually no noun phrase, it is determined as an error, and the degree of freedom in the syntax is narrow. Therefore, designing a grammar so that it can be analyzed definitively requires advanced theory, and its development requires specialized knowledge regarding syntactic analysis. Therefore, a lot of effort is spent on developing, maintaining, changing, and modifying it. Nowadays, machine interfaces are often developed), and the cost of developing them is sought to be reduced. On the other hand, the latter non-deterministic analysis method, for example, first analyzes the noun phrase,
If there is no noun phrase, the next sentence may be interpreted as a question, so something other than a noun phrase may come. Therefore, no special expertise is required for development, and it can be applied to very general syntax rules that are close to natural language. However, since bank tracking is performed even for errors in the input sentence, assuming that it can be analyzed using a different syntax, it is difficult to provide a function for detecting errors and continuing processing. .

[Purpose of the invention]

The present invention is based on the above considerations, and is a first method that can support the easy development of a parsing system that does not require specialized knowledge and has the function of recognizing errors in input sentences and continuing analysis. The purpose of this paper is to provide a text MT analysis method.

[Structure of the invention]

To avoid this, the syntactic analysis method of the present invention includes a word analysis unit that cuts an input sentence into words, a syntactic rule table that sets syntactic transition conditions, transition destination states, and information indicating whether it is a normal transition or a cut for each state. , a continuation condition table that sets continuation conditions for each state, and a syntactic analysis unit that receives words from the word analysis unit and parses the input sentence. The syntactic analysis unit repeatedly analyzes the state transition to the transition destination state according to the transition condition while referring to the syntax rule table, and analyzes the words of the input sentence after the state transition indicates a cut. If there is no transition condition corresponding to the above transition condition due to a reason such as an error in the above, the system is configured to refer to the above continuation condition table, skip the words of the above input sentence according to the above continuation condition, and execute the process. It is characterized by the fact that

[Embodiments of the invention]

Embodiments of the present invention will be described below with reference to the drawings.

Fig. 1 is a diagram explaining an example of syntactic rules for English sentences, Fig. 2 is a diagram showing functional blocks of the syntactic analysis system of the present invention, and Fig. 3
Figure 4 is a diagram explaining a syntax rule table to which the present invention is applied, Figure 4 is a diagram explaining a continuation condition table to which Kibatsu 1 is applied, and Figure 5 is a diagram illustrating a continuation condition table to which the present invention is applied. It is a figure explaining the flow of processing. In the figure, 1 is a word analysis unit, 2 is a syntax analysis unit, 3 is a syntax rule table, and 4
indicates the continuation condition table.

The present invention introduces a special state transition called CIIL into the syntax rules to suppress input errors by suppressing puncture tracks. Furthermore, the continuation conditions for each transition state are set in advance, and after an error is discovered, input is skipped until the continuation condition is satisfied, and the analysis after υ is automatically continued7.

An example of the English syntax rules of the present invention is shown in FIG. 1, where circles represent states, double circles represent final states, and arrows represent transitions. Furthermore, Figure 1 (
a) First, it starts from state S, and when a noun phrase comes, it transits to state S. When a verb phrase comes, it transits to state S. However, it starts from state MS+, and when it is not a noun phrase, Next, check whether an auxiliary verb comes, then a noun phrase, a verb phrase,
A question mark appears, indicating a transition from state S to S6.

When the state transitions to state S, it can be seen that the input sentence is an interrogative sentence. In addition, when examining state S1 with the assumption that a noun phrase will come next, as shown in Figure 1(b), start from state NI, and if an article comes there, confirm that it is a noun phrase. can be done. Therefore, in this case, we transitioned to state N as a cut and checked the next one, and as a result, even though no noun or adjective came, we determined that it was already a noun phrase and made it a cut. Recognize mistakes without backtracking.

Then, skip that part and continue processing from the next part.

For example, if an error is discovered in the state Ss, N+ -Nt, backtracking is not performed and the next state is Nz
or continue from state S, in which case it starts from state Vl shown in FIG. 1(C). Figure 1 (
The syntax rule for the sentence shown in a) is, for example, the following calculation-like input format.

(sentence (51(if noun-pha)
se -JS,)(if auxi 1iary-v
erb −+j31 ))(82(if verb-p
hase -1-8,))(Ss (if period
d -& )) (34accept) (35(if noun-pbase -+3. ))
(Sa (if verb-phase -8,))(
S, (if question marlc 4s) (83accept) Here, in the state S of the sentence, if it is a noun phrase, it transitions to state S, and if it is an auxiliary verb, it changes to state S. It means transition.

Also, in state S, if it is a verb phrase, state S3
This means a transition to . The same applies below. Furthermore, an example of a noun phrase is shown in Section 1S (b), and its computer input format is as follows.

(noun-phase (N, (if article
e :==;>N,))(N, (if adject
ive-4J, )) (if noun -1-N,
)) (NS accept) Figure 1 (C) shows an example of a verb phrase.
The computer input format is as follows.

(verb-phase (V, (+ f verb
→Vl ))(Vl (if adverb -4V,
)accept)) In the above computer input format, → stands for cut (cu
t).

Next, a specific example of syntactic analysis will be explained with reference to FIG. When performing syntax analysis using English text as input,
When the article is input, the beginning of the noun phrase is determined, and it is meaningless to backtrack before that point.

Therefore, the transition between states N1 and N shown in FIG. 1(b) is cut. For example, when the input sentence is "The airplan flies 5peedi", first, the state S shown in FIG.
, and parse whether a noun phrase exists. As shown in FIG. 1(b), the noun phrase analysis starts from state N and transitions to state N2 by the prefix RWJThe.

The next word arrpIan is misspelled (airplan
e) is neither an adjective nor a noun and cannot transition from state N, so the noun phrase analysis has failed. However, since the transition from state N to state N was a cut, backtracking is prohibited and it can be recognized that there was an error. Therefore, after issuing a warning indicating that there was an error, analysis f: Continue. In this case, the continuation condition for state N is that the next word is an adjective or noun, and the continuation condition for state S2 is that the next word is a verb, so a
Skip iplan and return to state S from the next fly.
, can be followed by 0 丑 た, e.g.) A sentence starting with low may be an interrogative sentence, but it may also be a Jl & lament sentence. Therefore, in the case of this sentence, first we assume that it is an interrogative sentence, then check what comes after IOW, and if do is found, it can be confirmed as an interrogative sentence, otherwise it cannot be determined as an interrogative sentence, and is an exclamatory sentence. As a result, we can check the next part of J(ow, and if you comes, it can be confirmed as an exclamatory sentence.In this way, just because the sentence starts with 110w, we cannot immediately confirm the sentence, but the following If a sentence can be determined by a word, cut at that point and backtracking is prohibited12.
After that, if the transition condition is not met, it is treated as an error υ, skipped, and the analysis continues.

Note that the continuation conditions for each state can be set as follows.

(b) The continuation condition for a state is the union of transition conditions for transition from that state.

When the transition is a word, the transition condition is that the next input is that word.

(c) When the transition is a syntax, the transition condition is the continuation condition of the syntax.

) The continuation condition of a construct is the continuation condition of the first state of that construct.

FIG. 2 shows functional blocks of the parsing system of the present invention. In FIG. 2, the word analysis section 1 divides the input sentence into Rin words and passes them to the syntactic analysis section 2.
The syntax analysis unit 2 repeats state transitions and analyzes while referring to the syntax rule table 3, and if an error is found, it refers to the continuation condition table 4 and skips input appropriately to continue processing. . Syntax rule table 3 is the third
As shown in the figure, the continuation condition table 4 has information on transition conditions, transition destination state, and normal transition/cut corresponding to the current state, and the continuation condition table 4 corresponds to each state as shown in FIG. It contains information on the continuation conditions generated by the algorithm described above.

Next, the flow of processing by the syntax analysis section will be explained with reference to FIG.

(2) Set the variable cs that holds the state reached up to the present time to the initial state, and set off the flag that prohibits backtracking. Next, perform the process (■).

■ Check the status of variable cs.

Analysis success (SUCCESS) if the final state is indicated,
, and if it indicates a state other than the final state, process (■) is performed.

■ Refer to the syntax rule table using the variable cs as a key,
The transition conditions are tested in order to determine whether the transition is possible.

In the case of Yes, the process ``■'' is performed, and in the case of NO, the process ``■'' is performed.

■ Refer to the syntax rule table and set variable cs to the transition destination state. Next, perform the process (■).

■ Check whether it is cut or not.

In the case of Yes, perform the processing in ■, and in the case of NO, return to the process in ■. 0 ■ Set the flag on. As a result, nokutsuku trucks are banned. Next, return to the process of ■.

■ Check whether the flag is on or off O If it is on, perform the process (■), and if it is off, it will be treated as an analysis failure (FAIL) and a back track will be performed.

■ Refer to the continuation condition table and check whether it is possible to continue.

If Yes, return to the process of ■ and restart the analysis, and then select NO.
In this case, process ■ is performed.

■ Skip input words. Next, return to processing for (seconds).

Therefore, the input word is skipped and the analysis is resumed when it becomes possible to continue. Also, once the flag is turned on, parsing of this syntax is guaranteed to succeed and no backtracking occurs.

Note that in the syntax analysis system shown in Figure M2, only the syntax rule table 3 and continuation condition table 4 need be made different for each application.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, a syntax analysis system capable of recognizing errors in an input sentence and continuing subsequent processing can be used to analyze syntax rules without requiring specialized knowledge. It can be easily developed by simply applying it.

[Brief explanation of drawings]

Figure 1 is a diagram explaining an example of syntactic rules for English sentences, and Figure 2 is a functional block side story of the syntactic analysis system of the present invention -F1 Momme-
Figure 4 is a diagram explaining a syntax rule table to which the present invention is applied, Figure 5 is a diagram explaining a syntax rule table to which the present invention is applied, and Figure 5 is a syntactic analysis unit to which the present invention is applied. FIG. 1...Error code analysis section, 2...Syntax analysis section, 3...Syntax rule table, 4...Continuation condition table 0 Patent applicant Fujitsu Ltd. representative patent attorney Kyotani Yobuge 1. h) ′;t 2 (2)

Claims (1)

[Claims] A word analysis unit that separates input sentences into words, a syntax rule table that sets syntactic transition conditions, transition destination states, and information indicating whether it is a normal transition or a cut for each state, and a continuation condition for each state. A syntax analysis method in a syntactic analysis system comprising a continuation condition table and a syntactic analysis unit that inputs words from the word analysis unit and analyzes M′ of the input sentence, the syntax analysis unit Analyze by repeating the state transition to the destination state according to the above transition conditions while referring to the syntax rule table, and find that there is an error in the word of the input sentence after the state transition indicates a cut. If there is no transition condition corresponding to the above transition condition due to factors such as
- A parsing method characterized in that it is configured to skip and execute processing according to conditions such as Jlit 4 or 11 door size.