Top-Down Parsing with Parsing Contexts

Citations Over TimeTop 13% of 2015 papers

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. Im- plementors of programming language parsers have adopted various techniques, such as hand-written parsers, special lex- ers, 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 tradi- tional approach that uses only the input stream as an input to a parsing function, we use a parsing context that provides ac- cess to a stream and possibly to other context-sensitive infor- mation. 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 el- ement names) parsing. We demonstrate our solution with PetitParser, a parsing-expression grammar based, top-down, parser combinator framework written in Smalltalk.

Related Papers

• → A graph grammar approach to graphical parsing(2002)65 cited
• → Parsing for agile modeling(2016)2 cited
• A computer language transformation system capable of generalized context-dependent parsing(2009)
• A parsing system based on logic programming(1987)
• → Generation of Indexes for Compiling Efficient Parsers from Formal Specifications(2007)2 cited