SuperC: Parsing all of C by taming the preprocessor

Paul Gazzillo, Robert Grimm

Research output: Contribution to journalArticlepeer-review

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 configurationpreserving 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)
Pages (from-to)323-334
Number of pages12
JournalACM SIGPLAN Notices
Volume47
Issue number6
DOIs
StatePublished - Aug 2012

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

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

Cite this