Jay Earley
Abstract
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 n3 (where n is the length of the string being parsed) in general; it has an n2 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.
- 1 EARLEY, J. An efficient context-free parsing algorithm. Ph.D. Thesis, Comput. Sei. Dept., Carnegie-Mellon U., Pittsburgh, Pa., 1968. Google Scholar
Digital Library
- 2 KNUTH, D. E. On the translation of languages from left to right. Information and Control 8 (1965), 607-639.Google ScholarCross Ref
- 3 FLOYD, R. W. The syntax of programming languages--a survey. IEEE Trans. EC-13, 4 (Aug. 1964).Google Scholar
- 4 YOUNGER, D. H. Recognition and parsing of context-free languages in time n 3. Information and Control 10 (1967), 189- 208.Google ScholarCross Ref
- 5 HAys, D. Automatic language-data processing. In Computer Applications in the Behavioral Sciences, H. Borko (Ed.) Prentice Hall, Englewood Cliffs, N.J., 1962.Google Scholar
- 6 YOUNGER, D.H. Context-free language processing in time n 3. General Electric R & D Center, Schenectady, N.Y., 1966.Google Scholar
- 7 KASAMI, T., AND TORII, K. A syntax-analysis procedure for unambiguous context-free grammars. J. ACM 16, 3 (July 1969), 423--431. Google ScholarDigital Library
- 8 GRIFFITHS, T., AND PETRICK, S. On the relative efficiencies of context-free grammar recognizers. Comm. ACM 8, 5 (May 1965), 289-300. Google ScholarDigital Library
- 9 FELDMAN, J., AND GRIES, D. Translator writing systems. Comm. ACM 11, 2 (Feb. 1968), 77-113. Google ScholarDigital Library
Recommendations
An efficient context-free parsing algorithm
Special 25th Anniversary IssueA 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 n3 (where n is the length ...
Parsing Arabic using induced probabilistic context free grammar
The importance of the parsing task for NLP applications is well understood. However developing parsers remains difficult because of the complexity of the Arabic language. Most parsers are based on syntactic grammars that describe the syntactic ...
An efficient augmented-context-free parsing algorithm
An efficient parsing algorithm for augmented context-free grammars is introduced, and its application to on-line natural language interfaces discussed. The algorithm is a generalized LR parsing algorithm, which precomputes an LR shift-reduce parsing ...
Comments