際際滷

際際滷Share a Scribd company logo

Bottom up parsing

D
Dr. ABHISHEK K PANDEY

The document discusses parsing trees for natural language. It notes that parsing approaches can be either top-down, where only trees consistent with start symbols are considered, or bottom-up, where only trees consistent with input words are formed. A bottom-up approach considers smaller constituents first and combines them, while a top-down approach expands nodes from the start symbol. Exhaustive search is infeasible due to exponential time complexity, but dynamic programming approaches like CKY and Earley parse more efficiently by reusing results.

1 of 6
Prof.Neeraj Bhargava Abhishek Kumar Department of Computer Science School of Engineering & System Sciences, MDS, University Ajmer, Rajasthan, India 1
We also want trees that cover the input words. Start with trees that link up with the words Then work your way up from there to larger and larger trees. 2
3
Top-down Only searches for trees that can be Ss But also suggests trees that are not consistent with any of the words Bottom-up Only forms trees consistent with the words But suggests trees that make no sense globally 4
Which node to try to expand next Which grammar rule to use to expand a node One approach: exhaustive search of the space of possibilities Not feasible Time is exponential in the number of non- terminals LOTS of repeated work, as the same constituent is created over and over (shared sub-problems) 5
DP search methods fill tables with partial results and thereby Avoid doing avoidable repeated work Solve exponential problems in polynomial time (well, no not really well return to this point) Efficiently store ambiguous structures with shared sub-parts. Well cover two approaches that roughly correspond to bottom-up and top-down approaches. CKY Earley we will mention this, not cover it in detail 6

More Related Content

Bottom up parsing

  • 1. Prof.Neeraj Bhargava Abhishek Kumar Department of Computer Science School of Engineering & System Sciences, MDS, University Ajmer, Rajasthan, India 1
  • 2. We also want trees that cover the input words. Start with trees that link up with the words Then work your way up from there to larger and larger trees. 2
  • 3. 3
  • 4. Top-down Only searches for trees that can be Ss But also suggests trees that are not consistent with any of the words Bottom-up Only forms trees consistent with the words But suggests trees that make no sense globally 4
  • 5. Which node to try to expand next Which grammar rule to use to expand a node One approach: exhaustive search of the space of possibilities Not feasible Time is exponential in the number of non- terminals LOTS of repeated work, as the same constituent is created over and over (shared sub-problems) 5
  • 6. DP search methods fill tables with partial results and thereby Avoid doing avoidable repeated work Solve exponential problems in polynomial time (well, no not really well return to this point) Efficiently store ambiguous structures with shared sub-parts. Well cover two approaches that roughly correspond to bottom-up and top-down approaches. CKY Earley we will mention this, not cover it in detail 6