Thu 25 Mar 2021 15:30 - 16:00 at Virtual Space C - Session 11 Chair(s): Jeremy Gibbons
Fri 26 Mar 2021 16:00 - 16:30 at Virtual Space A - Session 16 Chair(s): Theo D'Hondt

Context: An island parser reads an input text and builds the parse (or abstract syntax) tree of only the programming constructs of interest in the text. These constructs are called islands and the rest of the text is called water, which the parser ignores and skips over. Since an island parser does not have to parse all the details of the input, it is often easy to develop but still useful enough for a number of software engineering tools. When a parser generator is used, the developer can implement an island parser by just describing a small number of grammar rules, for example, in Parsing Expression Grammar (PEG).

Inquiry: In practice, however, the grammar rules are often complicated since the developer must define the water inside the island; otherwise, the island parsing will not reduce the total number of grammar rules. When describing the grammar rules for such water, the developer must consider other rules and enumerate a set of symbols, which we call alternative symbols. Due to this difficulty, island parsing seems to be not widely used today despite its usefulness in many applications.

Approach: This paper proposes the lake symbols for addressing this difficulty in developing an island parser. It also presents an extension to PEG for supporting the lake symbols. The lake symbols automate the enumeration of the alternative symbols for the water inside an island. The paper proposes an algorithm for translating the extended PEG to the normal PEG, which can be given to an existing parser generator based on PEG.

Knowledge: The user can use lake symbols to define water without specifying each alternative symbol. Our algorithms can calculate all alternative symbols for a lake symbol, based on where the lake symbol is used in the grammar.

Grounding: We implemented a parser generator accepting our extended PEG and implemented 36 island parsers for Java and 20 island parsers for Python. Our experiments show that the lake symbols reduce 42 % of grammar rules for Java and 89 % of rules for Python on average, excluding the case where islands are expressions.

Importance: This work eases the use of island parsing. Lake symbols enable the user to define the water inside the island simpler than before. Defining water inside the island is essential to apply island parsing for practical programming languages.

Conference Day
Thu 25 Mar

Displayed time zone: Belfast change

15:00 - 16:30
Session 11Research Papers at Virtual Space C
Chair(s): Jeremy GibbonsDepartment of Computer Science, University of Oxford
15:00
30m
Live Q&A
Functional Programming in Pattern-Match-Oriented Programming Style
Research Papers
Satoshi EgiRakuten Institute of Technology, Rakuten, Inc. / The University of Tokyo, Yuichi NishiwakiThe University of Tokyo
DOI Media Attached
15:30
30m
Live Q&A
Lake symbols for island parsing
Research Papers
Katsumi OkudaThe University of Tokyo / Mitsubishi Electric Corporation, Shigeru ChibaThe University of Tokyo
DOI Media Attached
16:00
30m
Live Q&A
Programming Paradigms, Turing Completeness and Computational Thinking
Research Papers
Greg MichaelsonHeriot-Watt University
DOI Media Attached

Conference Day
Fri 26 Mar

Displayed time zone: Belfast change

15:00 - 16:30
Session 16Research Papers at Virtual Space A
Chair(s): Theo D'HondtVrije Universiteit Brussel
15:00
30m
Live Q&A
Using Relational Problems to Teach Property-Based Testing
Research Papers
John WrennBrown University, Tim NelsonBrown University, Shriram KrishnamurthiBrown University, United States
DOI Media Attached
15:30
30m
Live Q&A
Reference Capabilities for Safe Parallel Array Programming
Research Papers
Beatrice ÅkerblomStockholm University, Elias CastegrenKTH, Tobias WrigstadUppsala University, Sweden
DOI Media Attached
16:00
30m
Live Q&A
Lake symbols for island parsing
Research Papers
Katsumi OkudaThe University of Tokyo / Mitsubishi Electric Corporation, Shigeru ChibaThe University of Tokyo
DOI Media Attached