Dynamic scanner

• US 20030035582A1
• Filed: 08/14/2001
• Published: 02/20/2003
• Est. Priority Date: 08/14/2001
• Status: Abandoned Application

• Current Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Original Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Inventors: Linhart, Christian
• Application Number:
  US09/929,448
• Publication Number:
  US 20030035582A1
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 8/425 Lexical analysis

Abstract

A method for generating a scanner includes receiving a definition of a plurality of patterns and receiving a definition of a respective association between each of the plurality of patterns and a respective executable action. The plurality of patterns and the respective associations are processed so as to form a scanner data structure capable of comparing input data to at least one of the patterns and causing execution of the associated executable action upon a match of the input data with the respective one of the plurality of patterns. The processing and the comparing are performed in the same active process.

Claims

1. A method for generating a scanner, the method comprising:

receiving a definition of a plurality of patterns;

receiving a definition of a respective association between each of the plurality of patterns and a respective executable action; and

processing the plurality of patterns and the respective associations to form a scanner data structure capable of comparing input data to at least one of the plurality of patterns and causing execution of the associated executable action upon a match of the input data with the respective one of the plurality of patterns, the processing and the comparing being performed in a same active process.

2. The method as recited in claim 1 wherein the scanner is capable of being used for at least one of a compiler front end, a syntax-highlighting editor, a text stream editor, a parser and a parser-filter.

3. The method as recited in claim 1 wherein the receiving the definition of the plurality of patterns is performed in the same active process.

4. The method as recited in claim 1 wherein the plurality of patterns include regular expressions.

5. The method as recited in claim 1 wherein the plurality of patterns include text patterns.

6. The method as recited in claim 1 wherein the receiving the definition of the respective association is performed in the same active process.

7. The method as recited in claim 1 wherein each respective association between each of the plurality of patterns and the respective executable action includes a pointer.

8. The method as recited in claim 1 wherein each respective association between each of the plurality of patterns and the respective executable action includes an index number.

9. The method as recited in claim 1 wherein at least one of the respective executable action includes a respective action object.

10. The method as recited in claim 1 wherein at least a portion of at least one of the respective executable action is generated in the same active process.

11. The method as recited in claim 1 wherein at least one of the respective executable action includes respective program code.

12. The method as recited in claim 1 wherein at least one of the respective executable action includes respective data.

13. The method as recited in claim 1 wherein the processing includes forming a scanner definition string from the plurality of patterns and respective associations.

14. The method as recited in claim 13 wherein each respective association is represented in the scanner definition string by a respective indicator.

15. The method as recited in claim 14 wherein the processing further includes saving a mapping between each respective indicator and a respective action-pointer.

16. The method as recited in claim 14 wherein each respective indicator includes a respective index.

17. The method as recited in claim 14 wherein each respective indicator includes a respective a number representing a respective pointer.

18. The method as recited in claim 13 wherein the scanner definition string has a format of a scanner definition file of a scanner generator.

19. The method as recited in claim 18 wherein the scanner generator is a Flex scanner generator.

20. The method as recited in claim 18 wherein the processing further includes inputting the scanner definition string into a scanner generator core modified for processing the scanner definition string so as to form a processed scanner definition data structure.

21. The method as recited in claim 20 wherein the scanner generator core is a Flex scanner generator core.

22. The method as recited in claim 20 wherein the processing further includes converting the processed scanner definition data structure into the scanner data structure.

23. The method as recited in claim 1 wherein the scanner data structure includes a respective indicator representing the respective association between each of the plurality of patterns and the respective executable action.

24. The method as recited in claim 23 wherein each respective indicator includes an index.

25. The method as recited in claim 23 wherein each respective indicator includes a pointer.

26. The method as recited in claim 13 wherein the processing further includes saving the scanner definition string and the scanner data structure.

27. The method as recited in claim 26 wherein the saving is performed to a persistent memory device.

28. The method as recited in claim 26 wherein the processing further includes saving a mapping between the scanner definition string and the scanner data structure.

29. The method as recited in claim 28 wherein the saving is performed to a persistent memory device.

30. The method as recited in claim 28 further comprising:

receiving a definition of a plurality of second patterns;

receiving a definition of a respective second association between each of the plurality of second patterns and a respective second executable action;

processing the plurality of second patterns and the respective second associations so as to determine a second scanner data structure capable of comparing the input data to each of the plurality of second patterns and causing execution of the respective second executable action upon a match of the input data with a one of the plurality of second patterns, the processing each of the plurality of second patterns and the respective second association and the comparing the input data to each of the plurality of second patterns being performed in a same second active process;

wherein the processing each of the plurality of second patterns and the respective second association includes;

forming a second scanner definition string from the plurality of second patterns and respective second associations; and

comparing the second scanner definition string to the saved scanner definition string and loading the saved scanner data structure as the second scanner data structure when the second scanner definition string matches the saved scanner definition string.

31. The method as recited in claim 30 wherein the saved scanner definition string and the second scanner definition string have a format of a scanner definition file of a scanner generator.

32. The method as recited in claim 31 wherein the scanner generator is a Flex scanner generator.

