Gyung-Ok Lee

10.5626/JOK.2021.48.3.352

LR automata complexity of LR automata LR parsers Parsing Compiler

LR parsing is a representative bottom-up parsing method, and LR automata have been used as the essential frame for the construction of LR parser. This paper defines an equivalence class of classical LR items, which is called Equi-LR class and defines Equi-LR automata by using Equi-LR class instead of classical LR items. This paper shows that Equi-LR automata have the advantage of reduced construction time over classical LR automata, and the size complexity of LR parser in the frame of Equi-LR automata is tighter compared with the frame of classical LR automata.