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.
Monadic parsing @cite_12 is a well-known way to build functional-style parser-combinator libraries, made popular by Haskell libraries such as Parsec @cite_11 . In this paradigm, the type of a parser is a function parameterized by a result type, i.e. with signature @math , where the parameter string is the input text and the returned string is the input remaining after parsing. The parser type is also a monad instance, meaning there is a bind function whose signature, in Haskell notation, is:
@cite_12 @cite_11
1997644097 2123835026
This paper is a tutorial on defining recursive descent parsers in Haskell. In the spirit of one-stop shopping, the paper combines material from three areas into a single source. The three areas are functional parsers, the use of monads to structure functional programs, and the use of special syntax for monadic programs in Haskell. More specifically, the paper shows how to define monadic parsers using do notation in Haskell. The paper is targeted at the level of a good undergraduate student who is familiar with Haskell, and has completed a grammars and parsing course. Some knowledge of functional parsers would be useful, but no experience with monads is assumed. Despite the long list of publications on parser combinators, there does not yet exist a monadic parser combinator library that is applicable in real world situations. In particular naive implementations of parser combinators are likely to suffer from space leaks and are often unable to report precise error messages in case of parse errors. The Parsec parser combinator library described in this paper, utilizes a novel implementation technique for space and time e±cient parser combinators that in case of a parse error, report both the position of the error as well as all grammar productions that would have been legal at that point in the input.