ComputingComputer ScienceCompilersOperating SystemsProgramming LanguagesAbstract Syntax TreesData-flow AnalysisIntermediate RepresentationParsingSyntactic AnalysisSyntax AnalysisAbstract Syntax Tree MergingIntermediate Code GenerationLr Parsing
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 well-formed 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.
33
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
On the translation of languages from left to right
Donald E. Knuth · Information and Control · 1965 · 792 citations
A few billion lines of code later
Al Bessey, Ken Block, Ben Chelf et al. · Communications of the ACM · 2010 · 624 citations
A static analyzer for large safety-critical software
Bruno Blanchet, Patrick Cousot, Radhia Cousot et al. · ACM SIGPLAN Notices · 2003 · 577 citations
Bryan Ford · 2004 · 409 citations
Computing, Computer Science, Natural Language Processing +16