Presentation: Practical Scope Recovery using Bridge Parsing

Date: September 23, 2008 (Tuesday) at 10:15

Emma Nilsson Nyman presents the article "Practical Scope Recovery using Bridge
Parsing", by Emma Nilsson-Nyman, Torbjörn Ekman and Görel Hedin, to appear at
the 1st International Conference on Software Language Engineering, Toulouse,
Sept 29-30, 2008.

Interactive development environments (IDEs) increase programmer productivity,
but unfortunately also the burden on language implementors since sophisticated
tool support is expected even for small domain-specific languages. Our goal is
to alleviate that burden, by generating IDEs from high-level language
specifications using the JastAdd meta-compiler system. This puts increased
tension on scope recovery in parsers, since at least a partial AST is required
by the system to perform static analysis, such as name completion and context
sensitive search.

In this paper we present a novel recovery algorithm called bridge parsing,
which provides a light-weight recovery mechanism that complements existing
parsing recovery techniques. An initial phase recovers nesting structure in
source files making them easier to process by existing parsers. This enables
batch parser generators with existing grammars to be used in an interactive
setting with minor or no modifications.

We have implemented bridge parsing in a generic extensible IDE for JastAdd
based compilers. It is independent of parsing technology, which we validate by
showing how it improves recovery in a set of typical interactive editing
scenarios for three parser generators: ANTLR (LL(variable lookahead) parsers),
LPG (LALR(k) parsers), and Beaver (LALR(1) parsers). ANTLR and LPG both contain
sophisticated support for error recovery, while Beaver requires manual error
productions. Bridge parsing complements these techniques and yields better
recovery for all these tools with only minimal changes to existing grammars.

Room: E:2116

Last modified Dec 9, 2011 12:59 pm