Stephen A. Blythe
Susan H. Rodger
Abstract
This paper describes instructional tools, LLparse and LRparse, for visualizing and interacting with small examples of LL and LR parsing. These tools can be used to understand the process of constructing LL(1) and LR(1) parse tables through a series of steps in which users receive feedback on the correctness of each step before moving on to the next step. For example, in LRparse, the user initially enters an LR(1) grammar, calculates FIRST and FOLLOW sets, graphically constructs a deterministic finite automaton of item sets, and finally constructs the LR(1) parsing table. Upon completion of the constructed table, the user can observe a visualization of the parsing of input strings. These tools can be used to provide problem solving feedback in courses on automata theory or compiler design.
- 1 A. Aho, R. Sethi and J. Ullman, Compilers: Princzples, Techniques, and Tools, Addison-Wesley, 1986. Google Scholar
Digital Library
- 2 A. Aho and J. Ullman, Foundations of Computer Science, Computer Science Press, 1992. Google ScholarDigital Library
- 3 J. Barwise and J. Etchemendy, Turing's World, Kinko's Academic Courseware Exchange, Santa Barbara~ CA~ 1986.Google Scholar
- 4 S. Blythe, LLparse and Lttparse" Interactive LL(1) and LR(1) Parsing Tutorials, Master's Project, Rensselaer Polytechnic institute, May 1993.Google Scholar
- 5 M. James, A Software Tool to Aid in Understanding LL Parsing, Master's Project, Rensselaer Polytechnic institute, September 1992.Google Scholar
- 6 D. Hannay, Hypercard Automata Simulation: Finite State, Pushdown and Turing Machines, SIGCSE Bulletin, 24, 2, p. 55-58, June 1992. Google ScholarDigital Library
- 7 M. C. Lee, An Abstract Machine Simulator, Third Inlernational Conference on Computer Assisted Learmng, p. 129-141, 1990. Google ScholarDigital Library
- 8 H. Lewis, and C. Papadimitriou, Elements of ~he Theory of Compulation, Prentice-Hall~ 1981. Google ScholarDigital Library
- 9 P. Linz, An Introduction to Formal Languages and A uloma~a, D. C. Heath and Company, 1990. Google ScholarDigital Library
- 10 M. LoSacco, and S. H. ttodger, FLAP:: A Tool for Drawing and Simulating Automata, ED-MEDIA 93, p. 310-317, June 1993.Google Scholar
- 11 K. Sutner, Implementing Finite State Machines, DIMA CS Workshop on Computational Support for Discrele Malhemalics, 1992.Google Scholar
Index Terms
- LLparse and LRparse: visual and interactive tools for parsing
Recommendations
LLparse and LRparse: visual and interactive tools for parsing
SIGCSE '94: Proceedings of the twenty-fifth SIGCSE symposium on Computer science educationThis paper describes instructional tools, LLparse and LRparse, for visualizing and interacting with small examples of LL and LR parsing. These tools can be used to understand the process of constructing LL(1) and LR(1) parse tables through a series of ...
LLLR parsing
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied ComputingThe idea of an LLLR parsing is presented. An LLLR(k) parser can be constructed for any LR(k) grammar but it produces the left parse of the input string in linear time (in respect to the length of the derivation) without backtracking. If used as a basis ...
Comments