Ouyang, S.-T., Wu, P.-C., Wang, F.-J., "Locating Free Positions in LR(k) Grammars," Journal of Information Science and Engineering, Vol. 18, No. 3, May 2002, pp.411-423. (SCI Expanded, EI)

論文題目: LR(k)文法中自由位置的定位

Abstract

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.

Key Words: parser generators, LR(k) grammars, semantic actions, parse tree, free positions.

摘要

       LR(k)是線性時間剖析最廣義的文法類別。LR剖析中,在識別一個符號之前,執行該符號相關的語意動作是極困難的。將語意動作加入LR(k)文法可能導致其成為非LR(k)文法。實務上有二種直截了當的做法。第一種做法是延遲所有語意動作,直到建立完整的剖析樹。第二種做法是隨意將語意動作加入文法中。本文提出一快速的方法找出LR(k)文法中可以自由放置語意動作的位置(稱為自由位置)。我們的方法在八個測試文法中,速度上的增益從15.502.23倍。

關鍵詞:剖析器產生器、LR(k)文法、語意動作、剖析樹、自由位置。