^^Grammatica formale per le espressioni di operazioni binarie.

 

Storia

Parsing timeline. e' l'articolo migliore per capire storia e difficoltà del parsing of an operator expresssion.

Links

Albero di un'espressione di operazioni binarie.

  1. robertjacobson/the-grammar-of-mathematical-expressions
  2. cs.stackexchange/how-does-one-make-an-unambiguous-context-free-grammar-for-arithmetic-expressions
  3. In Python

 

robertjacobson/when-students-die

Esempi

Unsigned integer

D → 0|1|2|3|4|5|6|7|8|9

N → D | DN

the grammar generates all integers unsigned nr, allowing redundant leading 0s.

Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}    the alphabet consists of the decimal digits

 

Context-free grammar. Context-sensitive grammar.

1965 KNUTH-OP

 

originale      

 

S ::= E
E ::= - T
E ::= T
E ::= E - T
T ::= P
T ::= T * P
P ::= a
P ::= ( E )

 

semplificata da me

 

S ::= E
E ::= T    
E ::= E + T
T ::= P
T ::= T * P
P ::= a
P ::= ( E )

 

KNUTH-OP  è 

noncontracting_grammar   in ogni regola di produzione

lunghezza parte sinistra  ≤  len(parte destra).

Le sostituzioni che non cambiano il nr di operandi

S ::= E
E ::= T    
T ::= P
P ::= a
P ::= ( E )

 

(a+b)*(c+d)

Espressione con 1 operando:  a

E  T  P a      ottenibile solo in 1 modo  !!!

dim:

a ottenibile solo da P con  P ::= a

P ottenibile solo da T con  T ::= P

T ottenibile solo da P con  E ::= T

Espressione con 1 operando:  (a)

E  T  P  (E)  (T)  (P)  (a)      ottenibile solo in 1 modo

Espressione con 2 operandi: Somma di 2 operandi a+a

E  E+T  ognuno dei 2 termini se deve generare solo 1 termine, e' terminabile in 1 solo modo

Espressione con 2 operandi: Prodotto di 2 operandi a*a

E  T  T*P  ognuno dei 2 termini se deve generare solo 1 termine, e' terminabile in 1 solo modo

Espressione con 3 operandi: a+a+a

E  E+T  E+T+T   ognuno dei termini se deve generare solo 1 termine, e' terminabile in 1 solo modo

Espressione con 3 operandi: a*a*a

E  T  T*P  T*T*P

Espressione con 3 operandi: a+a*a

E  E+T  E+T*P

E  E+T  T+T  T+T*P

Espressione con 3 operandi: a*a+a

E  E+T  T+T  T*P+T

 

 

Approfond

ing:

exhausting /ɪɡˈzɔːstɪŋ,ɛɡˈzɔːstɪŋ/   estenuante   spossante

aggettivo
making one feel very tired; very tiring.
"a long and exhausting journey"

 

exhaust /ɪɡˈzɔːst,ɛɡˈzɔːst/

verbo
1. make (someone) feel very tired.
"her day out had exhausted her"
Similar:  tire out  wear out   overtire    burdensome
2. use up (resources or reserves) completely.
"the country has exhausted its treasury reserves"
Similar:  waste   drain
"she seemed to have exhausted all permissible topics of conversation"
3. expel (gas or steam) from or into a particular place.
"you should never exhaust bathroom air into your attic"