A backtracking LR algorithm for parsing ambiguous context-dependent languages

Parsing context-dependent computer lan-guages 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 difficult 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 pro-duced 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. Copyright c © 2006 Adrian D. Thurston and James R. Cordy. Permission to copy is hereby granted pro-vided the original copyright notice is reproduced in copies made.