Title: Top-Down Parsing with Parsing Contexts A Simple Approach to Context-Sensitive Parsing
Abstract: The domain of context-free languages has been extensively explored and there exist numerous techniques for parsing (all or a subset of) context-free languages. Unfortunately, some programming languages are not context-free. Using standard context-free parsing techniques to parse a context-sensitive programming language poses a considerable challenge. Implementors of programming language parsers have adopted various techniques, such as hand-written parsers, special lexers, or post-processing of an ambiguous parser output to deal with that challenge. In this paper we suggest a simple extension of a top-down parser with contextual information. Contrary to the traditional approach that uses only the input stream as an input to a parsing function, we use a parsing context that provides access to a stream and possibly to other context-sensitive information. At a same time we keep the context-free formalism so a grammar definition stays simple without mind-blowing context-sensitive rules. We show that our approach can be used for various purposes such as indent-sensitive parsing, a high-precision island parsing or XML (with arbitrary element names) parsing. We demonstrate our solution with PetitParser, a parsing-expression grammar based, top-down, parser combinator framework written in Smalltalk.
Publication Year: 2014
Publication Date: 2014-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot