mrkkrp / mrkkrp/parser-combinators

makeExprParser: Mixing operators with different associativities in same precedence level does not work

Open
#87 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Haskell
Stars
55
Forks
17
PR merge metrics
No merged PRs in 30d

Description

When makeExprParser is given two infix operators at the same precedence level but with different associativit it stops before parsing the expression completely for some inputs.

Example:

operatorTable =
  [ [ prefix "-" Negation
    , prefix "+" id
    ]
  , [ binaryR "^" Expo
    , binaryL "*" Product
    , binaryL "/" Division
    ]
  , [ binaryL "+" Sum
    , binaryL "-" Subtr
    ]
  ]

For the above slightly modified example from the tutorial the parser stops unexpectedly:

ghci> parseTest pExpr "2 ^ 2 * 3 ^ 2"
Expo (Int 2) (Int 2)

This is unexpected because documentation says it should work:

All operators in one list have the same precedence (but may have different associativity).

Looking at the code it seems like this could be fixed by adding recursion to addPrecLevel. But I am not sure this is a good idea so have not created a PR to fix this.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with addPrecLevel in Control.Monad.Combinators.Expr and reproduce the issue using the operator table and input shown. Compare the documented mixed-associativity behavior with the parser result, then inspect nearby expression-parser code for existing tests or examples. Done means the full expression is parsed according to the documented precedence and associativity rules.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
56/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.