微信服务号

微信订阅号

2025-5-16- 18
Home > Archive>Volume 16, Issue 2, 2005 >174-183
PDF HTML XML Export Cite reminder
Optimized GLR Parsing for Programming Languages
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [22]
    • |
  • Related [20]
    • |
  • Cited by [1]
    • | |
  • Comments
    Abstract:

    The motivation of adopting the Generalized LR (GLR) parsing algorithm to construct parsers for programming languages is presented. A multi-level strategy for optimizing a GLR parser and the necessary runtime control mechanisms are introduced to the GLR parsers for flexible disambiguation and for invoking semantic actions attached to grammar rules while avoiding the “delayed semantic action” problem. The algorithm has been implemented in VPGE, a visual parser generation environment. Experimental results show that the speed of the generated GLR parsers is comparable to LALR(1) parsers generated by GNU’s Bison when parsing deterministic programming languages.

    Reference
    [1]Tomita M. Efficient Parsing for Natural Language. Boston: Kluwer, 1985.
    [2]Aycock JD. Practical Earley parsing and the SPARK toolkit [Ph.D. Thesis]. Victoria: University of Victoria, 2001.
    [3]McPeak S, Necula G. Elkhound: A GLR parser generator. In: Proc. Of the 13th Int'l Conf. On Compiler Construction. Barcelona: Spring-Verlag, 2004. 51-56.
    [4]Gao ZY, Jin MZ. The Theory and Construction of Compilers. Beijing: Beijing University of Aeronautics and Astronautics Press, 1990. 100-127 (in Chinese).
    [5]Johnson SC. YACC-Yet another compiler-compiler. Technical Report, Rep. CSTR 32, Murray Hill: Bell Laboratories, 1974.
    [6]Donnelly C. Bison: The YACC-compatible parser generator. 1992. Http://www.cs.utah.edu/dept/old/texinfo/bison/bison_toc.html
    [7]Rekers JG. Parser generation for interactive environments [Ph.D. Thesis]. Amsterdam: University of Amsterdam, 1992.
    [8]Irwin W, Churcher N. A generated parser of C++. 2001. Http://citeseer.nj.nec.com/irwin01generated.html
    [9]Corp R, Monica S. RACK: A parser generator for AI languages. In: Proc. Of the 2nd Int'l IEEE Conf. On Tools for Artificial Intelligence. Herndon: IEEE Publisher, 1990. 430-435.
    [10]Robert NM, Michael AA, Kfoury, AJ. An introduction to formal language theory. New York: Springer-Verlag, 1988. 61-75.
    [11]Brand MVD, Sellink A, Verhoed C. Current parsing techniques in software renovation considered harmful. In: Proc. Of the 6th Int'l Workshop on Program Comprehension. Ischia: IEEE Computer Society,1998. 108-117.
    [12]Billot S, Lang B. The structure of shared forest in ambiguous parsing. In: Proc. Of the 27th Annual Meeting of the Association for Computational Linguistics (ACL-89). 1989. 143-151.
    [13]Parr TJ. Obtaining practical variants of LL(k) and LR(k) for k>1 by splitting the atomic k-tuple [Ph.D. Thesis]. West Lafayette: Purdue University, 1993.
    [14]Zhu SH, Zhou M, Liu X, Huang CN. An efficient stochastic context-free parsing algorithm. Journal of Software, 1998,9(8):59-87 (in Chinese with English abstract).
    [15]Weng FL, Zhou B, Wu LD. Process the phenomena of extra grammaticality in NL parsing. Journal of Chinese Information Processing, 1994,8(3):1-13 (in Chinese with English abstract).
    [16]Donnelly C, Stallmen R. The Bison Manual: Using the YACC-Compatible Parser Generator, for Bison Version 1.875. Boston: GNU Press, 2004.
    [17]Aycock J, Horspool N, Janousek J, Melichar B. Even faster generalized LR parsing. Acta Informatica, 2001,37(9):633-651.
    [18]Parr TJ, Quong RW. ANTLR: A predicated-LL(k) parser generator. Software-Practice and Experience, 1995,25(7):789-810.
    [19]Yacc BB. Siber System Corporation. 2004. Http://www.siber.com//btyacc
    [20]高仲仪,金茂忠.编译原理与编译程序构造.北京:北京航空航天大学出版社,1990.
    [21]朱胜火,周明,刘昕,黄昌宁.一种有效的概率上下文无关文法分析算法.软件学报,1998,9(8):59-87.
    [22]翁富良,周斌,吴立德.NL句法分析中超语法符合现象的处理.中文信息学报,1994,8(3):1-13.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李虎,金茂忠,许福,张敏.程序设计语言的GLR优化分析.软件学报,2005,16(2):174-183

Copy
Share
Article Metrics
  • Abstract:5312
  • PDF: 6053
  • HTML: 0
  • Cited by: 0
History
  • Received:July 09,2004
  • Revised:October 10,2004
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044991Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063