Historically, true context-sensitive parsing has seldom been applied to programming languages, due to its inherent complexity. However, many mainstream programming and markup languages (C, Haskell, Python, XML, and more) possess context-sensitive features. These features are traditionally handled with ad-hoc code (e.g., custom lexers), outside of the scope of parsing theory. Current grammar formalisms struggle to express context-sensitive features. Most solutions lack context transparency: they make grammars hard to write, maintain and compose by hardwiring context through the entire grammar. Instead, we approach context-sensitive parsing through the idea that parsers may recall previously matched input (or data derived therefrom) in order to make parsing decisions. We make use of mutable parse state to enable this form of recall. We introduce principled stateful parsing as a new transactional discipline that makes state changes transparent to parsing mechanisms such as backtracking and memoization. To enforce this discipline, users specify parsers using formally specified primitive state manipulation operations. Our solution is available as a parsing library named Autumn. We illustrate our solution by implementing some practical context-sensitive grammar features such as significant whitespace handling and namespace classification.
Parsing with backtracking semantic actions @cite_6 is an approach that extends a (general) backtracking LR parser with reversible semantic actions. Upon backtracking, state changes are reversed. Two important restrictions apply: state changes can only occur during term reduction, and the state can only affect the parse through semantic conditions that trigger backtracking.
@cite_6
2011321377
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 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 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.