Parsing-with-Context-Free-Grammars- Notes | EduRev

: Parsing-with-Context-Free-Grammars- Notes | EduRev

 Page 1


Parsing with  
Context Free Grammars 
 
Reading: Chap 13, Jurafsky & Martin 
 
This slide set was adapted from J. Martin, U. Colorado 
Instructor: Rada Mihalcea 
Page 2


Parsing with  
Context Free Grammars 
 
Reading: Chap 13, Jurafsky & Martin 
 
This slide set was adapted from J. Martin, U. Colorado 
Instructor: Rada Mihalcea 
Slide 1 
Parsing 
• Parsing with CFGs refers to the task of assigning correct trees to 
input strings 
• Correct here means a tree that covers all and only the elements of the 
input and has an S at the top 
• It doesn’t actually mean that the system can select the correct tree 
from among the possible trees 
 
• As with everything of interest, parsing involves a search that involves 
the making of choices 
 
Page 3


Parsing with  
Context Free Grammars 
 
Reading: Chap 13, Jurafsky & Martin 
 
This slide set was adapted from J. Martin, U. Colorado 
Instructor: Rada Mihalcea 
Slide 1 
Parsing 
• Parsing with CFGs refers to the task of assigning correct trees to 
input strings 
• Correct here means a tree that covers all and only the elements of the 
input and has an S at the top 
• It doesn’t actually mean that the system can select the correct tree 
from among the possible trees 
 
• As with everything of interest, parsing involves a search that involves 
the making of choices 
 
Slide 1 
Some assumptions.. 
• Assume… 
– You have all the words already in some buffer 
– The input is/isn’t pos tagged 
– All the words are known 
• These are all (quite) feasible 
– State-of-the art in POS tagging? 
– “all words are known” ? 
Page 4


Parsing with  
Context Free Grammars 
 
Reading: Chap 13, Jurafsky & Martin 
 
This slide set was adapted from J. Martin, U. Colorado 
Instructor: Rada Mihalcea 
Slide 1 
Parsing 
• Parsing with CFGs refers to the task of assigning correct trees to 
input strings 
• Correct here means a tree that covers all and only the elements of the 
input and has an S at the top 
• It doesn’t actually mean that the system can select the correct tree 
from among the possible trees 
 
• As with everything of interest, parsing involves a search that involves 
the making of choices 
 
Slide 1 
Some assumptions.. 
• Assume… 
– You have all the words already in some buffer 
– The input is/isn’t pos tagged 
– All the words are known 
• These are all (quite) feasible 
– State-of-the art in POS tagging? 
– “all words are known” ? 
Slide 1 
Top-Down Parsing 
• Since we are trying to find trees rooted with an S (Sentences) start 
with the rules that give us an S. 
 
• Then work your way down from there to the words. 
Page 5


Parsing with  
Context Free Grammars 
 
Reading: Chap 13, Jurafsky & Martin 
 
This slide set was adapted from J. Martin, U. Colorado 
Instructor: Rada Mihalcea 
Slide 1 
Parsing 
• Parsing with CFGs refers to the task of assigning correct trees to 
input strings 
• Correct here means a tree that covers all and only the elements of the 
input and has an S at the top 
• It doesn’t actually mean that the system can select the correct tree 
from among the possible trees 
 
• As with everything of interest, parsing involves a search that involves 
the making of choices 
 
Slide 1 
Some assumptions.. 
• Assume… 
– You have all the words already in some buffer 
– The input is/isn’t pos tagged 
– All the words are known 
• These are all (quite) feasible 
– State-of-the art in POS tagging? 
– “all words are known” ? 
Slide 1 
Top-Down Parsing 
• Since we are trying to find trees rooted with an S (Sentences) start 
with the rules that give us an S. 
 
• Then work your way down from there to the words. 
Slide 1 
Top Down Space 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!