for examplegiven sentence in the english languagesuch as "the dog barked"we might transform the sentence into sequence of (part-of-speechword -tuples((definite_article"the")(noun"dog")(verb"barked")we would then perform syntactic analysis to see if this is valid english sentence in this case it isbut our parser would have to rejectsay"the barked dogthe lexing phase is used to convert the data into stream of tokens in typical caseseach token holds at least two pieces of informationthe token' type (the kind of data or language construct being represented)and the token' value (which may be empty if the type stands for itself--for examplea keyword in programming languagethe parsing phase is where parser reads each token and performs some semantic action the parser operates according to predefined set of grammar rules that define the syntax that the data is expected to follow (if the data doesn' follow the syntax rules the parser will correctly fail in multiphase parsersthe semantic action consists of building up an internal representation of the input in memory (called an abstract syntax tree--ast)which serves as input to the next phase once the ast has been constructedit can be traversedfor exampleto query the dataor to write the data out in different formator to perform computations that correspond to the meanings encoded in the data data formats and dsls (and programming languages generallycan be described using grammar-- set of syntax rules that define what is valid syntax for the data or language of coursejust because statement is syntactically valid doesn' mean that it makes sense--for example"the cat ate democracyis syntactically valid englishbut meaningless nonethelessbeing able to define the grammar is very usefulso much so that there is commonly used syntax for describing grammars--bnf (backus-naur formcreating bnf is the first step to creating parserand although not formally necessaryfor all but the most trivial grammars it should be considered essential here we will describe very simple subset of bnf syntax that is sufficient for our needs in bnf there are two kinds of itemterminals and nonterminals terminal is an item which is in its final formfor examplea literal number or string nonterminal is an item that is defined in terms of zero or more other items (which themselves may be terminals or nonterminalsevery nonterminal must ultimately be defined in terms of zero or more terminals figure shows an example bnf that defines the syntax of file of "attributes"to put things into perspective in practiceparsing english and other natural languages is very difficult problemseefor examplethe natural language toolkit (www nltk orgfor more information