Write a Blog >>
Sun 22 - Fri 27 October 2017 Vancouver, Canada
Sun 22 Oct 2017 09:00 - 09:30 at Oxford - Session 1 Chair(s): Eric Van Wyk

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 Oct

Displayed time zone: Tijuana, Baja California change

08:30 - 10:00
Session 1Parsing@SLE at Oxford
Chair(s): Eric Van Wyk University of Minnesota, USA
Day opening
Eric Van Wyk University of Minnesota, USA, Jurgen Vinju Centrum Wiskunde & Informatica / Technische Universiteit Eindhoven
Block Level Parallelism in Parsing Block Structured Languages
Abhinav Jangda University of Massachusetts, Amherst
Parsing techniques for graph analysis