# Bottom-up Chart Parsing ![[cfg-english.jpg]] Chart - Stores partial results of parsing in a vecor Edge - representation of a rule application, data structure: [id, left_vtx, right_vtx, mother_category, dtrs] Bottom up parsing process: ![[bottomup-parsing.jpg]] Chart for the above example: ![[parsing-chart.jpg]] Result: Spanning edges are 8 and 11 : Output results for 8 - (S (NP they) (VP (V Can) (VP (V fish) ) ) ) Output results for 11 - (S (NP they) (VP (V Can) (NP fish)) ) ### Final Algorithm **Parse**: - Initialize the chart - For each word *word*, let *from* be left vtx, - *to* right vtx and *dtrs* be (*word*) - For each category *category* - lexically associated with *word* - **Add new edge** *from*, *to*, *category*, *dtrs* - Output results for all spanning edges **Add new edge** *from*, *to*, *category*, *dtrs*: - Put edge in chart: [*id*,*from*,*to*, *category*,*dtrs*] - For each rule $lhs \rightarrow c a t_{1} \ldots c a t_{n-1}, category$ - Find sets of contiguous edges $ \begin{array}{l} {\left[i d_{1}, \text { from }_{1}, t o_{1}, c a t_{1}, d t r s_{1}\right] \ldots} \\ \quad\left[i d_{n-1}, \text { from }_{n-1}, \text { from, cat }_{n-1}, d t r s_{n-1}\right] \end{array} $ (such that $t o_{1}=$ from $_{2}$ etc) - For each set of edges, - **Add new edge** $f r o m_{1}, t o, l h s,\left(i d_{1} \ldots i d\right)$ ### Packing To make parsing more efficient, don't add equivalent edges as whole new edges, make *dtrs* a list of edges instead of a single edge. And do not recurse on it, never need to continue computation with a packable edge. --- ## References 1. Chapter 12, Jurafsky & Martin, 3rd Edition 2. Slides http://www.cs.uccs.edu/~jkalita/work/cs589/2010/12Grammars.pdf 3. Bottom up parsing video: https://www.youtube.com/watch?v=0EDBNIlWgN8