33. The method as recited in claim 30 wherein the loading the saved scanner data structure as the second scanner data structure is performed using the mapping between the scanner definition string and the scanner data structure.

34. The method as recited in claim 30 further comprising inputting the second scanner definition string into a scanner generator core so as to form a processed scanner definition data structure when the second scanner definition string does not match the saved scanner definition string.

35. The method as recited in claim 34 wherein the scanner generator core is a Flex scanner generator core.

36. The method as recited in claim 34 wherein the processing further includes converting the processed scanner definition data structure into the second scanner data structure.

37. The method as recited in claim 30 wherein the processing further includes saving the second scanner definition string and the second scanner data structure.

38. The method as recited in claim 37 wherein the processing further includes saving a mapping between the second scanner definition string and the second scanner data structure.

39. The method as recited in claim 1 further comprising:

associating at least one respective start state of a plurality of start states with each of the plurality of patterns; and

setting a current start state, the current start state being one of the plurality of start states;

wherein the processing includes processing the at least one respective start state along with each associated pattern so as to form a part of the scanner data structure, the comparing being performed so as to compare only the patterns of the plurality of patterns associated with a respective start state equal to the current start state.

40. The method as recited in claim 39 wherein the setting the current start state is performed so as to reset the current start state to another one of the plurality of start states at least once during the comparing.

41. The method as recited in claim 40 wherein the current start state is reset using at least one of the respective executable action.

42. The method as recited in claim 40 further comprising maintaining a stack of the plurality of start states, the current start state being the top of the stack.

43. The method as recited in claim 39 further comprising associating a respective context with each of the plurality of start states for controlling the respective start state.

44. The method as recited in claim 43 wherein each context includes at least one respective rule defining a start and an end of the context.

45. The method as recited in claim 39 further comprising maintaining a stack of the plurality of start states, the current start state being the top of the stack, each of the context for controlling a position of the respective start state in the stack.

46. The method as recited in claim 1 wherein the input data includes a data stream.

47. A method for scanning input data, the method comprising:

receiving a definition of a plurality of patterns;

receiving a definition of a respective association between each of the plurality of patterns and a respective executable action;

processing the plurality of patterns and the respective associations so as form a scanner data structure;

comparing the input data to the a plurality of patterns using the scanner data structure; and

when the comparing results in a matched one of the a plurality of patterns, executing the respective executable action associated with the matched pattern;

wherein the processing and the comparing are performed in a same active process.

48. The method as recited in claim 47 wherein the scanning is performed in at least one of a compiler front end, a syntax-highlighting editor, a text stream editor, a parser and a parser-filter.

49. The method as recited in claim 47 further comprising receiving the definition of the plurality of patterns in the same active process.

50. The method as recited in claim 47 wherein the receiving a definition of the respective association between each of the plurality of patterns and the respective executable action is performed in the same active process.

51. The method as recited in claim 47 wherein at least one of the respective executable action includes a respective action object.

52. The method as recited in claim 47 wherein at least a portion of at least one of the respective executable action is generated in the same active process.

53. The method as recited in claim 47 wherein the processing includes forming a scanner definition string from the plurality of patterns and respective associations.

54. The method as recited in claim 47 wherein the processing further includes inputting the scanner definition string into a scanner generator core modified for processing the scanner definition string so as to form a processed scanner definition data structure.

55. The method as recited in claim 54 wherein the processing further includes converting the processed scanner definition data structure into the scanner data structure.

56. The method as recited in claim 53 wherein the processing further includes saving the scanner definition string and the scanner data structure.

57. The method as recited in claim 56 wherein the processing further includes saving a mapping between the scanner definition string and the scanner data structure.

58. The method as recited in claim 57 further comprising:

receiving a definition of a plurality of second patterns;

receiving a definition of a respective second association between each of the plurality of second patterns and a respective second executable action;

processing the plurality of second patterns and the respective second associations so as to determine a second scanner data structure capable of comparing the input data to each of the plurality of second patterns and causing execution of the respective second executable action upon a match of the input data with a one of the plurality of second patterns, the processing each of the plurality of second patterns and the respective second association and the comparing the input data to each of the plurality of second patterns being performed in a same second active process;

wherein the processing each of the plurality of second patterns and the respective second association includes;

forming a second scanner definition string from the plurality of second patterns and respective second associations; and

comparing the second scanner definition string to the saved scanner definition string and loading the saved scanner data structure as the second scanner data structure when the second scanner definition string matches the saved scanner definition string.

59. The method as recited in claim 58 wherein the loading the saved scanner data structure as the second scanner data structure is performed using the mapping between the scanner definition string and the scanner data structure.

60. The method as recited in claim 58 further comprising inputting the second scanner definition string into a scanner generator core so as to form a processed scanner definition data structure when the second scanner definition string does not match the saved scanner definition string.

61. The method as recited in claim 47 further comprising:

associating at least one respective start state of a plurality of start states with each of the plurality of patterns; and

setting a current start state, the current start state being one of the plurality of start states;

wherein the processing includes processing the at least one respective start state along with each associated pattern so as to form a part of the scanner data structure, the comparing being performed so as to compare only the patterns of the plurality of patterns associated with a respective start state equal to the current start state.

