Dynamic tokens for an expression parser

Patent metadata

Field	Value
Publication number	US-9836451-B2
Application number	US-201615091191-A
Country	US
Kind code	B2
Filing date	Apr 5, 2016
Priority date	Feb 18, 2016
Publication date	Dec 5, 2017
Grant date	Dec 5, 2017

Abstract

The disclosure generally describes computer-implemented methods, software, and systems for enabling dynamic tokens in an expression parser. An example method includes identifying an expression represented as a natural language input for validation by a parser. Each of the phrases in the expression are iteratively converted into a set of tokens by determining whether a current phrase matches a pre-defined token associated with a known grammar rule, and, in response to determining that the current phrase matches a pre-defined token, generating a token for the current phrase for use in validating the expression. If the current phrase does not match a pre-defined token, the unrecognized string of characters is compared to a plurality of dynamic tokens included in an external pool of tokens to generate a generic token of an identified type. The dynamic token is replaced with the generic token and can be used to validate the expression.

First claim

What is claimed is:

1. A computer-implemented method performed by at least one processor, the method comprising:
identifying an expression for validation by a parser, the expression represented as a natural language input including a set of phrases;
iteratively converting each of the phrases of the natural language input into a set of tokens, wherein converting each phrase includes:
determining whether a current phrase matches a pre-defined token of a plurality of pre-defined tokens associated with a known grammar rule;
in response to determining that the current phrase matches a pre-defined token associated with a known grammar rule, generating a token for the current phrase for use in validating the expression;
in response to determining that the current phrase does not match a pre-defined token associated with a known grammar rule, the current phrase comprising an unrecognized string of characters:
comparing the unrecognized string of characters to a plurality of dynamic tokens included in an external pool of tokens, the plurality of dynamic tokens included in the external pool of tokens different than the plurality of pre-defined tokens associated with the known grammar rule;
identifying a dynamic token from the external pool of tokens corresponding to the unrecognized string of characters;
identifying a type of the identified dynamic token, wherein the identified type is one of a string, a number, or a date; and
generating a generic token for the current phrase based on the identified type of the identified dynamic token, wherein the generic token is a character string corresponding to the identified type of the identified dynamic token; and
replacing the identified dynamic token with the generic token for use in validating the expression;

generating a tokenized expression by combining the generated tokens; and
validating the tokenized expression.

2. The method of claim 1 , further comprising, after validating the tokenized expression, replacing each generic token in the tokenized expression with the corresponding dynamic token.

3. The method of claim 2 , further comprising executing the tokenized expression.

4. The method of claim 1 , wherein the expression represents a query.

5. The method of claim 1 , wherein each dynamic token is associated with a type.

6. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
identifying an expression for validation by a parser, the expression represented as a natural language input including a set of phrases;
iteratively converting each of the phrases of the natural language input into a set of tokens, wherein converting each phrase includes:
determining whether a current phrase matches a pre-defined token of a plurality of pre-defined tokens associated with a known grammar rule;
in response to determining that the current phrase matches a pre-defined token associated with a known grammar rule, generating a token for the current phrase for use in validating the expression;
in response to determining that the current phrase does not match a pre-defined token associated with a known grammar rule, the current phrase comprising an unrecognized string of characters:
comparing the unrecognized string of characters to a plurality of dynamic tokens included in an external pool of tokens, the plurality of dynamic tokens included in the external pool of tokens different than the plurality of pre-defined tokens associated with the known grammar rule;
identifying a dynamic token from the external pool of tokens corresponding to the unrecognized string of characters;
identifying a type of the identified dynamic token, wherein the identified type is one of a string, a number, or a date; and
generating a generic token for the current phrase based on the identified type of the identified dynamic token, wherein the generic token is a character string corresponding to the identified type of the identified dynamic token; and
replacing the identified dynamic token with the generic token for use in validating the expression;

generating a tokenized expression by combining the generated tokens; and
validating the tokenized expression.

7. The non-transitory, computer readable medium of claim 6 , the operations further comprising, after validating the tokenized expression, replacing each generic token in the tokenized expression with the corresponding dynamic token.

8. The non-transitory, computer readable medium of claim 7 , further comprising executing the tokenized expression.

9. The non-transitory, computer readable medium of claim 6 , wherein the expression represents a query.

10. The non-transitory, computer readable medium of claim 6 , wherein each dynamic token is associated with a type.

11. A computer system, comprising:
a computer memory; and
a hardware processor interoperably coupled with the computer memory and configured to perform operations comprising:
identifying an expression for validation by a parser, the expression represented as a natural language input including a set of phrases;
iteratively converting each of the phrases of the natural language input into a set of tokens, wherein converting each phrase includes:
determining whether a current phrase matches a pre-defined token of a plurality of pre-defined tokens associated with a known grammar rule;
in response to determining that the current phrase matches a pre-defined token associated with a known grammar rule, generating a token for the current phrase for use in validating the expression;
in response to determining that the current phrase does not match a pre-defined token associated with a known grammar rule, the current phrase comprising an unrecognized string of characters:
comparing the unrecognized string of characters to a plurality of dynamic tokens included in an external pool of tokens, the plurality of dynamic tokens included in the external pool of tokens different than the plurality of pre-defined tokens associated with the known grammar rule;
identifying a dynamic token from the external pool of tokens corresponding to the unrecognized string of characters;
identifying a type of the identified dynamic token, wherein the identified type is one of a string, a number, or a date; and
generating a generic token for the current phrase based on the identified type of the identified dynamic token, wherein the generic token is a character string corresponding to the identified type of the identified dynamic token; and
replacing the identified dynamic token with the generic token for use in validating the expression;

generating a tokenized expression by combining the generated tokens; and
validating the tokenized expression.

12. The system of claim 11 , the operations further comprising, after validating the tokenized expression, replacing each generic token in the tokenized expression with the corresponding dynamic token.

13. The system of claim 12 , further comprising executing the tokenized expression.

14. The system of claim 11 , wherein the expression represents a query.

15. The system of claim 11 , wherein each dynamic token is associated with a type.

Assignees

• Sap Se

Inventors

• Halbani Ronen
• Barel Liad
• Tarshish Shahar

Classifications

• G06F40/284 Primary

  Lexical analysis, e.g. tokenisation or collocates · CPC title

• G06F40/226 Primary

  Validation · CPC title

• G06F17/2725

  Physics · mapped topic

• G06F17/277 Primary

  Physics · mapped topic