Write a Blog >>
SPLASH 2017
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
08:45
15m
Day opening
Welcome
Parsing@SLE
Eric Van Wyk University of Minnesota, USA, Jurgen Vinju Centrum Wiskunde & Informatica / Technische Universiteit Eindhoven
09:00
30m
Talk
Block Level Parallelism in Parsing Block Structured Languages
Parsing@SLE
Abhinav Jangda University of Massachusetts, Amherst
09:30
30m
Talk
Parsing techniques for graph analysis
Parsing@SLE