／var／logmarcus chiu

Bottom-Up Chart Parsing

Created on · Last Modified on

Bottom-Up Chart Parsing

Bottom-Up Chart Parsing - Notation

‘•’ means ‘complete to here’

A → X Y•Z (active-arc)

in parsing an A, we’ve so far seen an X and a Y, and our A will be complete once we’ve seen a Z

A → X Y Z• (inactive-arc)

we have seen an X, a Y, and a Z, and hence completed the parse of an A

A → •X Y Z (active-arc)

in parsing an A, so far we haven’t seen anything

Bottom-Up Chart Parsing - Algorithm

Initialize agenda with the list of lexical categories (e.g. PoS) of each word in the input sentence

Until agenda is empty, repeat:

  • move next constituent 𝐶from agenda to completed-arcs section of the chart
  • find grammar rules whose RHS starts with 𝐶and add corresponding active-arcs to the active-arcs section of the chart
  • find active-arcs from the active section that continue with 𝐶and extend them; add the new active-arcs to the active-arcs section of the chart
  • find active-arcs from the active section that have been completed; and add their LHS as a new constituent 𝐶 to the agenda

Bottom-Up Chart Parsing - Example