Parsing with user-defined operator precedence

20
votes

OK, so here's a question: Given that Haskell allows you to define new operators with arbitrary operator precedence... how is it possible to actually parse Haskell source code?

You cannot know what operator precedences are set until you parse the source. But you cannot parse the source until you know the correct operator precedences. So... um, how?

Consider, for example, the expression

x *** y +++ z

Until we finish parsing the module, we don't know what other modules are imported, and hence what operators (and other identifiers) might be in scope. We certainly don't know their precedences yet. But the parser has to return something... But should it return

(x *** y) +++ z

Or should it return

x *** (y +++ z)

The poor parser has no way to know. This can only be determined once you hunt down the import that brings (+++) and (***) into scope, load that file off disk, and discover what the operator precedences are. Clearly the parser itself isn't going to do all that I/O; a parser just turns a stream of characters into an AST.

Clearly somebody somewhere has figured out how to do this. But I can't work it out... Any hints?

3
parsinghaskellsyntax
You could possibly build an AST with more than two children. Say this specific node gets as children the list [x, ***, y, +++, z], then check the precedence and build a binary node to replace itself afterwards. (There is probably a better approach). – Mephy
Note that you could also do this very easily without any hacks by just having two parse passes, one to grab operator fixity and precedence and one to actually parse the source code. – Cubic

3 Answers

11
votes

Quoting the page on GHC trac for the parser:

Infix operators are parsed as if they were all left-associative. The renamer uses the fixity declarations to re-associate the syntax tree.

8
votes

András Kovács's answer tells what's really done in GHC, but there's some history to this.

There was actually a somewhat hypothetical change from the Haskell 98 to the Haskell 2010 standard. In the former's BNF grammar, operator fixity and parsing were intertwined in such a way that you could in theory have some very strange interactions between the rules for fixity and the rules for when expressions and indentation blocks end. (For the latter two, the rules are essentially, "keep on going until you have to stop".)

In particular you could redefine a local operator and its fixity such that a use of it belonged in the redefining inner where block exactly ... when it didn't. So you got a parser paradox. I cannot find any of the old examples but this may be one:

let (+) = (Prelude.+)
    infix 9 + -- make the inner + high precedence and non-associative
in 2 + 3 + 4
--       ^ this + cannot parse here as the inner operator, which means
--         the let ... in ... expression should end automatically first,
--         but then it's the standard +, and its fixity says it should parse
--         as part of the inner expression...

In Haskell 2010 they officially changed that so that operator fixities are determined in a separate stage after the parsing proper.

So why was this a hypothetical change? Because all the compiler writers already did it the Haskell 2010 way, and always had, for their own sanity.

2
votes

Summarising the comments so far, it seems the possibilities are thus:

  • Return a parse tree where any infix operators are left as some kind of "list" structure, and then rearrange once precedences become known.
  • Pretend you know the operator precedences, and then rearrange the parse tree after the fact.
  • Do a first parse that only reads imports and fixity declarations, load the imports, and then do a full parse with known precedences.