Synchronization and error recovery

For an ambiguous grammar, the parser may search multiple paths. If an error occurs in one path, it abandons that path and tries the remaining ones. Very often, the correct path is found before all other paths have been tried, though. If an error occurs on the correct path, the parser will therefore abandon it and try incorrect ones, ultimately leading to false error messages.

To avoid that situation, synchronization points can be set in the grammar. Once passed, the parser will not backtrack beyond that point. Synchronization points are usually put after constructs, that you are certain to be correct, once they have been parsed successfully. The end of a declaration or the end of a statement in a programming language are examples for such points.

To insert a synchronization point in a rule, add the !(sync) operator:

Decl
{
    Decls !(sync) Decl;
    Decl;
}

Lists of declarations or statements provide typical synchronization points, as shown in the example.

For grammars with conflicts, good placement of synchronization points may be required to obtain useful error messages. If the grammar has no conflicts, synchronization points do not affect the error messages, because there will always be a single path.

Synchronization points are also used for error recovery. APaGeD may recover from errors and try to parse the rest of the file. In order to do so, it ignores the terminal, that produces the error, throws away non-terminal symbols that have been reduced until it reaches a synchronization point and continues parsing.