Parse views with Boolean grammars

• We introduce Boolean grammars from language theory to the parsing/reengineering community.
• We describe how Boolean grammars can improve programming language expressiveness and be used for agile parsing.
• We discuss its potential for source transformation systems.
• We demonstrate our progress implementing Boolean grammars in TXL.

We propose an enhancement to current parsing and transformation systems by leveraging the expressive power of Boolean grammars, a generalization of context-free grammars that adds conjunction and negation operators. In addition to naturally expressing a larger class of languages, Boolean grammars capture multiple parse trees of the same document simultaneously and the ability to switch between these parse “views”. In particular, source transformation and reengineering tasks can benefit from parse views by recasting the input text into whichever parse is most suitable for the task at hand.