SuperC: Parsing all of C by taming the preprocessor

Paul Gazzillo, Robert Grimm

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

C tools, such as source browsers, bug finders, and automated refactorings, need to process two languages: C itself and the preprocessor. The latter improves expressivity through file includes, macros, and static conditionals. But it operates only on tokens, making it hard to even parse both languages. This paper presents a complete, performant solution to this problem. First, a configuration preserving preprocessor resolves includes and macros yet leaves static conditionals intact, thus preserving a program's variability. To ensure completeness, we analyze all interactions between preprocessor features and identify techniques for correctly handling them. Second, a configuration- preserving parser generates a wellformed AST with static choice nodes for conditionals. It forks new subparsers when encountering static conditionals and merges them again after the conditionals. To ensure performance, we present a simple algorithm for table-driven Fork-Merge LR parsing and four novel optimizations. We demonstrate the effectiveness of our approach on the x86 Linux kernel.

Original languageEnglish (US)
Title of host publicationPLDI'12 - Proceedings of the 2012 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages323-334
Number of pages12
DOIs
StatePublished - 2012
Event33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'12 - Beijing, China
Duration: Jun 11 2012Jun 16 2012

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'12
CountryChina
CityBeijing
Period6/11/126/16/12

Keywords

  • C
  • Fork-merge LR parsing
  • LR parsing
  • Preprocessor
  • SuperC

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'SuperC: Parsing all of C by taming the preprocessor'. Together they form a unique fingerprint.

Cite this