An efficient context-free parsing algorithm

Communications of the ACM - Tập 13 Số 2 - Trang 94-102 - 1970
Jay Earley1
1Univ. of California, Berkeley

Tóm tắt

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR( k ) algorithm and the familiar top-down algorithm. It has a time bound proportional to n 3 (where n is the length of the string being parsed) in general; it has an n 2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

Từ khóa


Tài liệu tham khảo

10.1016/S0019-9958(65)90426-2

FLOYD , R. W . The syntax of programming languages--a survey . IEEE Trans. EC-13 , 4 ( Aug. 1964 ). FLOYD, R. W. The syntax of programming languages--a survey. IEEE Trans. EC-13, 4 (Aug. 1964).

10.1016/S0019-9958(67)80007-X

HA ys, D. Automatic language-data processing . In Computer Applications in the Behavioral Sciences , H. Borko (Ed.) Prentice Hall , Englewood Cliffs, N.J. , 1962 . HAys, D. Automatic language-data processing. In Computer Applications in the Behavioral Sciences, H. Borko (Ed.) Prentice Hall, Englewood Cliffs, N.J., 1962.

YOUNGER , D.H. Context-free language processing in time n 3. General Electric R &amp ; D Center , Schenectady, N.Y. , 1966 . YOUNGER, D.H. Context-free language processing in time n 3. General Electric R & D Center, Schenectady, N.Y., 1966.

10.1145/321526.321531

10.1145/364914.364943

10.1145/362896.362902

Thông tin
Thông tin xuất bản

Communications of the ACM

Tập 13 Số 2

94-102

Thông tin tác giả