Abstract:
An operator-precedence parser is disclosed that incorporates enhancements that support analysis of human languages. Operator-precedence parser are typically used to analyze arithmetic expression in calculators. Enhancements include allowing the result of applying an operator to be another operator; allowing elements to have a priority as an operator and a priority as an operand; allowing operands to have their priority determined by context; allowing a series of priorities to be specified for operators. These series of enhancements enable analysis of sentences that are more complex than can typically be handled by declaration based parsers. For example, the utterance “move tank1 and tank2 to position1 move tank2 to position1 fire tank2 at tank1 fire tank3 at tank1 6*6” can be successfully analyzed by a working system.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    Not Applicable 
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    Not Applicable 
       REFERENCE TO SEQUENCE LISTING, A TABLE, OR A COMPUTER PROGRAM LISTING COMPACT DISK APPENDIX 
       [0003]    The listing main.txt created on Dec. 1, 2010 with size 54,654 bytes contains an implementation of an enhanced operator precedence parser. The implementation language is Prolog. ‘matrix_next’ contains the top level function implementing the algorithm. ‘matrix_select_operators’ selects the operator to apply. ‘matrix_apply_operator_one’ applies the selected operator. ‘selector’ is used to select the arguments. \matrix_apply_evaluator’ applies the selected operator to the selected arguments. 
       BRIEF SUMMARY OF THE INVENTION 
       [0004]    An operator-precedence parser is disclosed which incorporates enhancements that facilitate analysis of human languages. In extant models for operator precedence parsing (such as the Shunting Yard algorithm) an operator is assigned a priority number. That number determines how the parser will build the structure of the expression. The parser applies the operators in order of precedence. Once an operator is applied the result is terminal symbol. Operators are applied highest priority first until a final since value is produced. This is typically used for analyzing arithmetic expressions. Enhancements advanced extent this approach to handle unrestricted natural languages. Enhancements include allowing the result of applying an operator to be another operator; allowing elements to have a priority as an operator and a priority as an operand; allowing operands to have their priority determined by context; allowing a series of priority to be specified for operators. These series of enhancements enabled analysis of sentences that are more complex than can typically be handled by declaration based parsers. 
       BACKGROUND OF THE INVENTION 
       [0005]    This invention disclosed herein relates to creation of structure data from plain text and more particularly to a processor that creates structured data from plain test using an enhanced operator precedent parser. 
         [0006]    There is a strong desire arising to provide every person access to the power of computers. This requires that computer systems that are able to interact using languages natural to users. Typical approaches to analyzing the structure of languages use declarative grammar based-approaches that fail to address complex linguistic structures that are commonly presented. 
         [0007]    Time has shown that declarative grammar based approaches such as unification grammars are not easily extended to effectively handle common problem such as conjunction, incompleteness and multiple languages. This is the case although a large number of resource have been applied to the declarative grammar approach. 
         [0008]    Early in the development of computer science an alternative approach for analyzing expression structure was defined. This is operator precedence parsing. These types of parsers are typically used to convert expressions in infix notation into reverse polish notation for evaluation as used in hand calculators. A well known implementation using the Shunting Yard algorithm developed by Edsger Dijkstra. 
         [0009]    The configuration of an operator precedence parser contains associations between operators and control parameters. A control parameter is a 3-tuple comprising a numeric priority, an argument type and semantics for applying the operator. The argument type specifies how the operator selects its arguments. For example, the ‘+’ operator selects one argument from the left side and one argument from the right side of the operator in the expression; the unary ‘−’ operator selects one argument from the right side of the operator in the expression. The semantic for applying the operator is the definition of how to calculate the result of applying the operator to the arguments. 
         [0010]    What follows is a worked example for the operator precedence parser. The table in  FIG. 1  also known as a lexicon defines the operators. In this case xfx means an operator that takes two arguments one from the left and one from the right side. fx means a unary operator that takes one argument from the left. This notation is a standard available in a well known computer language called Prolog. Number are represented symbolically in the tables using the “&lt;numbers&gt;” entry. 
         [0011]    The simplest algorithm for implementing an operator precedence parser would be 
         [0012]    1. Lookup each token in the lexicon and augment them with the control definition in order to create the list of elements. This is called Es. 
         [0013]    2. For each token lookup up the control in the lexicon. 
         [0014]    3. While there is more that one element in the list, Es
       A. Find the left-most operator with the highest priority. This is called O. If there is no O then proceed to step 4.   B. Using the type, select the arguments, called As.   C. Apply the evaluator to the arguments and replace O and As in the list Es with the result that has priority zero, type of number and no selector or evaluator.       
 
         [0018]    4. Emit the list Es as the result 
         [0019]    What follows is a worked example for the input “6+5*−2” assuming steps one and two have been performed.  FIG. 2A  shows the initial state of the calculation. 
         [0020]      FIG. 2B  show the result of applying one iteration of the algorithm.
       A. Element A 5  is selected as the operator since the priority is the highest   B. Element A 6  is selected as the argument.   C. Elements A 5  and A 6  are replace by the result at position B 5 .       
 
         [0024]      FIG. 2C  shows the result of the next iteration of the algorithm.
       A. Element B 4  is selected as the operator since the priority is the highest   B. Element B 3  and B 5  are selected as the arguments.   C. Elements B 3 , B 4  and B 5  are replaced by the result at position C 3 .       
 
         [0028]      FIG. 2E  shows the result of the final iteration of the algorithm.
       A. Element C 2  is selected as the operator since the priority is the highest   B. Element C 1  and C 3  are selected as the arguments.   C. Elements C 1 , C 2  and C 3  are replaced by the result at position D 1 .       
 
         [0032]    The calculation is now complete. 
         [0033]    This example illustrates the main control structure which comprises a priority for determining when to apply an operator, a type for determining what the apply the operator to and a semantic for calculating the result of applying the operator. What follows is an invention that extends the features of the operator precedence parser to be able to handle constructs that arise in natural languages used by humans. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0034]      FIG. 1  shows operator definitions for a simple operator precedence parser 
           [0035]      FIG. 2A  shows input for sample parse 
           [0036]      FIG. 2B-D  shows example parse matrix steps 
           [0037]      FIG. 3  shows selector definition for a natural language parser 
           [0038]      FIG. 4  shows evaluator definitions for a natural language parser 
           [0039]      FIG. 5  shows selector definitions for a natural language parser 
           [0040]      FIG. 6  shows constructor definitions for a natural language parser 
           [0041]      FIG. 7  shows old operator definitions using the new model 
           [0042]      FIG. 8A  shows lexicon definition for example one 
           [0043]      FIG. 8B  shows input for example one 
           [0044]      FIG. 8C-L  shows example one parse matrix steps 
           [0045]      FIG. 9A  shows the lexicon for tokenization example  FIG. 9B-C  shows example parse matrix steps 
           [0046]      FIG. 10  shows definitions for common English work/phrase types 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0047]    The basic operator precedence parser specifies a priority and semantic for each operator. The priority is a number that is used to determine the order that operators are applied. The semantic is an method that provides the steps to perform a calculation on the arguments. In the enhanced operator precedence parser presented here the priority and semantic specification are extended. This is know as the control definition. The control is a list of single control definitions. 
         [0048]    This invention extends the control definition for operators as follows. For reference to the simple control definitions see  FIG. 1 . 
         [0049]    The priority is extended from being a single number to a pair. There is one priority for the element as an operator and one priority for the element as an operand. When selecting the highest priority operator, the operator priority is used. When being selected as an operand for another operator, the priority of the element as an operand is used. A subsequent example will demonstrate verbs and adverbs being defined as operators. An adverb will take a verb as an operand and will evaluate to a verb type operator. When the priority as an operator and an operand are the same only one number will be show in the table. 
         [0050]    The type is extended to provide operators for selecting arguments from the matrix containing the current set of elements. The type is a pair of selection operators. One for selection from the left of the operator and one for selection from the right of the operator. The selection commands are defined in  FIG. 3 . 
         [0051]    After the operator is applied based on the priority and the arguments are selected using the selectors, the evaluator is used to calculate the value of applying the operator the arguments.  FIG. 4 . shows evaluator definitions. 
         [0052]    The matrix that the processing is performed in can contain any type of element as long as the semantics can process them. One such type is the linguistic frame. This will be shown for illustrative purposes. Examples of elements that could be in the matrix are phonemes, characters, words, function calls. Although the examples demonstrate parsing and tokenization, other stages of analysis can be performed in this model as well. 
         [0053]    For extant implementations the linguistic frame is used to represent the structure of the utterance. The linguistic_frame has the form linguistic_frame(Type, Word, Cases). Cases a list that associates a case name with a value. A sample linguistic_frame would be 
         [0054]    linguistic_frame(verb, is, [subject-(the sky), direct_object-blue]). 
         [0055]    This would correspond to a sentence such as “The sky is blue”. 
         [0056]      FIG. 5  shows the table that describes the control selector parameters for the linguistic frame evaluator.  FIG. 6  shows the table that describes the constructor parameter for the linguistic frame evaluator. For each element, the control is an ordered list of 3-tuple comprising (Priority, Selector, Evaluator) using the enhanced definition for these components. The table of the simple operator precedence parser example can be updated under the new model as seen in  FIG. 7 . 
         [0057]    The final piece is to update the algorithm converting the input into a value. The generalized method is as follows. 
         [0058]    Input: A sequence of characters. 
         [0059]    Output: A sequence of elements 
         [0060]    Method: 
         [0061]    1. Lookup each token in the lexicon and augment them with the control definition in order to create the matrix of elements. This is called Es. 
         [0062]    2. Set a list of operators to empty. This is called O. 
         [0063]    3. Find the element in Es with the highest operator priority not in O. This is called E.
       A. If no such element exists then proceed to step 4.   B. Add the element E to the set O.   C. Use the selection expression to select the elements from the matrix. These are the arguments that are called A.   D. If the selection fails proceed to step 3.   E. Apply the evaluator to the arguments A to yield the result R.   F. Replace the selected element E and the arguments A with the result R in the list of elements Es.   G. Proceed to Step 2.       
 
         [0071]    4. Find the element with the highest operator priority 
         [0072]    5. If such an element exists remove the first control definition and replace it in the list Es. Proceed to step 2. 
         [0073]    6. Emit the current sequence as the output. 
         [0074]    What follows is a worked example of the enhanced operator precedence parser. Assume the lexicon in show in the table in  FIG. 8A  and the input shown in the table in  FIG. 8B . After performing step one the matrix of elements, Es, is as shown in  FIG. 8C . 
         [0075]    The first iteration of the loop produces the matrix shown in  FIG. 8D . The steps are as follows. 
         [0076]    2. The list O is set to empty 
         [0077]    3. The element with highest priority is number C 3 .
       C. The selection expression selects elements C 2  and C 4 . They have matching control values.   E. The default evaluators is applied to the arguments yielding, lf(conj, [jumped, skipped]), known as R.   F. Elements C 2  to C 4  are replaced by R at position D 2 . The control of R is obtained from the verbs combined as indicated by the absorb(before).       
 
         [0081]    The second iteration of the loop produces the matrix shown in  FIG. 8E . The steps are as follows. 
         [0082]    2. The list O is set to empty. 
         [0083]    3. Find the element in Es with the highest operator priority not in O. This is element D 6 .
       B. Add the element E to the set O. Set O now contains element D 6 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element D 5  and element D 7  do not having matching control.   D. Retry step three.       
 
         [0087]    3. Find the element in Es with the highest operator priority not in O. This is called element D 4 .
       B. Add the element E to the set O.O contains element D 4  and element D 6 .   C. Element D 5  is selected as an argument.   E. The result of applying element D 4  to element D 5  has a control that is the same as element D 5 . This is denoted by the absorb(after) term. The result value is the value of the element E 4 . This is denoted by the select( 1 ) term that selected the Nth Argument. Note that the value can be more sophisticated and contain information about the determiner. For simplification this is not shown.       
 
         [0091]    The third iteration of the loop produces the matrix shown in  FIG. 8F . The steps are as follows. 
         [0092]    2. The list O is set to empty. 
         [0093]    3. Find the element in Es with the highest operator priority not in O. This is element E 5 .
       B. Add the element E to the set O. Set O now contains element E 5 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element E 4  and element E 6  do not having matching control.   D. Retry step three.       
 
         [0097]    3. Find the element in Es with the highest operator priority not in O. This is called element E 9 .
       B. Add the element E to the set O.O contains element E 9  and element E 5 .   C. Element E 10  is selected as an argument.       
 
         [0100]    E. The result of applying element E 9  to element E 10  has a control that is the same as element E 10 . This is denoted by the absorb(after) term. The value is the value of the element E 10 . This is denoted by the select( 1 ) term that selected the Nth Argument. Note that the value can be more sophisticated and contain information about the determiner. For simplification this is not shown. The result value is at position F 9 . 
         [0101]    The forth iteration of the loop produces the matrix shown in  FIG. 8G . The steps are as follows. 
         [0102]    2. The list O is set to empty. 
         [0103]    3. Find the element in Es with the highest operator priority not in O. This is element F 5 .
       B. Add the element E to the set O. Set O now contains element F 5 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element F 4  and element F 6  do not having matching control.   D. Retry step three.       
 
         [0107]    3. Find the element in Es with the highest operator priority not in O. This is called element F 3 .
       B. Add the element E to the set O.O contains element F 3  and element F 5 .   C. Element F 4  is selected as an argument.   E. The result of applying element F 3  to element F 4  has a control the remaining control elements from element F 3 . The value is the a new linguistic frame at position G 3 . These are specified by the evaluator.       
 
         [0111]    The fifth iteration of the loop produces the matrix shown in  FIG. 8H . The steps are as follows. 
         [0112]    2. The list O is set to empty. 
         [0113]    3. Find the element in Es with the highest operator priority not in O. This is element G 4 .
       B. Add the element E to the set O. Set O now contains element G 4 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element G 3  and element G 5  do not having matching control.   D. Retry step three.       
 
         [0117]    3. Find the element in Es with the highest operator priority not in O. This is called element G 7 .
       B. Add the element E to the set O.O contains element G 4  and element G 7 .   C. Element G 8  is selected as an argument.   E. The result of applying element G 7  to element G 8  has a control the remaining control elements from element G 7 . The value is the a new linguistic frame at position H 7 . These are specified by the evaluator.       
 
         [0121]    The sixth iteration of the loop produces the matrix shown in  FIG. 81 . The steps are as follows. 
         [0122]    2. The list O is set to empty. 
         [0123]    3. Find the element in Es with the highest operator priority not in O. This is element H 4 .
       B. Add the element E to the set O. Set O now contains element H 4 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element H 3  and element H 5  do not having matching control.   D. Retry step three.       
 
         [0127]    3. Find the element in Es with the highest operator priority not in O. This is called element H 2 .
       B. Add the element E to the set O.O contains element H 2  and element H 4 .   C. Element H 3  is selected as an argument.   E. The result of applying element H 2  to element H 3  has a control the remaining control elements from element H 2 . The value is the a new linguistic frame at positon I 2 . These are specified by the evaluator. Notice that element H 3  could have been applied as an operator to a preceding noun phrase but in the context the verb phrase used it first.       
 
         [0131]    The eighth iteration of the loop produces the matrix shown in  FIG. 8J . The steps are as follows. 
         [0132]    2. The list O is set to empty. 
         [0133]    3. Find the element in Es with the highest operator priority not in O. This is element I 3 .
       B. Add the element E to the set O. Set O now contains element I 3 .   C. Use the selection expression to select the elements from the matrix. The selection fails since element I 2  and element I 4  do not having matching control.   D. Retry step three.       
 
         [0137]    3. Find the element in Es with the highest operator priority not in O. This is called element I 4 .
       B. Add the element E to the set O.O contains element I 3  and element I 4 .   C. Element I 5  and I 6  are selected as an argument.   E. The result of applying element I 4  to element I 5  and I 6  has a control the remaining control elements from element I 4 . The value is the a new linguistic frame at position J 4 . These are specified by the evaluator.       
 
         [0141]    The ninth iteration of the loop produces the matrix shown in  FIG. 8K . The steps are as follows. 
         [0142]    2. The list O is set to empty. 
         [0143]    3. Find the element in Es with the highest operator priority not in O. This is called element J 3 .
       B. Add the element E to the set O.O contains element J 3 .   C. Element J 2  and J 4  are selected as an argument since the controls match. An enhancement would be to define a manner of combining or intersecting control when perfect matches are not possible.   E. The result of applying element J 3  to element J 2  and J 4  has a control the remaining control elements that are common to elements J 2  and J 4 . The value is the a new linguistic frame at position K 2 . These are specified by the evaluator.       
 
         [0147]    The tenth iteration of the loop produces the matrix shown in  FIG. 8L . The steps are as follows. 
         [0148]    2. The list O is set to empty. 
         [0149]    3. Find the element in Es with the highest operator priority not in O. This is called element K 2 .
       B. Add the element E to the set O.O contains element K 2 .   C. Element K 1  is selected as an argument   E. The result of applying element K 2  to element K 1  has a control the remaining control elements from element K 2 . The value is the a new linguistic frame at position L 1 . In this case, the subject term is added to the cases already present in the linguistic frame. These are specified by the evaluator.       
 
         [0153]    Further processing is not shown. The fact frame evaluator can be used to map the linguistic structures into data structures that allow for further processing that could for example perform an action or record a fact. 
       Tokenization Example 
       [0154]    What follows is an example of using the enhanced operator precedence parser to tokenize an input. The parser can be used to tokenize as well as to perform higher level analysis as in the previous example at the same time. The lexicon for the tokenization example is shown in  FIG. 9A . 
         [0155]    For the following input, step one is applied where each character is a token 
         [0156]    “Jane jumped” 
         [0157]    After applying Step 1 of the method the matrix of elements looks like the table shown in  FIG. 9B . 
         [0158]    For the first pass the highest priority operator is element B 5 . The selector select elements B 1  to B 4 . The default evaluate uses wrap to group the arguments in a list as the new value. The control for the new value is to replace. The result of the first iteration is shown in  FIG. 9C . 
         [0159]    The processing then continues with a lookup in the dictionary. These definitions can be combined with previous example to produce a system that can process input from a bare utterance. What comprises tokenization and parsing in typical models is integrated into a single model. 
       Definitions for Common English Categories 
       [0160]      FIG. 10  shows a table that contains definitions for common categories of English words. This can be extended to types of words present in other languages as well. 
       Enhancements 
       [0161]    A working version of the algorithm would include a more sophisticated control structure. The control structure would allow for alternative using a backtracking algorithm similar to Prolog. To simplify the presentation this is not shown. As well, the algorithms for backtracking are well known and easily applied. 
         [0162]    For each element, properties could be maintained to further characterize the element. These properties could be used in the selection process as well as to maintain semantics. When using the enhanced operator precedence model for analysis, structures from languages other than English are represented with interoperable definitions. This allows utterances that contains mixed languages to be seamlessly processed. Other layers of definitions could be added to support converting sounds into elements that are then tokenized and further processed. This would provide a seamless model for processing speech into action.