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

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