Left-corner chart parsing

• US 20060036429A1
• Filed: 10/04/2005
• Published: 02/16/2006
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Robert C.
• Granted Patent: US 7,236,925 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Different embodiments of the present invention provide improvements to left-corner chart parsing. The improvements include a specific order of filtering checks, transforming the grammar using bottom-up prefix merging, indexing productions first based on input symbols, grammar flattening, and annotating chart edges for the extraction of parses.

Claims

1. (canceled)

2. (canceled)

3. (canceled)

4. (canceled)

5. (canceled)

6. (canceled)

7. (canceled)

8. (canceled)

9. (canceled)

10. (canceled)

11. (canceled)

12. (canceled)

13. (canceled)

14. (canceled)

15. (canceled)

16. (canceled)

17. (canceled)

18. A method of indexing productions for use in a left-corner chart parser which parses input text containing input symbols, the method comprising:

indexing the productions first based on input symbols which are consistent with the productions.

19. The method of claim 18 wherein indexing comprises:

precomputing which of the productions are consistent with which of the input symbols.

20. The method of claim 19 wherein precomputing comprises:

precomputing, for each possible input symbol, which productions have a second daughter with that input symbol as a left corner.

22. The method of claim 18 and further comprising:

indexing the productions next based on a left-most daughter of the productions.

23. The method of claim 22 and further comprising:

indexing the productions next based on a mother of the productions.

24. The method of claim 23 and further comprising:

enumerating the productions based on remainder of the productions, other than the left-most daughter and the mother.

21. (canceled)

25. A method of parsing input text using a left-corner chart parsing process, comprising:

receiving an input symbol in the input text;

accessing an input symbol index to obtain productions having the input symbol as a left corner of the second daughter; and

after obtaining the productions having the input symbol as a left corner of the second daughter, accessing other indices to the productions.

27. The method of claim 25 wherein accessing other indices comprises:

accessing a left-most daughter index to obtain productions based on their left-most daughter.

28. The method of claim 27 wherein accessing other indices comprises:

accessing a mother index to obtain productions based on their mother.

29. The method of claim 28 and further comprising:

accessing a list containing a completion of productions that are obtained by accessing the left-most daughter index and the mother index.

26. (canceled)

30. A computer-readable data structure indexing productions used in a left-corner chart parser which parses input text, the data structure comprising:

a first index portion indexing the productions first based on input symbols which are consistent with the productions; and

a function which, when executed by the computer, traces the indexed productions to parse the input text.

31. The data structure of claim 30 wherein the first index portion indexes productions by input symbol based on which productions have the input symbol as a left corner of the second daughter.

32. The data structure of claim 31 and further comprising:

a second index portion indexing the productions based on a left-most daughter of the productions.

33. The data structure of claim 32 and further comprising:

a third index portion indexing the productions based on a mother of the productions.

34. The data structure of claim 33 and further comprising:

a fourth portion enumerating the productions based on a remainder of the productions, other than the left-most daughter and the mother of the productions.

35. (canceled)

36. (canceled)

37. (canceled)

38. (canceled)

39. (canceled)

40. (canceled)

41. (canceled)

42. (canceled)

43. (canceled)

44. (canceled)

45. (canceled)

46. (canceled)

47. (canceled)

48. (canceled)

49. (canceled)

50. (canceled)

51. (canceled)

52. (canceled)

53. (canceled)

54. (canceled)

55. (canceled)

56. (canceled)

57. (canceled)

58. (canceled)

59. (canceled)

60. (canceled)

61. (canceled)

62. (canceled)

63. (canceled)

64. (canceled)

65. (canceled)

66. (canceled)

67. (canceled)

68. (canceled)

69. (canceled)

70. (canceled)

71. (canceled)

72. (canceled)

73. (canceled)

74. (canceled)

75. (canceled)

76. (canceled)

77. (canceled)

78. (canceled)

79. (canceled)

80. (canceled)