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.
�. 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)
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
Alfred V A,Ravi S,Jeffrey D U. Compilers: principles,techniques,and tools[M]. Beijing: China Post and Telecommunications Press, 2002
Deremer F, Pennello T. Efficient computation of LALR(1) look-ahead sets[J]. ACMTOPLAS, 1982, 4(4): 615-649
Sippu S.[J].Soisalon-Soininen E. Parsing theory, Vol.II: LR( k ) & LL( k ) parsing[M]. Berlin: Springer-Verlag.1990,:-
Donnelly C, Stallmen R. The Bison manual: using the YACC-compatible parser generator, for Bison version 1.875[M]. Boston: GNU Press, 2004
Manuel Astudillo. GOLD parsing system .2007 . http://www.devincook.com/GOLDParser