In the previous segment, you studied the top-down parser and the problem of left-recursion. In this segment, you’ll learn another approach to parse a sentence- the bottom-up approach.
To summarise, the bottom-up approach reduces each terminal word to a production rule, i.e. reduces the right-hand-side of the grammar to the left-hand-side. It continues the reduction process until the entire sentence has been reduced to the start symbol S.
There are many types of bottom-up parsers. The shift-reduce parser is one of the most commonly used bottom-up parsing algorithm. Let’s consider the following sentence and grammar:
Sentence: The angry bear chased the squirrel
Grammar
In the following lecture, Prof. Srinath will explain how bottom-up parsing is done using the shift-reduce algorithm. As an example, we will take the sentence “The angry bear chased the squirrel” and use some production rules to implement the shift-reduce algorithm.
To summarise, the shift-reduce parser parses the words of the sentence one-by-one either by shifting a word to the stack or reducing the stack by using the production rules.
In the next lecture, you will see the Python implementation of the shift-reduce parser. The following Jupyter notebook is attached for your reference.
Ambiguities in Parse Trees
In one of the questions above, you saw that the sentence “The man caught fish with a net” can have two valid parses. In one parse, the prepositional phrase “with a net” is associated with “The man” whereas in another parse it is associated with “fish”.
Now, from common sense, you know that the phrase “with a net” is associated with “The man”, i.e. it is the man who has the net, not the fish. But how do you make the algorithm use this common sense?
Well, your common sense arises from the fact that it is more likely that the man has the net, not the fish. As always, the way to make algorithms understand the concept of likelihood is to use probabilistic techniques.
In the next segment, you will learn probabilistic context-free grammars or PCFGs.