PARSING

Process of analyzing a string of symbols either in natural language or in computer languages according to the rules of a formal grammar.

Since,     

Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually designed grammars for programming languages.

As some grammar formalisms are very difficult to parse computationally.

So, this problem is solved by "Parser" which uses algorithms like-CKY algorithm , shift-reduce algorithm etc.

A parser is one of the components in an interpreter or compiler that checks for correct syntax and builds a data structure. It parses the source code of a computer programming language to create some form of internal representation.

Types of parser :

Top-down parsers : Tokens are consumed from left to right in this type of Parsing.

                               Eg- LL parsers and recursive-descent parser

Bottom-up parsers : This type of parser is Shift-Reduce Parsing.

                               Eg-LR parsers , LALR parser , Canonical LR  parser , GLR parser

Parser development software : ANTLR , Bison , Coco/R , GOLD , JavaCC , Lemon , Parboiled , ParseIT , Ragel , SHProto (FSM parser language) , Spirit Parser Framework , Syntax Definition Formalism , SYNTAX , VisualLangLab , XPL , Yacc