A Backtracking LR Algorithm for Parsing Ambiguous Context-Dependent Languages

Parsing context-dependent computer languages requires an ability to maintain and query data structures while parsing for the purpose of influencing the parse. Parsing ambiguous computer languages requires an ability to generate a parser for arbitrary context-free grammars. In both cases we have tools for generating parsers from a grammar. However, languages that have both of these properties simultaneously are much more di#cult to parse. Consequently, we have fewer techniques. One approach to parsing such languages is to endow traditional LR systems with backtracking. This is a step towards a working solution, however there are number of problems. In this work we present two enhancements to a basic backtracking LR approach which enable the parsing of computer languages that are both context-dependent and ambiguous. Using our system we have produced a fast parser for C++ that is composed of strictly a scanner, a name lookup stage and parser generated from a grammar augmented with semantic actions and semantic `undo' actions. Language ambiguities are resolved by prioritizing grammar declarations