Patent US5903756A successfully refreshed from Google Patents.
US5903756A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Variable lookahead parser generator
Assignee: Sun Microsystems Inc
•
Filing: 1996-10-11
•
Granted: 1999-05-11
•
Expires: 2016-10-11
Abstract
Abstract A description language and a parser generator for top-down parsers allows grammars for top-down parsers to be defined using a sequence of productions written as extended BNF expressions. For productions that are ambiguous, a lookahead construct in the grammar allows the programmer to specify an increased number of lookahead tokens. The lookahead construct can be specified on an expansion-by-expansion basis. As a result, the generated parser only maintains an increased number of lookahead tokens when required to process ambiguous productions.
Inventors
- 👤 Sriram Sankar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:26
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/42; G06F8/427; G06F8/30; G06F8/37
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
127 words
A method for creating a top-down parser, the method comprising the steps of: providing an input grammar, the input grammar including a one or more productions with each production including one or more expansions for transforming terminals and non-terminals into non-terminals, the one or more productions including at least one ambiguous production, each ambiguous production including a lookahead construct specifying the number of lookahead tokens required to disambiguate the ambiguous production; and processing the input grammar using a parser generator, the parser generator emitting source code for the top-down parser, the source code including code corresponding to each production, the source code corresponding to each ambiguous production including code causing the parser to maintain the number of lookahead tokens specified by the lookahead token of that production.
Claim 2
Independent Claim
127 words
A method for creating a top-down parser, the method comprising the steps of: providing an input grammar, the input grammar including a one or more productions with each production including one or more expansions for transforming terminals and non-terminals into non-terminals, the one or more productions including at least one ambiguous production, each ambiguous production including a lookahead construct specifying the number of lookahead tokens required to disambiguate the ambiguous production; and processing the input grammar using a parser generator, the parser generator emitting source code for the top-down parser, the source code including code corresponding to each production, the source code corresponding to each ambiguous production including code causing the parser to maintain the number of lookahead tokens specified by the lookahead token of that production.
Claim 3
Dependent Claim
35 words
A method as recited in claim 1 wherein the step of processing the input grammar using a parser generator further comprises the step of emitting a Java™ method for each production in the input grammar.
Claim 4
Dependent Claim
45 words
A method as recited in claim 2 wherein the step of processing the input grammar using a parser generator further comprises the step of emitting a call to a lookahead agent as part of each Java™ method for each ambiguous production in the input grammar.
Claim 5
Dependent Claim
42 words
A method as recited in claim 1 further comprising the step of processing the input grammar to emit source code for a lexical analyzer, the source code for the lexical analyzer including code corresponding to each terminal included in the input grammar.
Claim 6
Independent Claim
88 words
A method for creating a top-down parser, the method comprising the steps of: providing an input grammar, the grammar including a one or more productions with each production including one or more expansions for transforming terminals and non-terminals into non-terminals; and processing the input grammar using an analysis tool to yield the top-down parser, the analysis tool detecting productions which are ambiguous, the analysis tool adding a lookahead construct to each ambiguous production, the lookahead construct specifying the number of lookahead tokens required to disambiguate the ambiguous production.
Claim 7
Independent Claim
88 words
A method for creating a top-down parser, the method comprising the steps of: providing an input grammar, the grammar including a one or more productions with each production including one or more expansions for transforming terminals and non-terminals into non-terminals; and processing the input grammar using an analysis tool to yield the top-down parser, the analysis tool detecting productions which are ambiguous, the analysis tool adding a lookahead construct to each ambiguous production, the lookahead construct specifying the number of lookahead tokens required to disambiguate the ambiguous production.
Claim 8
Dependent Claim
66 words
A method as recited in claim 5 further comprising the step of: processing the input grammar using a parser generator, the parser generator emitting source code for a parser, the source code including code corresponding to each production, the source code corresponding to each ambiguous production including code causing the parser to maintain the number of lookahead tokens specified by the lookahead token of that production.
Claim 9
Dependent Claim
35 words
A method as recited in claim 6 wherein the step of processing the input grammar using a parser generator further comprises the step of emitting a Java™ method for each production in the input grammar.
Claim 10
Dependent Claim
45 words
A method as recited in claim 7 wherein the step of processing the input grammar using a parser generator further comprises the step of emitting a call to a lookahead agent as part of each Java™ method for each ambiguous production in the input grammar.
Claim 11
Dependent Claim
40 words
A method as recited in claim 5 further comprising the step of processing the input grammar to emit source code for a scanner, the source code for the scanner including code corresponding to each terminal included in the input grammar.
Claim 12
Dependent Claim
212 words
A computer program product comprising: a computer usable medium having computer readable code embodied therein for analyzing an input grammar describing a source language to create a top-down parser, the computer program product including: first computer readable program code devices configured to cause a computer to analyze productions within the input grammar where each production, includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language, the first computer readable program code devices further configured to cause the computer to emit code for each production in the input grammar, the code emitted for each production executable by a computer to recognize the sequences of terminals and non-terminals in the source language which correspond to the expansions included in the production; and second computer readable program code devices configured to cause the computer to recognize lookahead constructs in the input grammar, each lookahead construct associated with a production, each lookahead construct specifying a number of lookahead tokens which are to be used by the top-down parser when processing the production, the second computer readable program code devices further configured to cause the computer to emit code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 13
Dependent Claim
212 words
A computer program product comprising: a computer usable medium having computer readable code embodied therein for analyzing an input grammar describing a source language to create a top-down parser, the computer program product including: first computer readable program code devices configured to cause a computer to analyze productions within the input grammar where each production, includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language, the first computer readable program code devices further configured to cause the computer to emit code for each production in the input grammar, the code emitted for each production executable by a computer to recognize the sequences of terminals and non-terminals in the source language which correspond to the expansions included in the production; and second computer readable program code devices configured to cause the computer to recognize lookahead constructs in the input grammar, each lookahead construct associated with a production, each lookahead construct specifying a number of lookahead tokens which are to be used by the top-down parser when processing the production, the second computer readable program code devices further configured to cause the computer to emit code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 14
Dependent Claim
56 words
A computer program product as recited in claim 10 further comprising third computer readable program code device configured to cause the computer to analyze terminals in the input grammar, the third computer readable program code device further configured to cause the computer to emit code for a lexical scanner for each terminal in the input grammar.
Claim 15
Dependent Claim
35 words
A computer program product as recited in claim 10 wherein the first computer readable program code devices are configured to cause the computer to emit a Java™ method for each production in the input grammar.
Claim 16
Independent Claim
165 words
An apparatus for processing an input grammar for a source language to create a top-down parser for the source language, the apparatus comprising: a first portion configured to analyze productions in the input grammar where each production Includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language, the first portion emitting code for each production in the input grammar, the code emitted for each production executable by a computer to recognize the sequences of terminals and non-terminals in the source language which correspond to the expansions included in the production; and a second portion configured to recognize lookahead constructs in the input grammar, each construct associated with one of the productions, each construct specifying a number of lookahead tokens which are to be used by the top-down parser when processing the production, the second portion emitting code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 17
Independent Claim
165 words
An apparatus for processing an input grammar for a source language to create a top-down parser for the source language, the apparatus comprising: a first portion configured to analyze productions in the input grammar where each production Includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language, the first portion emitting code for each production in the input grammar, the code emitted for each production executable by a computer to recognize the sequences of terminals and non-terminals in the source language which correspond to the expansions included in the production; and a second portion configured to recognize lookahead constructs in the input grammar, each construct associated with one of the productions, each construct specifying a number of lookahead tokens which are to be used by the top-down parser when processing the production, the second portion emitting code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 18
Independent Claim
132 words
A method for creating a top-down parser for a source language, the method comprising the steps of: analyzing productions in an input grammar where each production includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language; emitting code for each production in the input grammar, the code emitted for each production executable by a computer to recognize sequences of terminals and non-terminals in the source language; recognizing lookahead constructs in the input grammar, each construct associated with one of the productions, each construct specifying a number of lookahead tokens which are to be used by the parser when processing the production; and emitting code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 19
Independent Claim
132 words
A method for creating a top-down parser for a source language, the method comprising the steps of: analyzing productions in an input grammar where each production includes one or more expansions corresponding to sequences of terminals and non-terminals in the source language; emitting code for each production in the input grammar, the code emitted for each production executable by a computer to recognize sequences of terminals and non-terminals in the source language; recognizing lookahead constructs in the input grammar, each construct associated with one of the productions, each construct specifying a number of lookahead tokens which are to be used by the parser when processing the production; and emitting code executable by a computer to cause the top-down parser to maintain the specified number of lookahead tokens when processing the associated production.
Claim 20
Dependent Claim
54 words
A method as recited in claim 14 further comprising the step of processing the input grammar using an analysis tool, the analysis tool detecting productions which are ambiguous, the analysis tool adding a lookahead construct to each ambiguous production, the lookahead construct specifying the number of lookahead tokens required to disambiguate the ambiguous production.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-10 | 2002-11-09 | 2003-05-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-10 | 2006-11-09 | 2007-05-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-10 | 2010-11-09 | 2011-05-11 | $7700.00 | Window Closed / Lapsed |