Block Level Parallelism in Parsing Block Structured Languages
Despite the long history of research in parallel parsing, constructing parallel parsers for programming languages remains a difficult and a painful task. Current parallel parsing techniques either face difficulty in creating Abstract Syntax Tree, requires modifications in the grammar, or are specific to less expressive grammars. Most of the programming languages like C, C++, Java are block-structured, and in these languages, different blocks can be parsed in parallel. Based on this property, we propose Block Parallelized Parser (BPP), which parses different blocks incrementally in parallel. BPP is based on two properties: (i) an incremental parser can parse any block of the source code without the need of parsing the whole source code, and (ii) blocks in a source code can be parsed independently of each other. BPP divides the source code into different blocks, parse each of them in par- allel, and wait for each thread to complete parsing. BPP is based on Incremental Jump Shift Reduce (I JSR) Parser [1]. In this paper, we first propose a notion of First Non-Terminals used to partition the set of Non-Terminals to be used with I JSR. We then present our BPP technique for LR(1) grammars. We believe that BPP can be easily extended to LR(k) grammars and can also be converted to an LALR(1) parser. We solve the hard problem of dividing text into several parts, executing parser on each of the part in parallel to create sub-AST for each part, and then combining all sub-ASTs into one AST.
Sun 22 OctDisplayed time zone: Tijuana, Baja California change
08:30 - 10:00 | |||
08:45 15mDay opening | Welcome Parsing@SLE Eric Van Wyk University of Minnesota, USA, Jurgen Vinju Centrum Wiskunde & Informatica / Technische Universiteit Eindhoven | ||
09:00 30mTalk | Block Level Parallelism in Parsing Block Structured Languages Parsing@SLE Abhinav Jangda University of Massachusetts, Amherst | ||
09:30 30mTalk | Parsing techniques for graph analysis Parsing@SLE |