標題: | 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 |
顯示於類別: | 會議論文 |