Abstract
The parser construction method presented here might be characterized as the offspring of the successful marriage of LR(k) methodology [4] with the transition diagram systems of Conway [2]. Like transition diagram systems, the parsers constructed by the method presented here, called the LLP(k) method, consist of small, finite state automata linked by “subroutine calls” and provide a mixed top-down/bottom-up parse. Transition diagram systems with one exit state per diagram correspond to top-down parsers and have been extensively studied [6,9,10]. Like Conway’s transition diagrams, however, LLP(k) subroutines can parse multiple non-terminals simultaneously and return an indication of what they have discovered. It has been shown [7] that transition diagram systems composed of such multiple exit diagrams can parse all deterministic context free languages. Further, LLP(k) parsers can be realized as directly executing (non-interpretive) subroutines. The method has been implemented [8]. The results demonstrate the feasibility of the approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backes, S., Top-down syntax analysis and Floyd-Evans production language. Information Processing 71, 504–517.
Conway, M. E., Design of a separable transition-diagram compiler. Comm. ACM 6, 7 (July 1963), 396–408.
DeRemer, F. L., Simple LR(k) grammars. Comm. ACM 14, 7 (July 1971), 453–460.
Knuth, D. E., On the translation of languages from left to right. Inform. Cont. 8 (Oct. 1965), 607–639.
Korenjak, A. J., A practical method for constructing LR(k) processors. Comm. ACM 12, 11 (Nov. 1969), 613–623.
Lewis, P. M. and Stearns, R. E., Syntax-directed transductions. J. ACM 15, 3 (July 1968) 465–488.
Lomet, D. B., A formalization of transition systems.. J. ACM 20, 2 (April 1973), 235–257.
Lomet, D. B., The construction of efficient deterministic language processors. Ph.d. diss., University of Pennsylvania, Philadelphia, Pa., December, 1969 and IBM Research Report RC 2738, January, 1970.
Rosenkrantz, D. J. and Stearns, R. E., Properties of deterministic top-down grammars. ACM Symposium on theory of computing, Marina del Rey, California, May 1969, 165–180.
Tixier, V., Recursive functions of regular expressions in language analysis. Tech. Rep. CS-58, Computer Science Department, Stanford University, Stanford, California, March, 1967.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1974 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lomet, D.B. (1974). Automatic Generation of Multiple Exit Parsing Subroutines. In: Loeckx, J. (eds) Automata, Languages and Programming. ICALP 1974. Lecture Notes in Computer Science, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-21545-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-662-21545-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-06841-9
Online ISBN: 978-3-662-21545-6
eBook Packages: Springer Book Archive