A PARSING METHOD FOR CONTEXT-FREE LANGUAGES USING BOTTOM-UP LOOKAHEADCOMPUTATION

Authors
WATANABE Y TOKUDA T
Citation
Y. Watanabe et T. Tokuda, A PARSING METHOD FOR CONTEXT-FREE LANGUAGES USING BOTTOM-UP LOOKAHEADCOMPUTATION, Systems and computers in Japan, 27(10), 1996, pp. 14-22
Citations number
7
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Information Systems","Computer Science Theory & Methods
Journal title
Systems and computers in Japan → ACNP
ISSN journal
08821666
Volume
27
Issue
10
Year of publication
1996
Pages
14 - 22
Database
ISI
SICI code
0882-1666(1996)27:10<14:APMFCL>2.0.ZU;2-M
Abstract
A new parsing algorithm of context-free languages using bottom-up comp utation of lookahead information is presented. Earley's algorithm uses a great number of items during enumeration to recognize a context-fre e language. If items with lookahead fields are used, the number of ite ms can be reduced, but item spacing is considerably increased. The met hod presented here may reduce the number of items during enumeration w ithout using lookahead fields of items. The computation of lookahead i nformation takes place in a bottom-up manner, It is not necessary to c ompute lookahead information until it is required during enumeration.