Volume 34 Issue 01
Jan.  2008
Turn off MathJax
Article Contents
Li Hu, Yang Xiaojin, Liu Chaoet al. Faster generation of LALR(1) parsers[J]. Journal of Beijing University of Aeronautics and Astronautics, 2008, 34(01): 117-121. (in Chinese)
Citation: Li Hu, Yang Xiaojin, Liu Chaoet al. Faster generation of LALR(1) parsers[J]. Journal of Beijing University of Aeronautics and Astronautics, 2008, 34(01): 117-121. (in Chinese)

Faster generation of LALR(1) parsers

  • Received Date: 15 Jan 2007
  • Publish Date: 31 Jan 2008
  • Deremer & Pennello-s formula for computing LALR(1) lookaheads was studied in practice, by introducing a forward searching method for the computation of lookback and includes relations which were defined in the formula. Efficient algorithms for implementing of the two relations were designed. Several experiments were conducted to show that the computation of LR(0) items closure and searching for a sate in LR(0) state machine are the main bottlenecks of parser generation. Effective and efficient data structures and algorithms for the optimization of these two computations were also proposed. Experimental results show that the speed of LALR(1) parser generation implemented by improved algorithm is even faster than the speed of Bison, a well-known defacto industrial standard of LALR(1) parser generator.

     

  • loading
  • [1] 李虎. GLR分析器自动生成及相关研究 .北京:北京航空航天大学计算机学院, 2006 Li Hu. On GLR parser generation and related issues . Beijing: School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, 2006(in Chinese) [2] Park J C H, Choe K M, Chang C H. A new analysis of LALR formalism[J]. ACM Transactions on Programming Languages and Systems, 1985, 7(1): 159-175 [3] Alfred V A,Ravi S,Jeffrey D U. Compilers: principles,techniques,and tools[M]. Beijing: China Post and Telecommunications Press, 2002 [4] Deremer F, Pennello T. Efficient computation of LALR(1) look-ahead sets[J]. ACMTOPLAS, 1982, 4(4): 615-649 [5] Sippu S, Soisalon-Soininen E. Parsing theory, Vol.II: LR( k ) & LL( k ) parsing[M]. Berlin: Springer-Verlag, 1990 [6] Donnelly C, Stallmen R. The Bison manual: using the YACC-compatible parser generator, for Bison version 1.875[M]. Boston: GNU Press, 2004 [7] Manuel Astudillo. GOLD parsing system .2007 . http://www.devincook.com/GOLDParser
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views(3030) PDF downloads(1734) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return