PROJECTING SYNTACTIC INFORMATION USING A BOTTOM-UP PATTERN MATCHING ALGORITHM

• US 20090326925A1
• Filed: 12/15/2008
• Published: 12/31/2009
• Est. Priority Date: 06/27/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Baisley, Donald E., Crider, Anthony L.
• Application Number:
  US12/335,206
• Publication Number:
  US 20090326925A1
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Embodiments for converting a token collection that is derived from a natural language expression into a computational independent model (CIM) syntax tree representation are disclosed. In accordance with one embodiment, the conversion includes deriving a plurality of tokens from a natural language expression, where each of the plurality of tokens including at least one word. The conversion further includes transforming the plurality of tokens into a CIM syntax tree representation based on a CIM phrase tree model. The conversion also includes providing the CIM syntax tree representation to an application.

Claims

1. A computer readable medium storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

deriving a plurality of tokens from a natural language expression, each of the plurality of tokens including at least one word;

transforming the plurality of tokens into a computational independent model (CIM) syntax tree representation based on a CIM phrase tree model; and

presenting the CIM syntax tree representation.

2. The computer readable medium of claim 1, wherein the transforming includes:

segregating the plurality of tokens into subclauses based on the CIM phrase tree model;

projecting one or more base nominal expressions in each subclause based on the CIM phrase tree model;

projecting one or more base predicate expressions in each subclause based on the CIM phrase tree model;

projecting one or more base value expressions in each subclause based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model;

assembling the one or more base nominal expressions, the one or more base predicate expressions, the one or more base value expressions into one or more complex clauses based on the CIM phrase tree model; and

assembling a rule by projecting a correct type of intention for the one or more complex clauses based on the CIM phrase tree model, the rule including the CIM syntax tree representation.

3. The computer readable medium of claim 1, wherein the transforming includes parsing at least one of one or more conditional subclauses or one or more sentential expressions based on the CIM phrase tree model.

4. The computer readable medium of claim 1, wherein the transforming includes parsing one of a conditional subclause or a sentential expressions, the parsing comprising:

projecting one or more base predicate expressions in each subclause based on the CIM phrase tree model;

projecting one or more base nominal expressions in each subclause based on the CIM phrase tree model;

projecting one or more base value expressions in each subclause based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model; and

assembling the one or more base predicate expressions, the one or more base nominal expressions, the one or more base value expressions into one or more complex clauses based on the CIM phrase tree model.

5. The computer readable medium of claim 1, wherein the transforming includes one of projecting a verbal complex from one or more tokens of the plurality of tokens or projecting a pronominal reference from the one or more tokens based on the CIM tree representation.

6. The computer readable medium of claim 1, wherein the transforming includes processing helper verbs in a predicate complex.

7. The computer readable medium of claim 2, wherein the projecting of the sentential structure includes projecting a functional restrictive structure.

8. The computer readable medium of claim 2, wherein the projecting of the one or more base predicate expressions includes creating one or more predicate expressions from one or more tokens of the plurality of tokens.

9. The computer readable medium of claim 2, wherein the projecting of the one or more base predicate expressions includes creating one or more predicate expressions from one or more tokens of the plurality of tokens by determine whether at least one of the tokens is one of a modal token, an adverb token, a verb token, or a keyword token.

10. The computer readable medium of claim 2, wherein the projecting of the one or more base value expressions includes parsing value expressions from one or more tokens of the plurality of tokens.

11. The computer readable medium of claim 2, wherein the projecting of the one or more base value expressions includes parsing a value expression from one or more tokens of the plurality of tokens, the parsing including:

projecting one or more base value expressions from a value expression token array based on the CIM phrase tree model;

project one or more function restrictions from the value expression token array based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model that facilitates the projection of the functional restrictions;

assembling the one or more base values expression based on the CIM phrase tree model; and

determining a type for each of the one or more value expressions.

12. The computer readable medium of claim 11, wherein the parsing of the value expression from the one or more tokens further includes removing at least one of parentheses or quotes from ends of the value expression token array of the one or more tokens.

13. A method, comprising:

deriving a plurality of tokens from a natural language expression, each of the plurality of tokens including at least one word;

transforming the plurality of tokens into a computational independent model (CIM) syntax tree representation based on a CIM phrase tree model, the transforming including;

projecting one or more base nominal expressions in each subclause based on the CIM phrase tree model;

projecting one or more base predicate expressions in each subclause based on the CIM phrase tree model;

projecting one or more base value expressions in each subclause based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model;

assembling the one or more base nominal expressions, the one or more base predicate expressions, the one or more base value expressions into one or more complex clauses based on the CIM phrase tree model; and

assembling a rule by projecting a correct type of intention for the one or more complex clauses based on the CIM phrase tree model, the rule including the CIM syntax tree representation; and

presenting the CIM syntax tree representation.

14. The method of claim 13, wherein the transforming further includes parsing at least one of one or more conditional subclauses or one or more sentential expressions based on the CIM phrase tree model.

15. The method of claim 13, wherein the transforming further includes parsing one of a conditional subclause or a sentential expressions, the parsing comprising:

projecting one or more base predicate expressions in each subclause based on the CIM phrase tree model;

projecting one or more base nominal expressions in each subclause based on the CIM phrase tree model;

projecting one or more base value expressions in each subclause based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model; and

assembling the one or more base predicate expressions, the one or more base nominal expressions, the one or more base value expressions into one or more complex clauses based on the CIM phrase tree model.

16. The method of claim 13, further comprising constructing the CIM phrase tree model component to enable transformation of the plurality of tokens into a CIM syntax tree representation.

17. The method of claim 13, wherein the projecting of the one or more base predicate expressions includes creating one or more predicate expressions from the one or more tokens of the plurality of tokens.

18. The method of claim 13, wherein the projecting of the one or more base value expressions includes parsing value expressions from the one or more tokens of the plurality of tokens.

19. A system, comprising:

an input component to receive a plurality of tokens, the plurality of tokens being derived from a natural language expression;

a computational independent model (CIM) phrase tree model component to enable transformation of the plurality of tokens into a CIM syntax tree representation;

a CIM tree transformation algorithm component to transform the plurality of tokens into a CIM syntax tree representation based on the CIM phrase tree model; and

an output component to provide to present the CIM syntax tree representation.

20. The system of claim 19, wherein the CIM tree transformation algorithm component is to:

projecting one or more base predicate expressions in each subclause based on the CIM phrase tree model;

projecting one or more base nominal expressions in each subclause based on the CIM phrase tree model;

projecting one or more base value expressions in each subclause based on the CIM phrase tree model;

projecting a sentential structure based on the CIM phrase tree model; and

assembling the one or more base predicate expressions, the one or more base nominal expressions, the one or more base value expressions into one or more complex clauses based on the CIM phrase tree model.