Revision Notes

These are lecture notes from my Computer Science course.


  • Chart parsers are better than backtracking parsers because they are more efficient. This is because in a backtracking parser partial successful parses are thrown away, and so have to be parsed again. A chart parser maintains all sub-parses.

Active Chart Parsers

(This is from memory so is probably wrong).

You have both top-down and bottom-up chart parsers, and they do things slightly differently. By using a chart (as in, storing partial parsings) a top-down parser can handle left-recursive rules.

A top-down parser initialises the chart with all S rules at (0,0), then will try to predict active edges from these new active edges.

A bottom-up parser first initialises the chart with all the lexical entries. Then starting from the left it adds rules at (0,0) that will potentially match the first lexical entry. It will do this for each vertex n, adding rules for (n,n). I think.

This entry was posted in lecture, nlp. Bookmark the permalink.