Two sharply different approaches: data-driven and grammar-based. There approaches in the middle too. For each kind, you have a wealth of approaches. You really need to dig deep into that if you want to become an expert, otherwise just download a tool and give it a try.

A parse tree (syntax tree) keeps track of

decisions made during parsing, the choices

of rules that have been applied.

Creating a parse tree is not a necessary

action, it is an option, a side effect

while applying grammar rules. Consider an

interpreter: statements are executed almost

immediately and then forgotten. A parse tree

can serve as a template for creating code

(machine code, P-Code) to be executed at

any time later. Or simply to represent

the structure of the source text, source code.

Typically context free grammars are preferred.

For parsing a context free grammar you can

use e.g. tools like Yacc in combination with

Lex, or an algorithm like CYK (Cocke Younge

Kasami), or recursive descent.

Let us discuss a recursive descent parser.

In a context free grammar (for languages

of Chomsky type 2) the left side of a

rule is one nonterminal (a symbol that

must be replaced). On the right side is

a string of symbols, each of them either

a terminal (word) or a nonterminal.

For a recursive descent parser, write

a function for each nonterminal that

appears of the left side of a rule.

Say we have the rules A -> x B

and A -> y C

Nonterminals are in capitals,

terminals in lowercase. Another thing

I should mention is that the next token

(word) decides what branch of grammar

rule to follow ("LR(1)"). In the above case

x or y decide whether the first or second

rule is to be applied. Our function:

ParseTreeItem A()

{

if (nextToken.value == "x")

return new ParseTreeItem("A", x, B());

else

return new ParseTreeItem("A", y, C());

}

The function is recursive, it calls B()

or C(), which in turn could call A().

And they return an object of type ParseTreeItem,

which might mean an inner node of

a parse tree, with appropriate constructor

arguments.

Note that the parser would also be possible

with functions that return no value.

Creating a parse tree is an option, a side effect.

A parser by itself does nothing more than

to decide whether a sentence is in a language

or not.

Literature:

http://en.wikipedia.org/wiki/Context-free_grammar

http://epaperpress.com/lexandyacc/

http://en.wikipedia.org/wiki/CYK_algorithm

http://en.wikipedia.org/wiki/Recursive_descent_parser

Regards,

Joachim

Also note that not all parsers think of grammar according to tree structures. Head-driven Phrase Structure Grammar (HPSG) is a feature-based  grammar.

Thanks evry1 for the answer....