Approaches to recovering from syntax errors

One may adopt different approaches to handling syntax errors in the programs to be analysed by a parser:

• Terminate the analysis when the first syntax error is encountered.
• Continue the syntax analysis by trying to find a possible interpretation of the sentence (at the syntactic level) without introducing too many error messages due to a wrong interpretation.
  • Issues: If the next terminal symbol is not correct, one should consider the following possibilities:
    • skip the symbol and continue the analysis without changing the content of the syntax analysis stack (assuming that the symbol was inserted by error)
    • insert a terminal symbol that is valid at this point of the syntax analysis (assuming that the symbol was forgotten)
    • replace the symbol by a symbol that is acceptable at this point.
    • consider the possibility that the error was actually already earlier with the string that was already analysed (in this case, one has to go back in the analysis; for instance, one may drop the last nonterminal on the syntax stack.
  • Error recovery is difficult in general. The best approach may also depend on the frequency that certain errors are made by typical users.
  • Certain systematic approaches to syntax error recovery have been proposed. Among those is the so-called "panic mode" which can be applied for top-down analysis of any grammar and is based on the First and Follow sets of the nonterminals, as explained in the following:
    • Principle: If an error is detected, the following situations are distinguished:
      • a specific terminal is expected: Action: one assumes that the terminal was forgotten in the sentence (the terminal is taken off the syntax stack)
      • a specific nonterminal is expected: if there is an error, this means that the next terminal is not in the First set of that nonterminal. In this case one skips the next terminals until one finds a terminal that belongs to the First set of the expected nonterminal, or one that belongs to its Follow set. If the terminal is in the First set, one continues the analysis at this point of the input string. If the terminal is in the Follow set, one eliminates the nonterminal from the syntax stack (or in the case of recursive procedures, the procedure of the nonterminal returns immediately).
    • Example: Here is a grammar and its syntax table
    •     
    • In the following syntax table, an empty field means that the terminal in question should be skipped. The entry sync means that the nonterminal should be removed from the top of the syntax stack (because the terminal is included in the Follow set).
    • 

Translated from french: March 3, 2008