Top-Down Parsing with Parsing Contexts

Kurs, Jan; Lungu, Mircea; Nierstrasz, Oscar (2014). Top-Down Parsing with Parsing Contexts. In: Proceedings of International Workshop on Smalltalk Technologies (IWST 2014).

[img] Text
Kurs14a-ParsingContext.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (198kB) | Request a copy

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.

Item Type:

Conference or Workshop Item (Paper)


08 Faculty of Science > Institute of Computer Science (INF)
08 Faculty of Science > Institute of Computer Science (INF) > Software Composition Group (SCG)

UniBE Contributor:

Kurs, Jan; Lungu, Mircea and Nierstrasz, Oscar Marius


000 Computer science, knowledge & systems
500 Science > 510 Mathematics




Oscar Nierstrasz

Date Deposited:

23 Apr 2015 09:49

Last Modified:

08 Feb 2017 11:36

Uncontrolled Keywords:

scg14 scg-pub jb14 snf-asa missing-doi




Actions (login required)

Edit item Edit item
Provide Feedback