Ellipsis and movable constituent handling via synthetic token insertion
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.
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.