Data processing system implemented process and compiling technique for performing context-free parsing algorithm based on register vector grammar

• US 5,095,432 A
• Filed: 07/10/1989
• Issued: 03/10/1992
• Est. Priority Date: 07/10/1989
• Status: Expired due to Term

• Current Assignee: Harris Corporation Melbourne
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Reed, Jonathan H.
• Primary Examiner(s): Jablon, Clark A.
• Application Number:
  US07/377,152
• Time in Patent Office: 974 Days
• Field of Search: 364/419, 364/200, 364/900, 364/972.1, 364/274.8
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A context-free parsing algorithm employing register vector grammars provides fast parsing of natural languages. A compiler for register vector grammars accepts input grammars as standard phase structure rules and generates strongly equivalent grammars in register vector grammar form. By applying the context-free register vector grammar parsing algorithm to the resulting grammars, strings may be parsed and trees may be constructed in the same manner performed with phase structure grammar.

Claims

1. A method, utilizing a data processing system, for compiling context-free phase structure grammar productions into context-free register vector grammar productions and parsing a word string, said method comprising the steps of:

a) translating the phase structure grammar productions for a given nonterminal category into a finite-state automaton such that each phase structure grammar production is represented by an independent sequence of transitions beginning at an initial state;

b) reducing the finite-state automaton by removing nondeterminism, removing inaccessible states, and merging indistinguishable states;

c) translating each of the finite-state automaton states into a register vector grammar production; and

d) repeating steps a) -c) for each nonterminal category to translate the entire phrase structure grammar into register vector grammar; and

e) parsing a word string to determine whether the word string is a member of the language defined by the register vector grammar.

2. The method of claim 1 wherein step c) is performed by:

(1) distinguishing input tokens which transition to each state from input tokens which transition to other states;

(2) setting up a register vector grammar table having rows defining register vector grammar productions, including an initialization vector and a close vector, and columns defining the category c, condition vector cv, and result vector rv of each production;

93) mapping the initial state into the initialization vector containing 1 for each token on which there is a transition from the initial state and a 0 for each remaining token;

(4) mapping each of the remaining states into a row of the register vector grammar table, wherein;

(a)the category of the production is the same as the state'"'"'s input token;

(b) the condition vector of the production contains a 1 for the token on which the state transitions to some other state and a 0 for the remaining tokens except for one marked close; and

(d) if the state is final, then the close token of the result vector contains a 1 and otherwise contains a 0; and

(5) assigning the close vector a 1 for the close token and a 2 for the remaining tokens.

3. The method as claimed in claim 1 wherein the merging of the indistinguishable states in step b) comprises utilizing the Pairs Table algorithm.

4. The method of claim 1, wherein the word string has n tokens X₀, X₁ X₂ ... X_i ... X_n-1, followed by a dummy terminator symbol X_n, and wherein step e) is performed by the steps of:

(1) constructing a set of states S_i, where i initially equals 0, containing the single state <

c, v, f>

, where c is the root category of the grammar, v is the initialization vector associated with c, and f equals 0;

(2) processing the state in set S_i by scanning the register vector grammar productions associated with c to find those productions whose condition vector cv matches v, using a rvg-match operation;

93) for those register vector grammar productions whose category is nonterminal and which in step (2) match, applying a predict operation to the state and to the production by adding to set S₂ a new state consisting of the production'"'"'s nonterminal category, the initialization vector of the category, and index i;

(4) for those register vector grammar productions whose category is terminal and which in step (2) match, with the terminal being the same as input token X_i, applying a shift operation to the production and to the state by adding to set S_i+1 a copy of the state being processed, with the vector thereof updated by applying the result vector rv of the production to v, using an rvg-apply operation;

(5) matching the close vector associated with c to v to determine whether the complete operation is applicable to the state;

(6) recognizing each state <

d, w, g,>

in set S_f in which d is nonterminal, d has a production whose category is c, and the cv of the production matches w, using the rvg-match operation; and

(2) adding to set S_i a copy of each state <

d, w, g>

with the vector thereof updated by applying the rv of the production to w using the rvg-apply operation;

(7) repeating steps (2)-(6) for each additional state <

c, v, f>

) in set S_i added by steps (g) and (j);

(8) repeating steps (20-(7) for sets S₁ ... S_n ;

(9) matching the close vector of the root category c with the vector v of each state in set S_n whose category is c, using the rvg-match operation; and

(10) recognizing a successful parse of the word string when a match of step (9) is successful, and otherwise recognizing that the word string is not a member of the language defined by the register vector grammar.