Chirp on crickets: teaching compilers using an embedded robot controller

ABSTRACT

Traditionally, the topics of compiler construction and language processing have been taught as an elective course in Computer Science curricula. As such, students may graduate with little understanding or experience with the useful techniques embodied in modern compiler construction.In this paper, we present the design of Chirp, a language specification and compiler implementation. As a language, Chirp is based on Java/C syntax conventions and is matched with the stack-based virtual machine that is built into the simple yet versatile Handy Cricket educational robot controller. As a compiler, the Chirp design is a series of Java components. These modules demonstrate key compiler construction techniques including lexing, parsing, intermediate representation, semantic analysis, error handling and code generation.We have designed a 6-week teaching module to be integrated into an intermediate-level undergraduate programming class. In the module, students will incrementally build the Chirp compiler, culminating with code generation for the Cricket controller. They will test their work on both physical Cricket-based robots and a web-based Cricket simulator. The Chirp system and our pedagogical design provides a realistic and engaging environment to teach compilers in undergraduate core programming courses.

REFERENCES

• 1: ACM Computing Curricula 2001, Computer Science volume. http://www.sigcse.org/cc2001/.
• 2: ANTLR documentation. http://www.antlr.org/doc.
• 3: William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968 [doi>10.1145/362929.362976]
• 4: Richard H. Austing , Bruce H. Barnes , Della T. Bonnette , Gerald L. Engel , Gordon Stokes, Curriculum '78: recommendations for the undergraduate program in computer science— a report of the ACM curriculum committee on computer science, Communications of the ACM, v.22 n.3, p.147-166, March 1979 [doi>10.1145/359080.359083]
• 5: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 6: K. Andrews , R. R. Henry , W. K. Yamamoto, Design and implementation of the UW Illustrated compiler, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.105-114, June 20-24, 1988, Atlanta, Georgia, United States
• 7: K. D. Cooper and L. Torczon. Engineering a Compiler. Morgan Kaufmann, 2003.
• 8: Saumya Debray, Making compiler design relevant for students who will (most likely) never design a compiler, Proceedings of the 33rd SIGCSE technical symposium on Computer science education, February 27-March 03, 2002, Cincinnati, Kentucky
• 9: Tyson R. Henry, Teaching compiler construction using a domain specific language, Proceedings of the 36th SIGCSE technical symposium on Computer science education, February 23-27, 2005, St. Louis, Missouri, USA
• 10: Fred Martin , Bakhtiar Mikhak , Mitchel Resnick , Brian Silverman , Robbie Berg, To mindstorms and beyond: evolution of a construction kit for magical machines, Robots for kids: exploring new technologies for learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 11: F. Martin , B. Mikhak , B. Silverman, MetaCricket: a designer's kit for making computational devices, IBM Systems Journal, v.39 n.3-4, p.795-815, July 2000
• 12: F. G. Martin and S. Kuhn. Computing in context: Integrating an embedded computing project into a course on ethical and societal issues. in press, 2006.
• 13: F. G. Martin, N. Palmer, and B. Skinner. The virtual cricket: A web-based simulator for learning robot programming. In preparation.
• 14: Dung Zung Nguyen , Mathias Ricken , Stephen Wong, Design patterns for parsing, Proceedings of the 36th SIGCSE technical symposium on Computer science education, February 23-27, 2005, St. Louis, Missouri, USA
• 15: M. Resnick, R. Berg, and M. Eisenberg. Beyond black boxes: Bringing transparency and aesthetics back to scientific investigation. Journal of the Learning Sciences, 9(1):7--30, 2000.
• 16: L. Xu and F. Martin. The chirp language specification. Technical Report TR-2005-003, Dept. of Computer Science, UMass Lowell.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Languages

Keywords:
compiler construction, educational robotics, embedded processor, language processing, virtual machine