GLC: Generalized left-corner parsing

Left-corner (LC) parsing more specifically, left-corner parsing with top-down filtering originated as a method for deterministically parsing a restricted class of CFGs. It is often attributed to Rosenkrantz and Lewis (1970), who may have first used the term “left-corner parsing” in print. Griffiths and Petrick (1965), however, previously described an LC parsing algorithm under the name “selective bottom-to-top”(SBT) parsing, which they assert to be an abstraction of previously described algorithms.

The origins of LC parsing for general CFGs (other than by naive backtracking) are even murkier. Pratt’s (1975) algorithm is sometimes considered to be a generalized LC method, but it is perhaps better described as CKY parsing with top-down filtering added. Kay’s (1980) method for undirected bottom-up chart parsing is clearly left-corner parsing without top-down filtering, but in adding top-down filtering to obtain directed bottom-up chart parsing, he changed the method signicantly. The BUP parser of Matsumoto et al. (1983) appears to be the first clearly described LC parser capable of parsing general CFGs in polynomial time.

— Improved Left-Corner Chart Parsing for Large Context-Free Grammars, 2004 ↗