RECORD
Taming Context-Sensitive Languages with Principled Stateful Parsing
Programming Languages · Submitted 17 Sep 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We introduce principled stateful parsing as a new transactional discipline that makes state changes transparent to parsing mechanisms such as backtracking and memoization.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Historically, true context-sensitive parsing has seldom been applied to programming languages, due to its inherent complexity. | background 1.00 | 0.05 | 0.03 | asserted 1.00 |
| s1 | However, many mainstream programming and markup languages (C, Haskell, Python, XML, and more) possess context-sensitive features. | background 1.00 | 0.07 | 0.03 | asserted 1.00 |
| s2 | These features are traditionally handled with ad-hoc code (e.g., custom lexers), outside of the scope of parsing theory. | background 0.98 | 0.04 | 0.02 | asserted 1.00 |
| s3 | Current grammar formalisms struggle to express context-sensitive features. | background 0.76 | 0.07 | 0.02 | asserted 1.00 |
| s4 | Most solutions lack context transparency: they make grammars hard to write, maintain and compose by hardwiring context through the entire grammar. | background 0.57 | 0.07 | 0.05 | asserted 1.00 |
| s5 | 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. | method 0.55 | 0.53 | 0.20 | hedged possibility 0.69 |
| s6 | We make use of mutable parse state to enable this form of recall. | method 0.94 | 0.88 | 0.07 | asserted 1.00 |
| s7 | We introduce principled stateful parsing as a new transactional discipline that makes state changes transparent to parsing mechanisms such as backtracking and memoization. | contribution 0.96 | 0.92 | 0.42 | asserted 1.00 |
| s8 | To enforce this discipline, users specify parsers using formally specified primitive state manipulation operations. | method 0.96 | 0.78 | 0.09 | asserted 1.00 |
| s9 | Our solution is available as a parsing library named Autumn. | contribution 0.89 | 0.87 | 0.06 | asserted 1.00 |
| s10 | We illustrate our solution by implementing some practical context-sensitive grammar features such as significant whitespace handling and namespace classification. | contribution 0.78 | 0.95 | 0.09 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.