Zirun Zhu
Hsiang-Shang Ko
João Saraiva
ABSTRACT
Language designers usually need to implement parsers and printers. Despite being two intimately related programs, in practice they are often designed separately, and then need to be revised and kept consistent as the language evolves. It will be more convenient if the parser and printer can be unified and developed in one single program, with their consistency guaranteed automatically.
Furthermore, in certain scenarios (like showing compiler optimisation results to the programmer), it is desirable to have a more powerful reflective printer that, when an abstract syntax tree corresponding to a piece of program text is modified, can reflect the modification to the program text while preserving layouts, comments, and syntactic sugar.
To address these needs, we propose a domain-specific language BiYacc, whose programs denote both a parser and a reflective printer for an unambiguous context-free grammar. BiYacc is based on the theory of bidirectional transformations, which helps to guarantee by construction that the pairs of parsers and reflective printers generated by BiYacc are consistent. We show that BiYacc is capable of facilitating many tasks such as Pombrio and Krishnamurthi's "resugaring", simple refactoring, and language evolution.
Supplemental Material
Available for Download
Materials passed artefact evaluation
- A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Google Scholar
Digital Library
- R. Boulton. Syn: A single language for specifying abstract syntax trees, lexical analysis, parsing and pretty-printing. Technical Report Number 390, Computer Laboratory, University of Cambridge, 1966.Google Scholar
- C. Brabrand, A. Møller, and M. I. Schwartzbach. Dual syntax for XML languages. Information Systems, 33(4):385–406, 2008. Google ScholarDigital Library
- K. Czarnecki, J. N. Foster, Z. Hu, R. Lämmel, A. Schürr, and J. Terwilliger. Bidirectional transformations: A cross-discipline perspective. In International Conference on Model Transformation, volume 5563 of Lecture Notes in Computer Science, pages 260– 283. Springer, 2009. Google ScholarDigital Library
- M. De Jonge. Pretty-printing for software reengineering. In International Conference on Software Maintenance, pages 550– 559. IEEE, 2002. Google ScholarDigital Library
- M. de Jonge and E. Visser. An algorithm for layout preservation in refactoring transformations. In International Conference on Software Language Engineering, volume 6940 of Lecture Notes in Computer Science, pages 40–59. Springer, 2012. Google ScholarDigital Library
- E. W. Dijkstra. Guarded commands, nondeterminacy and formal derivation of programs. Communications of the ACM, 18(8): 453–457, 1975. Google ScholarDigital Library
- J. Dureg˚ard and P. Jansson. Embedded parser generators. In Haskell Symposium, pages 107–117. ACM, 2011. Google ScholarDigital Library
- S. Fischer, Z. Hu, and H. Pacheco. The essence of bidirectional programming. Science China Information Sciences, 58(5):1–21, 2015.Google ScholarCross Ref
- J. N. Foster. Bidirectional programming languages. PhD thesis, University of Pennsylvania, 2009. Google ScholarDigital Library
- J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems, 29(3):17, 2007. Google ScholarDigital Library
- M. Hirzel and K. H. Rose. Tiger language specification. https://cs.nyu.edu/courses/fall13/CSCI-GA.2130-001/tigerspec.pdf, 2013.Google Scholar
- Z. Hu, A. Schurr, P. Stevens, and J. F. Terwilliger. Dagstuhl seminar on bidirectional transformations (BX). ACM SIGMOD Record, 40(1):35–39, 2011. Google ScholarDigital Library
- Z. Hu, H. Pacheco, and S. Fischer. Validity checking of putback transformations in bidirectional programming. In International Symposium on Formal Methods, volume 8442 of Lecture Notes in Computer Science, pages 1–15. Springer, 2014. Google ScholarDigital Library
- B. W. Kernighan, D. M. Ritchie, and P. Ejeklint. The C programming language, volume 2. prentice-Hall Englewood Cliffs, 1988. Google ScholarDigital Library
- H.-S. Ko, T. Zan, and Z. Hu. BiGUL: A formally verified core language for putback-based bidirectional programming. In Partial Evaluation and Program Manipulation, pages 61–72. ACM, 2016. Google ScholarDigital Library
- J. Kort and R. Lämmel. Parse-tree annotations meet re-engineering concerns. In International Workshop on Source Code Analysis and Manipulation, pages 161–170. IEEE, 2003.Google Scholar
- P. Martins, J. Saraiva, J. P. Fernandes, and E. Van Wyk. Generating attribute grammar-based bidirectional transformations from rewrite rules. In Partial Evaluation and Program Manipulation, pages 63–70. ACM, 2014. Google ScholarDigital Library
- K. Matsuda and M. Wang. FliPpr: A prettier invertible printing system. In European Symposium on Programming, volume 7792 of Lecture Notes in Computer Science, pages 101–120. Springer, 2013. Google ScholarDigital Library
- U. Norell. Towards a practical programming language based on dependent type theory. PhD thesis, Chalmers University of Technology, 2007.Google Scholar
- H. Pacheco, Z. Hu, and S. Fischer. Monadic combinators for putback style bidirectional programming. In Partial Evaluation and Program Manipulation, pages 39–50. ACM, 2014a. H. Pacheco, T. Zan, and Z. Hu. BiFluX: A bidirectional functional update language for XML. In Principles and Practice of Declarative Programming, pages 147–158. ACM, 2014b. J. Pombrio and S. Krishnamurthi. Resugaring: Lifting evaluation sequences through syntactic sugar. Programming Language Design and Implementation, pages 361–371, 2014. Google ScholarDigital Library
- T. Rendel and K. Ostermann. Invertible syntax descriptions: Unifying parsing and pretty printing. In Haskell Symposium, pages 1–12. ACM, 2010. Google ScholarDigital Library
- T. Sheard and S. P. Jones. Template meta-programming for Haskell. In Haskell Workshop, pages 1–16. ACM, 2002. Google ScholarDigital Library
- E. Visser. Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam, 1997.Google Scholar
- Z. Zhu, H.-S. Ko, P. Martins, J. Saraiva, and Z. Hu. BiYacc: Roll your parser and reflective printer into one. In International Workshop on Bidirectional Transformations, pages 43–50. CEURWS, 2015.Google Scholar
Index Terms
- Parsing and reflective printing, bidirectionally
Recommendations
Unifying Parsing and Reflective Printing for Fully Disambiguated Grammars
AbstractLanguage designers usually need to implement parsers and printers. Despite being two closely related programs, in practice they are often designed separately, and then need to be revised and kept consistent as the language evolves. It will be more ...
Left recursion in Parsing Expression Grammars
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Left recursion in parsing expression grammars
SBLP'12: Proceedings of the 16th Brazilian conference on Programming LanguagesParsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Comments