# 1970 AnEfficientCFParsingAlgorithm

- (Earley, 1970) ⇒ Jay Earley. (1970). “An Efficient Context-Free Parsing Algorithm.” In: Communications of the ACM, 13(2). doi:10.1145/362007.362035

**Subject Headings:** Earley Parser.

## Notes

## Quotes

### 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.
- A recognizer is an algorithm which takes as input a string and either accepts or rejects it depending on whether or not the string is a sentence of ...,

Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|

1970 AnEfficientCFParsingAlgorithm | Jay Earley | An Efficient Context-Free Parsing Algorithm | Communications of the ACM | http://www.cs.cmu.edu/afs/cs/user/alavie/11-711/711-cmt/Class-notes/p94-earley.pdf | 10.1145/362007.362035 | 1970 |

Facts about "1970 AnEfficientCFParsingAlgorithm"

Author | Jay Earley + |

doi | 10.1145/362007.362035 + |

journal | Communications of the ACM + |

title | An Efficient Context-Free Parsing Algorithm + |

titleUrl | http://www.cs.cmu.edu/afs/cs/user/alavie/11-711/711-cmt/Class-notes/p94-earley.pdf + |

year | 1970 + |