Ellipsis and movable constituent handling via synthetic token insertion

• US 20110112823A1
• Filed: 11/06/2009
• Published: 05/12/2011
• Est. Priority Date: 11/06/2009
• Status: Abandoned Application

• Current Assignee: Clausal Computing Oy (Tatu Juhani Ylönen)
• Original Assignee: TATU Ylonen OY Limited
• Inventors: Ylonen, Tatu J.
• Application Number:
  US12/613,874
• Publication Number:
  US 20110112823A1
• 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

Abstract

Movable and elliptic constituents are handled in a parser by inserting synthetic tokens that do not occur in the input. Parser actions can push a syntax tree or semantic value to be realized later as a synthetic token, and some synthetic tokens (for cataphoric ellipsis) may be inserted without a prior push but require a later definition. At clause boundary it may be checked that all mandatory tokens have been inserted.

Claims

1. A system comprising:

a left-to-right parser executor for natural language;

a synthetic token insertion means configured to insert a synthetic token to be processed by the left-to-right parser executor; and

a synthetic define means coupled to the synthetic token insertion means and responsive to parser actions triggered by the left-to-right parser executor.

2. The system of claim 1, further comprising:

a synthetic item set associated with a parse context;

wherein the coupling is via at least one synthetic item set.

3. The system of claim 1, further comprising:

a clause boundary means configured to reject a parse in response to a synthetic token that must be inserted in the current not having been inserted before the end of the clause in which it should have been inserted.

4. The system of claim 1, wherein the system is a computer.

5. The system of claim 4, comprising at least one synthetic define means selected from the group consisting of movable push means, anaphoric push means, and cataphoric define means.

6. The system of claim 4, further comprising:

a clause boundary means responsive to parser actions performed by the parser executor.

7. The system of claim 4, further comprising:

a clause nesting means responsive to parser actions performed by the parser executor.

8. The system of claim 4, wherein at least one synthetic define means makes available for insertion in a parse context a synthetic token corresponding to a constituent in an earlier question in the dialog context associated with the parse context.

9. The system of claim 4, wherein the left-to-right parser executor implements a generalized LR parser.

10. The system of claim 9, wherein the generalized LR parser is a non-deterministic LALR(1) parser.

11. The system of claim 9, further comprising:

a clause boundary means responsive to parser actions performed by the parser executor.

12. The system of claim 9, further comprising:

a clause nesting means responsive to parser actions performed by the parser executor.

13. The system of claim 9, further comprising:

a sentence boundary means responsive to parser actions performed by the parser executor.

14. The system of claim 9, wherein at least one synthetic define means makes available for insertion in a parse context a synthetic token corresponding to a constituent in an earlier question in the dialog context associated with the parse context.

15. A method of parsing natural language using a left-to-right parser executor in a computer, comprising:

adding, by a parser action performed by the parser executor after parsing a non-synthetic constituent, an item specifying a synthetic token and a value from the non-synthetic constituent into a synthetic item set; and

inserting, by the parser executor, a synthetic token specified by an item in the synthetic item set to be processed by the parser executor.

16. The method of claim 15, wherein a clause boundary means is used to make the added synthetic token available for insertion.

17. The method of claim 15, further comprising:

rejecting, by an action associated with a clause boundary, at least one parse.

18. The method of claim 15, further comprising:

upon entering a relative clause, saving at least some items in the synthetic token set; and

upon leaving a relative clause, restoring at least some items into the synthetic token set.

19. The method of claim 15, further comprising:

adding at least one item specifying a synthetic token and a value for it into the synthetic item set based on at least one constituent of a question stored in a dialog context associated with the parse context associated with the synthetic item set.

20. The method of claim 15, wherein the left-to-right parser executor implements a generalized LR parser.

21. The method of claim 20, wherein the synthetic token in at least one added item is made fully available for insertion by a parser action associated with a clause boundary.

22. The method of claim 20, further comprising:

rejecting, by an action associated with a clause boundary, at least one parse context whose synthetic item set comprises an item that should have been inserted in the preceding clause but was not.

23. The method of claim 20, further comprising:

upon entering a relative clause, saving at least some items in the synthetic item set; and

upon leaving a relative clause, restoring at least some items into the synthetic item set.

24. The method of claim 20, further comprising:

inserting in an embedded clause at least one synthetic token defined in an outer clause.

25. The method of claim 20, further comprising:

inserting at least one synthetic token based on at least one constituent of a question stored in a dialog context.

26. A method of parsing natural language using a left-to-right parser executor in a computer, comprising:

inserting, by the parser executor, a synthetic token to be processed by the parser executor; and

defining, by a parser action performed by the parser executor after parsing a non-synthetic constituent, a value associated with the inserted synthetic token based on the non-synthetic constituent.

27. The method of claim 26, wherein the left-to-right parser executor implements a generalized LR parser.

28. The method of claim 27, further comprising:

rejecting at least one parse context for which for an inserted synthetic token the value has not been defined, in response to an action associated with a sentence boundary.

29. A computer program product stored on a computer readable medium, operable to cause a computer to perform left-to-right parsing of natural language, the product comprising:

a computer readable program code means for causing a computer to add an item specifying a synthetic token and a value for it into a synthetic item set; and

a computer readable program code means for causing a computer to insert a synthetic token specified by an item in the synthetic item set to be processed by the computer as part of the left-to-right parsing.

30. The computer program product of claim 29, further comprising a computer readable program code means for causing a computer to perform generalized LR parsing.

31. The computer program product of claim 30, further comprising:

a computer readable program code means for causing a computer to reject a parse context in response to a movable constituent not having been inserted by the time the end of the clause in which it must be inserted is encountered.

32. A computer program product stored on a computer readable medium, operable to cause a computer to perform left-to-right parsing of natural language, the product comprising:

a computer readable program code means for causing a computer to insert a synthetic token to be processed by the computer as part of the left-to-right parsing; and

a computer readable program code means for causing a computer to define the value associated with the inserted token after parsing a non-synthetic constituent based on the value of the non-synthetic constituent.

33. The computer program product of claim 32, further comprising a computer readable program code means for causing a computer to perform generalized LR parsing.

34. The computer program product of claim 33, further comprising:

a computer readable program code means for causing a computer to reject at least parse context in response to a parser action associated with a sentence boundary.