Pierpaolo Degano
Abstract
A technique for generating parsers which is an extension to LR techniques and is based on parsing table splitting, is presented. Then this technique is slightly extended to support incremental syntax analysis. Given a context-free grammar and a set “IC” of nonterminals devised to be incremental, a set of subtables is generated to drive the analysis of program fragments derivable from nonterminals in IC.
The proposed technique generates parsing tables which are considerably smaller than the standard ones, even when incrementality is not exploited. Thus, these tables may be stored as arrays permitting faster access and accurate error handling. Furthermore, our tables are suitable for generating syntax-directed editors which provide a full analytic mode. The efficiency of the analytic component of a syntax-directed editor obtained in this way and its easy integration with the generative component stress the advantages of incremental program writing.
- 1 AHO, A. V., AND ULMANN, J. D. The Theory of Parsing, Translation and Compiling, Vols. 1 and 2. Prentice-Hall, Englewood Cliffs, N.J., 1972. Google Scholar
- 2 AHO, A. V., AND ULMANN, J.D. Principles of Compiler Design. Prentice-Hall, Englewood Cliffs, N.J., 1977.Google Scholar
- 3 BAHLKE, R., AND SNELTING, G. The PSG system: From formal language definitions to interactive programming environments. ACM Trans. Program. Lang. Syst. 8, 4 (Oct. 1986), 547-576. Google Scholar
- 4 DEREMER, F., AND PENNELLO, T. Efficient computation of LALR(1) look-ahead sets. ACM Trans. Program. Lang. Syst. 4, 4 (Oct. 1982), 613-649. Google Scholar
- 5 DONZEAU-GOUGE, V., HUET, G., KAttN, G., LANG, B., AND LEVY, J.J. A structure-oriented program editor. Tech. Rep. INRIA, Le Chesnay, France, 1975.Google Scholar
- 6 GHEZZI, C., AND MANDRIOLI, D. Augmenting parsers to support incrementality. J. ACM 27, 3 (July 1980), 564-579. Google Scholar
- 7 HANSEN, W. Creation of hierarchic text with a computer display. Ph.D. dissertation, Computer Science Dept., Stanford Univ., Stanford, Calif., June 1971. Google Scholar
- 8 JALILI, F., AND GALLIER, J.H. Building friendly parsers. In Proceedings of 9th Annual ACM Symposium on Principles of Programming Languages (Albuquerque, N.M., Jan. 25-27, 1982). ACM, New York, 1982, pp. 196-206. Google Scholar
- 9 KORENJAK, A.J. A practical method for constructing LR(k) processors. Commun. ACM 12, 11 (Nov. 1969), 613-623. Google Scholar
- 10 MEDINA-MORA, R., AND FEILER, P. An incremental programming environment. IEEE Trans. Softw. Eng. SE-7, 5 (Sept. 1981), 472-482.Google Scholar
- 11 MICHELSON, M., AND WEGMAN, M. $. PDEiL: The PLIL program development environment: Principles of operation. Res. Rep. RC8513, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., Nov. 1980.Google Scholar
- 12 REPS, T., TEITELBAUM, W., AND DEMERS, A. Incremental context-dependent analysis for language-based editors. ACM Trans. Program. Lang. Syst. 5, 3 (July 1983), 439-447. Google Scholar
- 13 TEITELBAUM, T., AND REPS, T. The Cornell program synthesizer: A syntax-directed programming environment. Commun. ACM 24, 9 (Sept. 1981), 563-573. Google Scholar
- 14 WEGMAN, U. $. Parsing for structural editors. In Proceedings of the 21th Annual Symposium on Foundations of Computer Science (1980). IEEE, New York, 1980, pp. 320-327.Google Scholar
- 15 WILCOX, T. R., DAVIS, A. M., AND TINDALL, M. $. The design and implementation of a table driven, interactive diagnostic programming system. Commun. ACM 19, 11 (Nov. 1976), 609-616. Google Scholar
Index Terms
- Efficient incremental LR parsing for syntax-directed editors
Recommendations
Incremental scannerless generalized LR parsing
SPLASH Companion 2019: Proceedings Companion of the 2019 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for HumanityWe present the Incremental Scannerless Generalized LR (ISGLR) parsing algorithm, which combines the benefits of Incremental Generalized LR (IGLR) parsing and Scannerless Generalized LR (SGLR) parsing. The parser preprocesses the input by modifying the ...
LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...
Parsing extended LR(k) grammars
An extended LR(k) (ELR(k)) grammar is a context free grammar in which the right sides of the productions are regular expressions and which can be parsed from left to right with k symbol look-ahead. We present a practical algorithm for producing small ...
Comments