Precedence and associativity declarations in systems like yacc
resolve ambiguities in context-free grammars (CFGs) by specifying restrictions on allowed parses. However, they are special purpose and do not handle many other grammatical restrictions that language designers need in order to resolve ambiguities like dangling else
, the interactions between binary operators and functional if
expressions in ML, and the interactions between object allocation and function calls in JavaScript. Often, language designers resort to restructuring their grammars in order to encode these restrictions, but this obfuscates the designer's intent and makes grammars difficult to read, write, and maintain.
In this paper, we show how tree automata can modularly and concisely encode such restrictions. We do this by reinterpreting CFGs as tree automata and intersecting them with tree automata encoding the desired restrictions. The results are then reinterpreted back into CFGs that encode the specified restrictions. This process can be used as a
preprocessing step before other CFG manipulations and is well behaved. It performs well in practice and never introduces ambiguities or LR($k$) conflicts.
Thu 26 OctDisplayed time zone: Tijuana, Baja California change
13:30 - 15:00 | Mining Software Repositories and ParsingOOPSLA at Regency A Chair(s): Wolfgang De Meuter Vrije Universiteit Brussel | ||
13:30 22mTalk | Exploiting Implicit Beliefs to Resolve Sparse Usage Problem in Usage-Based Specification Mining OOPSLA Samantha Syeda Khairunnesa Iowa State University, Hoan Anh Nguyen Iowa State University, USA, Tien N. Nguyen University of Texas at Dallas, Hridesh Rajan Iowa State University DOI | ||
13:52 22mTalk | DéjàVu: A Map of Code Duplicates on GitHub OOPSLA Crista Lopes University of California, Irvine, Petr Maj ReactorLabs, Pedro Martins University of California at Irvine, USA, Vaibhav Saini University of California at Irvine, USA, Di Yang University of California at Irvine, USA, Jakub Zitny Czech Technical University, Czechia, Hitesh Sajnani Microsoft , Jan Vitek Northeastern University, USA DOI | ||
14:15 22mTalk | Understanding the Use of Lambda Expressions in Java OOPSLA Davood Mazinanian Concordia University, Canada, Ameya Ketkar Oregon State University, USA, Nikolaos Tsantalis Concordia University, Canada, Danny Dig School of EECS at Oregon State University DOI | ||
14:37 22mTalk | Restricting Grammars with Tree Automata OOPSLA DOI |