Deep priority conflicts in the wild: a pilot study
Pages 55 - 66
Abstract
Context-free grammars are suitable for formalizing the syntax of programming languages concisely and declaratively. Thus, such grammars are often found in reference manuals of programming languages, and used in language workbenches for language prototyping. However, the natural and concise way of writing a context-free grammar is often ambiguous.
Safe and complete declarative disambiguation of operator precedence and associativity conflicts guarantees that all ambiguities arising from combining the operators of the language are resolved. Ambiguities can occur due to shallow conflicts, which can be captured by one-level tree patterns, and deep conflicts, which require more elaborate techniques. Approaches to solve deep priority conflicts include grammar transformations, which may result in large unambiguous grammars, or may require adapted parser technologies to include data-dependency tracking at parse time.
In this paper we study deep priority conflicts "in the wild". We investigate the efficiency of grammar transformations to solve deep priority conflicts by using a lazy parse table generation technique. On top of lazily-generated parse tables, we define metrics, aiming to answer how often deep priority conflicts occur in real-world programs and to what extent programmers explicitly disambiguate programs themselves. By applying our metrics to a small corpus of popular open-source repositories we found that in OCaml, up to 17% of the source files contain deep priority conflicts.
Supplementary Material
Auxiliary Archive (sle17-sle17main12-aux.zip)
- Download
- 4541.80 MB
References
[1]
Ali Afroozeh and Anastasia Izmaylova. 2015. Faster, Practical GLL Parsing. In Compiler Construction - 24th International Conference, CC 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings (Lecture Notes in Computer Science), Björn Franke (Ed.), Vol. 9031. Springer, 89–108.
[2]
Ali Afroozeh and Anastasia Izmaylova. 2016. Operator precedence for data-dependent grammars. In Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, Martin Erwig and Tiark Rompf (Eds.). ACM, 13–24.
[3]
Ali Afroozeh, Mark G. J. van den Brand, Adrian Johnstone, Elizabeth Scott, and Jurgen J. Vinju. 2013. Safe Specification of Operator Precedence Rules. In Software Language Engineering - 6th International Conference, SLE 2013, Indianapolis, IN, USA, October 26-28, 2013. Proceedings (Lecture Notes in Computer Science), Martin Erwig, Richard F. Paige, and Eric Van Wyk (Eds.), Vol. 8225. Springer, 137–156.
[4]
Raymond P.L. Buse and Westley R. Weimer. 2008. A Metric for Software Readability. In Proceedings of the 2008 International Symposium on Software Testing and Analysis (ISSTA ’08). ACM, New York, NY, USA, 121–130.
[5]
Luis Eduardo de Souza Amorim, Timothée Haudebourg, and Eelco Visser. 2017. Declarative Disambiguation of Deep Priority Conflicts. Technical Report TUD-SERG-2017-014. Delft University of Technology.
[6]
James Gosling, Bill Joy, Guy L. Steele Jr., Gilad Bracha, and Alex Buckley. 2013. The Java Language Specification, Java SE 7 Edition.
[7]
James Gosling, Bill Joy, Guy Steele, Gilad Bracha, and Alex Buckley. 2014. The Java Language Specification. Java SE 8 Edition.
[8]
Jan Heering, P. R. H. Hendriks, Paul Klint, and Jan Rekers. 1989. The syntax definition formalism SDF - reference manual. SIGPLAN Notices 24, 11 (1989), 43–75.
[9]
Jan Heering, Paul Klint, and Jan Rekers. 1989. Incremental Generation of Parsers. In PLDI. 179–191.
[10]
Mark Hills, Paul Klint, and Jurgen Vinju. 2013. An Empirical Study of PHP Feature Usage: A Static Analysis Perspective. In Proceedings of the 2013 International Symposium on Software Testing and Analysis (ISSTA 2013). ACM, New York, NY, USA, 325–335.
[11]
Andrew Hunt and David Thomas. 1999. The Pragmatic Programmer: From Journeyman to Master. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
[12]
S. C. Johnson. 1975. YACC—yet another compiler-compiler. Technical Report CS-32. AT & T Bell Laboratories, Murray Hill, N.J.
[13]
Lennart C. L. Kats, Eelco Visser, and Guido Wachsmuth. 2010. Pure and declarative syntax definition: paradise lost and regained. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, William R. Cook, Siobhán Clarke, and Martin C. Rinard (Eds.). ACM, Reno/Tahoe, Nevada, 918–932.
[14]
Paul Klint and Eelco Visser. 1994. Using Filters for the Disambiguation of Context-free Grammars. In Proceedings of the ASMICS Workshop on Parsing Theory. Tech. Rep. 126–1994, Dipartimento di Scienze dell’Informazione, Università di Milano, Milano, Italy.
[15]
Ralf Lämmel. 2001. Grammar Testing. In Fundamental Approaches to Software Engineering, FASE 2001 (Lecture Notes in Computer Science), Heinrich Hußmann (Ed.), Vol. 2029. Springer, 201–216.
[16]
Davy Landman, Alexander Serebrenik, Eric Bouwers, and Jurgen J. Vinju. 2016. Empirical analysis of the relationship between CC and SLOC in a large corpus of Java methods and C functions. Journal of Software: Evolution and Process 28, 7 (2016), 589–618.
[17]
Davy Landman, Alexander Serebrenik, and Jurgen J. Vinju. 2017. Challenges for Static Analysis of Java Reflection: Literature Review and Empirical Study. In Proceedings of the 39th International Conference on Software Engineering (ICSE ’17). IEEE Press, Piscataway, NJ, USA, 507–518.
[18]
Terence John Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) parsing: the power of dynamic analysis. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014, part of SPLASH 2014, Portland, OR, USA, October 20-24, 2014, Andrew P. Black and Todd D. Millstein (Eds.). ACM, 579–598.
[19]
T. Sedano. 2016. Code Readability Testing, an Empirical Study. In 2016 IEEE 29th International Conference on Software Engineering Education and Training (CSEET). 111–117.
[20]
Andreas Stefik and Susanna Siebert. 2013. An Empirical Investigation into Programming Language Syntax. Trans. Comput. Educ. 13, 4, Article 19 (Nov. 2013), 40 pages.
[21]
Masaru Tomita. 1985. An Efficient Context-Free Parsing Algorithm for Natural Languages. In IJCAI. 756–764.
[22]
Eelco Visser. 1997. Syntax Definition for Language Prototyping. Ph.D. Dissertation. University of Amsterdam. Advisor(s) Paul Klint.
[23]
Tobi Vollebregt, Lennart C. L. Kats, and Eelco Visser. 2012. Declarative specification of template-based textual editors. In International Workshop on Language Descriptions, Tools, and Applications, LDTA ’12, Tallinn, Estonia, March 31 - April 1, 2012, Anthony Sloane and Suzana Andova (Eds.). ACM.
Index Terms
- Deep priority conflicts in the wild: a pilot study
Recommendations
Operator precedence for data-dependent grammars
PEPM '16: Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program ManipulationConstructing parsers based on declarative specification of operator precedence is a very old research topic, and there are various existing approaches. However, these approaches are either tied to a particular parsing technique, or cannot deal with all ...
One parser to rule them all
Onward! 2015: 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!)Despite the long history of research in parsing, constructing parsers for real programming languages remains a difficult and painful task. In the last decades, different parser generators emerged to allow the construction of parsers from a BNF-like ...
An on-the-fly grammar modification mechanism for composing and defining extensible languages
Adaptable Parsing Expression Grammar (APEG) is a formal method for defining the syntax of programming languages. It provides an on-the-fly mechanism to perform modifications of the syntax of the language during parsing time. The primary goal of this ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2017
267 pages
ISBN:9781450355254
DOI:10.1145/3136014
- General Chair:
- Benoit Combemale,
- Program Chairs:
- Marjan Mernik,
- Bernhard Rumpe
Copyright © 2017 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2017
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Conference
SPLASH '17
Sponsor:
SPLASH '17: Conference on Systems, Programming, Languages, and Applications: Software for Humanity
October 23 - 24, 2017
BC, Vancouver, Canada
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 108Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in