US5812853A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for parsing source code using prefix analysis
Assignee: Nokia of America Corp
•
Filing: 1994-04-11
•
Granted: 1998-09-22
•
Expires: 2014-04-11
Abstract
Abstract A method and apparatus for processing source code in a language processing system with improved parsing based on prefix analysis. A method in accordance with the present invention includes the steps of identifying a previously-parsed prefix of a source code translation unit; creating a parser in a parser state corresponding to the identified prefix; and parsing a remaining portion of the translation unit after the prefix using the parser in the parser state corresponding to the prefix. In one embodiment of the invention, the step of creating a parser includes retrieving stored level-one subtrees corresponding to the top-level statements in the prefix. The level-one subtrees corresponding to the prefix may be stored in the form of a prefix tree along with the text of the top-level source code statements represented by the prefix and a parser delta indicating the effect of the code statements on the parser state.
Inventors
- 👤 Martin D. Carroll
- 👤 Peter Juhl
- 👤 Andrew Richard Koenig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:23
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/42; G06F8/427
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
82 words
A method of parsing source code in a language processing system, said method comprising the steps of: analyzing a translation unit of said source code to identify a previously-parsed prefix of the translation unit; creating a parser in a parser state that said parser would be in after parsing said prefix; and parsing a remainder of said translation unit after said prefix using said parser in said parser state, regardless of whether portions of said remainder are unchanged since a previous parse.
Claim 2
Independent Claim
82 words
A method of parsing source code in a language processing system, said method comprising the steps of: analyzing a translation unit of said source code to identify a previously-parsed prefix of the translation unit; creating a parser in a parser state that said parser would be in after parsing said prefix; and parsing a remainder of said translation unit after said prefix using said parser in said parser state, regardless of whether portions of said remainder are unchanged since a previous parse.
Claim 3
Dependent Claim
19 words
The method of claim 1 furthing including the step of preprocessing said source code to generate said translation unit.
Claim 4
Dependent Claim
18 words
The method of claim 1 further including the step of storing results thereof for use in subsequent parsing.
Claim 5
Dependent Claim
35 words
The method of claim 1 wherein said step of creating said parser in said parser state corresponding to said prefix further includes the step of retrieving a number of level-one subtrees corresponding to said prefix.
Claim 6
Dependent Claim
33 words
The method of claim 1 wherein said step of parsing a remainder of said translation unit after said prefix includes generating a number of level-one subtrees for said remainder of said translation unit.
Claim 7
Dependent Claim
35 words
The method of claim 1 wherein said method further includes the step of combining level-one subtrees corresponding to said prefix of said translation unit with level-one subtrees corresponding to said remainder of said translation unit.
Claim 8
Dependent Claim
37 words
The method of claim 1 wherein said steps of identifying said prefix and creating a parser in a state corresponding to said prefix further includes the step of retrieving a stored prefix tree representing said parser state.
Claim 9
Dependent Claim
21 words
The method of claim 7 wherein said prefix tree includes a number of nodes representing top-level statements in said source code.
Claim 10
Dependent Claim
50 words
The method of claim 8 wherein each node in said prefix tree further includes: text corresponding to a sequence of top-level statements in said source code represented by said node; a level-one subtree corresponding to said sequence of top-level statements; and a parser delta for said sequence of top-level statements.
Claim 11
Dependent Claim
49 words
The method of claim 8 wherein said step of creating said parser in said parser state further includes the steps of: creating a parser in an initial state; and applying a parser delta for each of said nodes in said prefix tree to said parser in said initial state.
Claim 12
Dependent Claim
19 words
The method of claim 8 wherein each node of said prefix tree represents a contiguous sequence of top-level statements.
Claim 13
Dependent Claim
19 words
The method of claim 1 wherein said prefix was parsed in a previous parse of a second translation unit.
Claim 14
Dependent Claim
22 words
The method of claim 1 wherein said prefix was parsed in a previous parse of a different version of said translation unit.
Claim 15
Independent Claim
84 words
An apparatus for processing source code in a language processing system, said apparatus comprising: means for analyzing a translation unit of said source code to identify a previously-parsed prefix of the translation unit; and a parser configured in a parser state that said parser would be in after parsing said prefix, wherein said parser in said parser state is adapted to parse a remainder of said translation unit after said prefix, regardless of whether portions of said remainder are unchanged since a previous parse.
Claim 16
Independent Claim
84 words
An apparatus for processing source code in a language processing system, said apparatus comprising: means for analyzing a translation unit of said source code to identify a previously-parsed prefix of the translation unit; and a parser configured in a parser state that said parser would be in after parsing said prefix, wherein said parser in said parser state is adapted to parse a remainder of said translation unit after said prefix, regardless of whether portions of said remainder are unchanged since a previous parse.
Claim 17
Dependent Claim
22 words
The apparatus of claim 14 further including means for storing results of parsing performed by said parser for use in subsequent parsing.
Claim 18
Dependent Claim
24 words
The apparatus of claim 14 wherein said parser in said parser state is created from a number of level-one subtrees corresponding to said prefix.
Claim 19
Dependent Claim
15 words
The apparatus of claim 14 wherein said parser state is stored as a prefix tree.
Claim 20
Dependent Claim
21 words
The apparatus of claim 17 wherein said prefix tree includes a number of nodes representing top-level statements in said source code.
Claim 21
Dependent Claim
50 words
The apparatus of claim 18 wherein each node in said prefix tree further includes: text corresponding to a sequence of top-level statements in said source code represented by said node; a level-one subtree corresponding to said sequence of top-level statements; and a parser delta for said sequence of top-level statements.
Claim 22
Dependent Claim
19 words
The apparatus of claim 18 wherein each node of said prefix tree represents a contiguous sequence of top-level statements.
Claim 23
Dependent Claim
15 words
The apparatus of claim 14 wherein said source code is in a C programming language.
Claim 24
Dependent Claim
15 words
The apparatus of claim 14 wherein said source code is in a C++ programming language.
Claim 25
Dependent Claim
19 words
The apparatus of claim 14 wherein said prefix was parsed in a previous parse of a second translation unit.
Claim 26
Dependent Claim
22 words
The apparatus of claim 14 wherein said prefix was parsed in a previous parse of a different version of said translation unit.
Claim 27
Dependent Claim
19 words
The apparatus of claim 14 further including a preprocessor for preprocessing said source code to generate said translation unit.
References Cited (Backward Citations)
US4464650A
Cited
US4667290A
Cited
US5313387A
Cited
US5325531A
Cited
US5276880A
Cited
US5355493A
Cited
US5408603A
Cited
US5386570A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-21 | 2002-03-23 | 2002-09-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-21 | 2006-03-23 | 2006-09-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-21 | 2010-03-23 | 2010-09-22 | $7700.00 | Window Closed / Lapsed |