BiYacc

Roll Your Parser and Reflective Printer into One

Abstract

Language 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 convenient if the parser and printer can be unified and developed in a 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 a fully disambiguated context- free grammar. BiYacc is based on the theory of bidirectional transformations, which helps to guarantee by construction that the generated pairs of parsers and reflective printers are consistent. For handling grammatic ambiguity, we adopt generalised parsing and disambiguation filters, which produce all the parse results and (try to) select the only correct one in the parsing direction; the filters are carefully bidirectionalised so that they also work in the printing direction and will not break the consistency between the parsers and reflective printers. We show that BiYacc is capable of facilitating many tasks such as Pombrio and Krishnamurthi’s ‘resugaring’, simple refactoring, and language evolution.

Test Cases
We have tested our system with some examples. Please try them online.
A few notes:
  • Please leave the source empty if you want a traditional printer, however, it will produce ugly results as for current BiYacc.
  • The compilation takes half a minute for the Tiger example.
    (The most time consuming part is the compilation of the parser generated by Happy.)
  • The warning and error messages produced from Happy may not be gathered and shown in this webGUI.
  • The server will do cleaning every hour. Your compiled program may be deleted at that time.
  • The structure of a BiYacc program is: abstract syntax (defined by Haskell data types), concrete syntax (defined by production rules, directives (possibly), and actions (updating strategies).
    BiYacc program
  • Compilation

    Please click the compile button. The compilation may take up to half a minute. (especially for big examples such as Tiger)
    If the code is compiled successfully, boxes showing source, view and log will be shown.
    If not, the error message will be shown in a console.


Source
Installation and Use Guide

Please install GHC (The Glasgow Haskell Compiler), BiGUL, and BiYacc in order.
After installation you may use BiYacc in your command line: "biyacc biyaccProgramName outputExecutableName".
After the executable is generated, run the executable in the terminal and you will get tips.
Download and read the README file for more details.
Team Members

PhD student, SOKENDAI (The Graduate University for Advanced Studies)

PhD student, SOKENDAI (The Graduate University for Advanced Studies)

Assistant Professor by Special Appointment, National Institute of Informatics

Assistant Project Scientist, University of California - Irvine

Associate Professor, University of Minho

Professor, National Institute of Informatics

Acknowledgments

We thank Tao Zan for the template of this website.