4 ms·
This technique has a problem with combinatorial explosion: N operators, N(N-1) exclusion rules plus a high risk of writing them incorrectly. Consider the 2 ope
by HelloNurse 2y ago
This technique has a problem with combinatorial explosion: N operators, N(N-1) exclusion rules plus a high risk of writing them incorrectly.
Consider the 2 operators example near the end:
Expr =
'number'
| '(' Expr ')'
| Expr '+' Expr
| Expr '*' Expr
Expr !=
Expr '+' [Expr '+' Expr]
| Expr '*' [Expr '*' Expr]
| Expr '*' [Expr '+' Expr]
| [Expr '+' Expr] '*' Expr
There are 1 exclusion per operator to enforce associativity (not problematic) and 2 exclusions (out of 4 trees containing both operators) to enforce precedence. These scale quadratically: if we add, say, exponentiation ('^') we need to add both
Expr!=
| Expr '^' [Expr '+' Expr]
| [Expr '+' Expr] '^' Expr
and
Expr!=
| Expr '^' [Expr '*' Expr]
| [Expr '*' Expr] '^' Expr
And so on.
There is a simpler but less elegant technique to constrain associativity and precedence: different types used asymmetrically.
Expr_base = 'number' | '(' Expr ')'
Expr_plus= Expr_plus '+' Expr_base | Expr_base
Expr_mul= Expr_mul '*' Expr_plus| Expr_plus
Expr_exp= Expr_mul '^' Expr_exp| Expr_mul
Expr=Expr_exp
Expr_mul contains no '^', Expr_plus contains no '^' and no '*', Expr_base contains no operator at all.