Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.18 No.3, pp.411-423 (May 2002)

Locating Free Positions in LR(k) Grammars*

Shih-Ting Ouyang, Pei-Chi Wu+ and Feng-Jian Wang++
Sunplus Technology Co., Ltd.
Hsinchu, 300 Taiwan
E-mail: tim_ouyang@sunplus.com.tw
+Department of Computer Science and Information Engineering
National Penghu Institute of Technology
Penghu, 880 Taiwan
E-mail: pcwu@npit.edu.tw
++Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, 300 Taiwan
E-mail: fjwang@csie.nctu.edu.tw

LR(k) is the most general category of linear-time parsing. Before a symbol is recognized in LR parsing, it is difficult to invoke the semantic action associated with the symbol. Adding semantic actions to an LR(k) grammar may result in a non-LR(k) grammar. There are two straightforward approaches adopted by practitioners of parser generators. The first approach is to delay all semantic actions until the whole parse tree is constructed. The second is to add semantic actions to the grammar by chance. This paper presents an efficient algorithm for finding positions (called free positions) that can freely put semantic actions into an LR(k) grammar. The speedups of our method range from 2.23 to 15.50 times for the eight tested grammars.

Keywords: parser generators, LR(k) grammars, semantic actions, parse tree, free positions

Full Text () Retrieve PDF document (200205_06.pdf)

Received June 30, 2000; revised February 15, 2001; accepted May 18, 2001.
Communicated by Jang-Ping Sheu
* This research was partly supported by National Science Council, Taiwan, R.O.C., under Contract No. NSC 89-2213-E-346-002.