News for hackers. Stuff that matters.
Re:Regular, Recursive, Restricted by HelloNurse on Thursday June 06, 2024 @09:02AM (#40596876)
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.

There are no comments on this comment yet.