Tuesday, 6 September 2016

Top Down Parsing and Bottom Up Parsing in NLP (Natural Language Processing)

Top Down Parsing:- This parsing begins with the starting symbol and proceeds by breaking the sentence into its constituents words. It starts with the symbol 'S' and replace it by a sequence of terminal symbol that match the class of words in the input sequence. Thus, in the top down parsing words of the sentence are replaced by their categories replaced by noun phase, verb phase, articles, determiners etc.... These symbols are rewritten as per the grammer rules. Finally the terminal symbols are replaced by language words. This process of parsing keep on continuing until it teach the non terminal symbol.

Example:- Ram went to the park

Production rules:-

  • S--> NP VP
  • NP--> N
  • VP--> V NP
       (OR)

  • S--> NP VP
  • NP--> N/  ARTICLE NP
  • VP--> V / VP PRONOUN
Parsing Algorithum:- To perform the parsing following steps are replaced either till sucessor is obtained or failure is obtained.

  • Select first state from the completeset of possiblities and remove it from the list
  • Genetare the new state by trying every possible options from the related state.
  • Add the state generated in the step to possible list.
Bottom Up Parsing:- In it we start from the non terminal symbols and continuious replacing the sentence with thw sentence with the sentence pharse till reach the root symbol. Bottom-up parsing is reverse parsing of top down parsing.

Example:- Ram went to the park

Production Rules:-

  • NP--> ARTICLE N
  • VP--> N PREPOSITION
  • NP--> VP NP
  • S--> NP VP / N NP  

No comments:

Post a Comment