A parsing method for context‐free languages using bottom‐up lookahead computation
Yoshimichi Watanabe, Takehiro Tokuda · Systems and Computers in Japan · 1996
Abstract A new parsing algorithm of context‐free languages using bottom‐up computation of lookahead information is presented. Earley's algorithm uses a great number of items during enumeration to recognize a context‐free language. If items with lookahead fields are used, the number of items can be reduced, but item spacing is considerably increased. The method presented here may reduce the number of items during enumeration without using lookahead fields of items. The computation of lookahead information takes place in a bottom‐up manner. It is not necessary to compute lookahead information until it is required during enumeration.