Is there a way to fix an expression with operators in it after parsing, using a table of associativities and precedences?

user_11336776 0
Viewed 97

I'm currently working on a parser for a simple programming language written in Haskell. I ran into a problem when I tried to allow for binary operators with differing associativities and precedences. Normally this wouldn't be an issue, but since my language allows users to define their own operators, the precedence of operators isn't known by the compiler until the program has already been parsed.

Here are some of the data types I've defined so far:

data Expr
  = Var String 
  | Op String Expr Expr
  | ..

data Assoc 
  = LeftAssoc 
  | RightAssoc 
  | NonAssoc

type OpTable = 
  Map.Map String (Assoc, Int)

At the moment, the compiler parses all operators as if they were right-associative with equal precedence. So if I give it an expression like a + b * c < d the result will be Op "+" (Var "a") (Op "*" (Var "b") (Op "<" (Var "c") (Var "d"))).

I'm trying to write a function called fixExpr which takes an OpTable and an Expr and rearranges the Expr based on the associativities and precedences listed in the OpTable. For example:

operators :: OpTable
operators =
  Map.fromList
    [ ("<", (NonAssoc, 4))
    , ("+", (LeftAssoc, 6))
    , ("*", (LeftAssoc, 7))
    ]

expr :: Expr
expr = Op "+" (Var "a") (Op "*" (Var "b") (Op "<" (Var "c") (Var "d")))

fixExpr operators expr should evaluate to Op "<" (Op "+" (Var "a") (Op "*" (Var "b") (Var "c"))) (Var "d").

How do I define the fixExpr function? I've tried multiple solutions and none of them have worked.

abstract-syntax-tree parsing operators haskell
1 Answers

An expression e may be an atomic term n (e.g. a variable or literal), a parenthesised expression, or an application of an infix operator ○.

e ⩴ n | (e​) | e1 ○ e2

We need the parentheses to know whether the user entered a * b + c, which we happen to associate as a * (b + c) and need to reassociate as (a * b) + c, or if they entered a * (b + c) literally, which should not be reassociated. Therefore I’ll make a small change to the data type:

data Expr
  = Var String 
  | Group Expr
  | Op String Expr Expr
  | …

Then the method is simple:

  1. The rebracketing of an expression ⟦e⟧ applies recursively to all its subexpressions.

    1. ⟦n⟧ = n

    2. ⟦(e)⟧ = (⟦e⟧)

    3. ⟦e1 ○ e2⟧ = ⦅⟦e1⟧ ○ ⟦e2⟧⦆

  2. A single reassociation step ⦅e⦆ removes redundant parentheses on the right, and reassociates nested operator applications leftward in two cases: if the left operator has higher precedence, or if the two operators have equal precedence, and are both left-associative. It leaves nested infix applications alone, that is, associating rightward, in the opposite cases: if the right operator has higher precedence, or the operators have equal precedence and right associativity. If the associativities are mismatched, then the result is undefined.

    1. ⦅e ○ n⦆ = e ○ n

    2. ⦅e1 ○ (e2)⦆ = ⦅e1 ○ e2⦆

    3. ⦅e1 ○ (e2 ● e3)⦆ =

      1. ⦅e1 ○ e2⦆ ● e3, if:

        a. P(○) > P(●); or

        b. P(○) = P(●) and A(○) = A(●) = L

      2. e1 ○ (e2 ● e3), if:

        a. P(○) < P(●); or

        b. P(○) = P(●) and A(○) = A(●) = R

      3. undefined otherwise

NB.: P(o) and A(o) are respectively the precedence and associativity (L or R) of operator o.

This can be translated fairly literally to Haskell:

fixExpr operators = reassoc
  where

    -- 1.1
    reassoc e@Var{} = e

    -- 1.2
    reassoc (Group e) = Group (reassoc e)

    -- 1.3
    reassoc (Op o e1 e2) = reassoc' o (reassoc e1) (reassoc e2)

    -- 2.1
    reassoc' o e1 e2@Var{} = Op o e1 e2

    -- 2.2
    reassoc' o e1 (Group e2) = reassoc' o e1 e2

    -- 2.3
    reassoc' o1 e1 r@(Op o2 e2 e3) = case compare prec1 prec2 of

      -- 2.3.1a
      GT -> assocLeft

      -- 2.3.2a
      LT -> assocRight

      EQ -> case (assoc1, assoc2) of

        -- 2.3.1b
        (LeftAssoc, LeftAssoc) -> assocLeft

        -- 2.3.2b
        (RightAssoc, RightAssoc) -> assocRight

        -- 2.3.3
        _ -> error $ concat
          [ "cannot mix ‘", o1
          , "’ ("
          , show assoc1
          , " "
          , show prec1
          , ") and ‘"
          , o2
          , "’ ("
          , show assoc2
          , " "
          , show prec2
          , ") in the same infix expression"
          ]

      where
        (assoc1, prec1) = opInfo o1
        (assoc2, prec2) = opInfo o2
        assocLeft = Op o2 (Group (reassoc' o1 e1 e2)) e3
        assocRight = Op o1 e1 r

    opInfo op = fromMaybe (notFound op) (Map.lookup op operators) 

    notFound op = error $ concat
      [ "no precedence/associativity defined for ‘"
      , op
      , "’"
      ]

Note the recursive call in assocLeft: by reassociating the operator applications, we may have revealed another association step, as in a chain of left-associative operator applications like a + b + c + d = (((a + b) + c) + d).

I insert Group constructors in the output for illustration, but they can be removed at this point, since they’re only necessary in the input.

This hasn’t been tested very thoroughly at all, but I think the idea is sound, and should accommodate modifications for more complex situations, even if the code leaves something to be desired.

An alternative that I’ve used is to parse expressions as “flat” sequences of operators applied to terms, and then run a separate parsing pass after name resolution, using e.g. Parsec’s operator precedence parser facility, which would handle these details automatically.

user_2468860
Related