^^Context-free grammar. Context-sensitive grammar.

CFG context-free grammar  rules: left-hand side only 1 letter

1. is the formalism of choice for describing the syntax of programming languages.
2. CFG describes a language as the set of strings generated from the grammar’s initial symbol by a sequence of rewriting steps.

Problems

1. CFG does not specify how to parse the language ! 
2. CFG may be ambiguos: a string can have more than 1 parse tree.

ref: CFG vs PEG. Context-Free Gram VS Parsing Expression Gram.

Esempi

1. E → (E+E)
2. E → (E*E)
3. E → nr

Es derivation of all strings by 2 productions using only rule 1&2

    rule 1 as 1st

E  1  (E+E)  1  (E+(E+E)) ... (5+(6+7))

E  1  (E+E)  1  ((E+E)+E) ... ((5+6)+7)

E  1  (E+E)  2  (E+(E*E)) ... (5+(6*7))

E  1  (E+E)  2  ((E*E)+E) ... ((5*6)+7)

    rule 2 as 1st

E  2  (E*E)  1  (E*(E+E)) ... (5*(6+7))

E  2  (E*E)  1  ((E+E)*E) ... ((5+6)*7)

E  2  (E*E)  2  (E*(E*E)) ... (5*(6*7))

E  2  (E*E)  2  ((E*E)*E) ... ((5*6)*7)

Notation: P nr Q  reads

• "String P generates string Q by means of production nr"
• the generated part is each time indicated in bold type.

Context-sensitive grammar.

per costruire le espressioni +* con priorita' della moltiplicazione, evitando cosi' parte delle parentesi.

regola 3 4 5 6 "esplora" il contesto di E per stabilire se sostituire con parentesi o senza

1.  S → E+E

2.  S → E*E

3. +E → E+E

4. E+ → E+E  

5. *E → *(E+E)

6. E* → (E+E)*

7.  E → E*E

8.  E → nr

S  1  E+E  3  E+E+E   ... 2+3+4   

S  1  E+E  7  E+E*E   ... 2+3*4

S  1  E*E  7  E*E*E   ... 2*3*4

S  1  E*E  5  E*(E+E) ... 2*(3+4)

S  1  E*E  6  (E+E)*E ... (2+3)*4