Animating parsing algorithms

ABSTRACT

The paper describes a package that can be used to present the parsing algorithms. The package fully animates the top-down LL(1) and bottom-up SLR(1) parsing algorithms. By full animation we mean that the input string being parsed, the corresponding actions that take place in the stack, and the building of the parse tree are all simultaneously animated on the same screen, thus enabling the user to get a full appreciation of all the intricate details that occur during parsing. The package makes use of XTANGO and can be used in the beginning of the semester as a teaching tool. Later, the students could be asked to write their own animations of the compiling process.

REFERENCES

• 1: Barwise, J. and Etchemendy, J. Turing's World: A Computer-Based Introduction to Computability Theory. Kinko's Academic Courseware Exchange (Santa Barbara, CA 1986).
• 2: Joe Bergin , Ken Brodie , Marta Patiño-Martínez , Myles McNally , Tom Naps , Susan Rodger , Judith Wilson , Michael Goldweber , Sami Khuri , Ricardo Jiménez-Peris, An overview of visualization: its use and design: report of the working group in visualization, ACM SIGCSE Bulletin, v.28 n.SI, p.192-200, 1996
• 3: Susan H. Rodger , Anna O. Bilska , Kenneth H. Leider , Magdalena Procopiuc , Octavian Procopiuc , Jason R. Salemme , Edwin Tsang, A collection of tools for making automata theory and formal languages come alive, Proceedings of the twenty-eighth SIGCSE technical symposium on Computer science education, p.15-19, February 27-March 01, 1997, San Jose, California, United States
• 4: Stephen A. Blythe , Michael C. James , Susan H. Rodger, LLparse and LRparse: visual and interactive tools for parsing, Proceedings of the twenty-fifth SIGCSE symposium on Computer science education, p.208-212, March 10-12, 1994, Phoenix, Arizona, United States
• 5: Rockford J. Ross , Christopher M. Boroni , Frances W. Goosey , Michael Grinder , Paul Wissenbach, WebLab! A universal and interactive teaching, learning, and laboratory environment for the World Wide Web, Proceedings of the twenty-eighth SIGCSE technical symposium on Computer science education, p.199-203, February 27-March 01, 1997, San Jose, California, United States
• 6: Stephen J. Hartley, Animating operating systems algorithms with XTANGO, Proceedings of the twenty-fifth SIGCSE symposium on Computer science education, p.344-348, March 10-12, 1994, Phoenix, Arizona, United States
• 7: Johnson, S. YACC-yet another compiler-compiler. G5' Technical Report (23, Bell Telephone Laboratories, Murray Hill, NJ, 1975).
• 8: Sami Khuri , Jason Williams, Understanding the bottom-up SLR parser, Proceedings of the twenty-fifth SIGCSE symposium on Computer science education, p.339-343, March 10-12, 1994, Phoenix, Arizona, United States
• 9: Lawrence, A., Badre, A:, and Stasko, J. Empirically Evaluating the Use of Animations to Teach Algorithms Technical Report GIT- G VU- 9~-07 (Georgia Institute of Technology, Atlanta, GA, 1994).
• 10: Harry R. Lewis , Christos H. Papadimitriou , Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 11: Kenneth C. Louden, Compiler Construction: Principles and Practice, PWS Publishing Co., Boston, MA, 1997
• 12: Najork, M. and Brown, M. A library for Visualizing Combinatorial Structures. SRC Research Report (Digital Systems Research Center, Palo Air% CA, September, 1994).
• 13: John T. Stasko, Tango: A Framework and System for Algorithm Animation, Computer, v.23 n.9, p.27-39, September 1990 [doi>10.1109/2.58216]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Animations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Algorithms, Design, Human Factors, Languages, Management, Performance, Theory