標題: Locating free positions in LR(k) grammars
作者: Ouyang, ST
Wu, PC
Wang, FJ
資訊工程學系
Department of Computer Science
關鍵字: parser generators;LR(k) grammars;semantic actions;parse tree;free positions
公開日期: 1-May-2002
摘要: 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.
URI: http://hdl.handle.net/11536/28847
ISSN: 1016-2364
期刊: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 18
Issue: 3
起始頁: 411
結束頁: 423
Appears in Collections:Articles


Files in This Item:

  1. 000176175900006.pdf