Volume 13 / Number 2 / February, 1970 | JAY EARLEY
The paper presents an efficient context-free parsing algorithm, which is similar to both Knuth's LR(k) algorithm and the top-down algorithm. The algorithm has a time complexity of \( n^3 \) in general, \( n^2 \) for unambiguous grammars, and linear time for a large class of grammars, including most practical context-free programming language grammars. The author provides a formal investigation and empirical comparison to demonstrate the algorithm's efficiency. The algorithm uses state sets and look-ahead features to process input strings, with operations like predictor, scanner, and completer to handle nonterminals and terminals. The paper also discusses the implementation details, time and space bounds, and practical applications of the algorithm, emphasizing its versatility and efficiency compared to other parsing algorithms.The paper presents an efficient context-free parsing algorithm, which is similar to both Knuth's LR(k) algorithm and the top-down algorithm. The algorithm has a time complexity of \( n^3 \) in general, \( n^2 \) for unambiguous grammars, and linear time for a large class of grammars, including most practical context-free programming language grammars. The author provides a formal investigation and empirical comparison to demonstrate the algorithm's efficiency. The algorithm uses state sets and look-ahead features to process input strings, with operations like predictor, scanner, and completer to handle nonterminals and terminals. The paper also discusses the implementation details, time and space bounds, and practical applications of the algorithm, emphasizing its versatility and efficiency compared to other parsing algorithms.