H98 Report: expression syntax glitch

Simon Marlow simonmar@microsoft.com
Mon, 25 Feb 2002 16:27:56 -0000

> Consider the following Haskell 98 expressions:
> 	(let x =3D 10 in x `div`)
> 	(let x =3D 10 in x `div` 3)
> To parse the first, a bottom-up parser should reduce the=20
> let-expression
> before the operator, while to parse the second it should shift.
> But it needs 4 tokens of lookahead to decide which to do.  That seems
> unreasonable, and is well beyond the LALR(1) parsers used by=20
> Hugs and GHC.
> Replacing `div` by + needs 2 tokens of lookahead, which is=20
> still too much.
> I think the first should be made illegal, but can't think of=20
> a clean rule.
> (There are similar expressions using lambda and if.)

This is a known problem with the Haskell grammar.  Another example in a =
similar vein is

	let x =3D 3 in x =3D=3D 4 =3D=3D True

which should parse as

	(let x =3D 3 in x =3D=3D 4) =3D=3D True

according to the "extends as far to the right as possible" rule, because =
'=3D=3D' is nonfix.  In order to do this, the parser must have access to =
the fixity information for '=3D=3D', which is unreasonable (fixity =
declarations can even be local to a binding group).  Perhaps it is =
possible to post-process the parse when the fixities have been resolved, =
but that seems overly complex even if it is possible.

My favourite solution would be to remove the notion of operator =
precedence from the grammar altogether and specify fixity resolution =