What is Parsing and Types of parsing?

Parsing:

The process of converting a sentence into a tree that represents a sentence’s syntactic structure is known as Parsing.

Example: “The white dog crossed the road“. Its parse tree is given below:

In figure shows how a sentence is made up of a noun phrase and a verb phrase. The noun phrase consists of an article, an adjective and a noun. The verb phrase consists of a verb and a noun phrase, in turn, consists of an article and a noun. Parsing is thus a typical AI search problem in which –
i. The initial state is an input sequence of words.
ii. The goal state is a complete tree representing the whole sentence structure.
iii. The production rules are grammar rules.
iv. The parser can be viewed as searching through the space of all possible parse trees to find the correct parse tree for the sentence in consideration.

Types of Parsing:

There are two types of parsing –
i. Top-down Parsing
ii. Bottom-up Parsing

Top-down Parsing:

Building a parse tree from the top-down involves starting from a sentence and determining which of the possible rewriters for a sentence can be applied to the sentence that is being parsed. Hence, in this passing the sentence would be rewritten using the following rule:

Sentence-> Noun phrase, Verb phrase

Bottom-up Parsing:

To build a parse tree from the bottom-up, the terminal symbol of the sentence is first replaced by its corresponding non-terminals and then these non-terminals are combined to match the right-hand sides of rewrite rules.
NounPhrase-> Article, Noun