Parser

Syntax: the way in which words are put together to form phrases, clause, or sentence.

1.Context-free grammar

We learn before that we use regular expression and finite automata to construct lexical scanner. For example.

            digits=[0-9]+

            sum=(digits"+")*digits

This use the abbreviation of 'digits' and can express 'sum=12+43+33'. But now consider

            digits=[0-9]+

            sum=expr"+"expr

            expr="("sum")"|digits

This can express 'sum=1+(123+9)'. But it is impossible for a finite automata to recognize that expression since it is recursive. In short we cannot use regular expression and finite automata to express things like that. So we need one more powerful tools to support recursion: Context-free Grammar! 

The grammar consists of 4 part:

1.Terminal (symbol).which is tokens obtained from lexical analysis. 

2.Nonterminal (symbol). using the abbreviation and appears on the left-hand side of a production.

3.Production.like the form:symbol ——>symbol symbol ... symbol.

4.Start symbol.the symbol you start to derive a sentence.

Context-free grammar

2. Parse tree 

Through the derivation of grammar, we can obtain an parse tree. For example, we want to derive a := 7; b := c + (d := 5 + 6, d) in terms of grammar above. The derivation and parse tree shows below.

Derivation

`Parse tree