Generation of error messages and error recovery for an LL(1) parser

• US 5,487,147 A
• Filed: 09/05/1991
• Issued: 01/23/1996
• Est. Priority Date: 09/05/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brisson, James P.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Snyder, Glenn
• Application Number:
  US07/755,270
• Time in Patent Office: 1,601 Days
• Field of Search: 395/575, 364/280.4, 364/419.08
• US Class Current: 714/1
• CPC Class Codes: G06F 8/427 Parsing

Abstract

The syntactic definition of a grammar for language statements is the basis for a method for automatically generating error messages and error recovery for the language statements. The grammar is used to produce a parser, an error message generator, and error recovery for the language statements. The error message generator is produced automatically along with a parser and provides an indication of alternative valid input symbols. The method also produces the automatic generation of expected symbols lists to achieve error message generation goals. The error recovery routines are also produced automatically along with a parser and provide an indication of where valid parsing continues in the event of error detection in the language statements. The method also uses the dynamic generation of sets of synchronization symbols to achieve error recovery goals.

Claims

1. A method for dynamically producing a set of synchronizing symbols, said method comprising the steps of:

creating a copy of a parsing stack, said parsing stack being produced by a parser operating consistently with a set of grammar rules to create said stack;

adding a bottom of stack indicator to the set of synchronizing symbols;

scanning said stack to determine if the symbol at the top of the stack is the bottom of stack indicator and terminate synchronizing symbol accumulation if it is, otherwise, continue processing by;

determining if the symbol at the top of the stack is a nonterminal symbol in said grammar and, if so, adding First set symbols associated with said top of stack symbol to said set of synchronizing symbols and replacing said nonterminal symbol on said stack in accordance with a designated grammar rule for it, and continuing processing at said scanning step, but if said top of stack symbol is not a nonterminal symbol, continue processing by;

determining if said top of stack symbol is a terminal symbol in said grammar and, if so, adding said terminal symbol to said set of synchronizing symbols and removing said terminal symbol from said stack and continuing processing at said scanning step, but if said top of stack symbol is neither a terminal symbol nor a nonterminal symbol, continue processing by;

removing said neither terminal nor nonterminal symbol from said stack and continue processing at said scan step.

2. The method of claim 1 in which the roles of said stack and said stack copy are reversed.

3. A method for dynamically producing a set of synchronizing symbols, said method comprising the steps of:

scanning down a parsing stack using top of stack symbols to determine which symbols to add to the set of synchronizing symbols, said stack being produced by a parser operating consistently with a set of grammar rules to create said stack;

modifying the stack in response to a top of stack symbol and a designated grammar rule such that the top of stack symbol is removed from the stack and the designated grammar rule is added to the stack; and

terminating said scanning and modification upon encountering a bottom of stack symbol in said stack.