標題: Extended LALR(1) Parsing
作者: Yang, Wuu
資訊工程學系
Department of Computer Science
關鍵字: context-free grammar;grammar;extended LALR parser;LR parser;LALR parser;parsing
公開日期: 1-一月-2017
摘要: We identify a class of context-free grammars, called the extended LALR(1) (ELALR(1)), which is a superclass of LALR(1) and a subclass of LR(1). Our algorithm is essentially a smarter method for merging similar states in the LR(1) state machines. LALR(1) would merge every pair of similar states. In contrast, our algorithm merges a pair of similar states only if no (reduce-reduce) conflicts will be created. Thus, when no conflicts occur, our algorithm produces exactly the same state machines as the LALR(1) algorithm. However, when the LALR(1) algorithm reports conflicts, our algorithm may still produce a (larger) conflict-free state machine. In the extreme case when no states can be merged, our algorithm simply returns the original LR(1) machines. An important characteristic of the ELALR(1) algorithm is that there is no backtracking. On the other hand, the ELALR(1) algorithm does not guarantee the minimum state machines.
URI: http://hdl.handle.net/11536/147224
期刊: THIRTEENTH INTERNATIONAL CONFERENCE ON AUTONOMIC AND AUTONOMOUS SYSTEMS (ICAS 2017)
起始頁: 30
結束頁: 35
顯示於類別:會議論文