62. The method as recited in claim 61 further comprising associating a respective context with each of the plurality of start states for controlling the respective start state.

63. The method as recited in claim 62 wherein each respective context includes at least one rule defining a start and an end of the context.

64. A scanner comprising:

a scanner data structure including processed information for a plurality of patterns and respective indicators for associating a respective executable action with each of the a plurality of patterns, the scanner data structure being capable of being used to compare input data to the plurality of patterns and cause execution of the respective executable action upon a match of the input data with a one of the a plurality of patterns, the scanner data structure being formed and the comparing being performed in a same active process.

65. The scanner as recited in claim 64 wherein the scanner is capable of being used for at least one of a compiler front end, a syntax-highlighting editor, a text stream editor, a parser and a parser-filter.

66. The scanner as recited in claim 64 wherein a definition of the plurality of patterns is received in the same active process.

67. The scanner as recited in claim 64 wherein a definition of each of the respective indicator is received in the same active process.

68. The scanner as recited in claim 64 wherein at least one of the respective executable action includes a respective action object.

69. The scanner as recited in claim 64 wherein at least a portion of at least one of the respective executable action is generated in the same active process.

70. The scanner as recited in claim 64 wherein the scanner definition data structure is formed by a process including forming a scanner definition string from the plurality of patterns and respective associations.

71. The scanner as recited in claim 70 wherein the process further includes inputting the scanner definition string into a scanner generator core modified for processing the scanner definition string.

72. A computer readable medium having stored thereon computer executable process steps operative to perform a method for generating a scanner, the method comprising:

defining a plurality of patterns;

defining a respective association between each of the plurality of patterns and a respective executable action; and

processing the plurality of patterns and the respective associations so as to form a scanner data structure capable of comparing input data to each of the plurality of patterns and causing execution of the respective executable action upon a match of the input data with a one of the plurality of patterns, the processing and the comparing being performed in a same active process.

73. The computer readable medium as recited in claim 72 wherein the scanner is capable of being used for at least one of a compiler front end, a syntax-highlighting editor, a text stream editor, a parser and a parser-filter.

74. The computer readable medium as recited in claim 72 wherein the method further comprises defining the plurality of patterns in the same active process.

75. The computer readable medium as recited in claim 72 wherein the defining the respective association between each of the plurality of patterns and the respective executable action is performed in the same active process.

76. The computer readable medium as recited in claim 72 wherein at least one of the respective executable action includes a respective action object.

77. The computer readable medium as recited in claim 72 wherein at least a portion of at least one of the respective executable action is generated in the same active process.

78. The computer readable medium as recited in claim 72 wherein the processing includes forming a scanner definition string from the plurality of patterns and respective associations.

79. The computer readable medium as recited in claim 72 wherein the processing further includes inputting the scanner definition string into a scanner generator core modified for processing the scanner definition string so as to form a processed scanner definition data structure.

80. The computer readable medium as recited in claim 79 wherein the processing further includes converting the processed scanner definition data structure into the scanner data structure.

81. The computer readable medium as recited in claim 78 wherein the processing further includes saving the scanner definition string and the scanner data structure.

82. The computer readable medium as recited in claim 81 wherein the processing further includes saving a mapping between the scanner definition string and the scanner data structure.

83. The computer readable medium as recited in claim 82 further comprising:

defining a plurality of second patterns;

defining a respective second association between each of the plurality of second patterns and a respective second executable action;

processing the plurality of second patterns and the respective second associations so as to determine a second scanner data structure capable of comparing the input data to each of the plurality of second patterns and causing execution of the respective second executable action upon a match of the input data with a one of the plurality of second patterns, the processing each of the plurality of second patterns and the respective second association and the comparing the input data to each of the plurality of second patterns being performed in a same second active process;

wherein the processing each of the plurality of second patterns and the respective second association includes;

forming a second scanner definition string from the plurality of second patterns and respective second associations; and

comparing the second scanner definition string to the saved scanner definition string and loading the saved scanner data structure as the second scanner data structure when the second scanner definition string matches the saved scanner definition string.

84. The computer readable medium as recited in claim 83 wherein the loading the saved scanner data structure as the second scanner data structure is performed using the mapping between the scanner definition string and the scanner data structure.

85. The computer readable medium as recited in claim 83 further comprising inputting the second scanner definition string into a scanner generator core so as to form a processed scanner definition data structure when the second scanner definition string does not match the saved scanner definition string.

86. The computer readable medium as recited in claim 72 further comprising:

associating at least one respective start state of a plurality of start states with each of the plurality of patterns; and

setting a current start state, the current start state being one of the plurality of start states;

wherein the processing includes processing the at least one respective start state along with each associated pattern so as to form a part of the scanner data structure, the comparing being performed so as to compare only the patterns of the plurality of patterns associated with a respective start state equal to the current start state.

87. The computer readable medium as recited in claim 86 further comprising associating a respective context with each of the plurality of start states for controlling the respective start state.

88. The computer readable medium as recited in claim 87 wherein each respective context includes at least one rule defining a start and an end of the context.