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.
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.
