[Haskell-cafe] Can we write a parser with both name resolution and error handling by using Happy?

[Tsuyoshi Ito]

Hello,

I have a question about Happy, the parser generator.

Section 2.1 of Happy User Guide explains a neat trick to perform the
name resolution inside a parser by turning the semantic values of
nonterminal symbols into Reader monads.
    http://www.haskell.org/happy/doc/html/sec-using.html#sec-other-datatypes

(The example uses bare functions instead of Reader monads, but this
difference is insignificant.)

A compilable Calc.y file is available from https://gist.github.com/2554028.

The important part of the example is the following:

    Exp   : let var '=' Exp in Exp  { \p -> $6 (($2, $4 p) : p) }
          | Exp1                    { $1 }

    Exp1 : ...

    Term : ...

    Factor
          : int                     { \p -> $1 }
          | var                     { \p -> case lookup $1 p of
                                                Nothing -> error "no var"
                                                Just i  -> i }
          | '(' Exp ')'             { $2 }

The example code calls `error` on the failure in the name resolution.
Although this is fine as an example, it is not good in an actual
parser because that means that I have to run the parser in IO monad to
catch a parse error.  I would like to handle this error just like a
parse error by using a monadic parser as explained in Section 2.5.1.
    http://www.haskell.org/happy/doc/html/sec-monads.html#sec-exception

However, I cannot make this work.  I tried the following approaches:

1. Just combine these two techniques.  That is, write `%monad { E } {
thenE } { returnE }` in .y file, where `E t` is equivalent to `Either
String t` as defined in Section 2.5.1, and make the semantic value a
Reader monad.  This does not achieve what I want: now Happy expects
that the semantic expression of the form {% ... } will have type `E
(Env -> t)` (or `E (Reader Env t)`), but I want to write an expression
of type `Env -> E t` (or `ReaderT Env E t`) because whether name
resolusion succeeds or not depends on the environment.  See
https://gist.github.com/2554041 for a code (which does not compile).

2. Write `%monad { P } { thenP } { returnP }`, where `P t` is
equivalent to `Env -> E t` or `ReaderT Env E t` and `thenP` and
`returnP` are defined accordingly.  Now I cannot write the semantic
expression for the production rule `Exp : let var '=' Exp in Exp`,
because the semantic values of children ($2, $4, and $6) accessible in
the `{ ...  }` or `{% ... }` part is no longer Reader monads but plain
values, meaning that I cannot evaluate a subexpression ($6) using a
different environment from the current one.  Moreover, this feels
wrong because not every symbol requires the environment to evaluate.
See https://gist.github.com/2554044 for a code (which does not run
because it contains `undefined`).

3. Maybe I cannot use the `%monad` support for this purpose, so shall
I give up using it and just use `Env -> E t` as a type of semantic
values?  This is cumbersome at best because now in each production
rule, I have to handle the case where the semantic values of some of
the children are `Nothing` (after giving an environment).  But more
importantly, this does not work because Happy expects the `parseError`
function to have type `forall a. [Token] -> a` (which is
understandable), which means that it cannot return anything like
`Nothing`, defeating the purpose of the use of a monadic parser for
error handling.  See https://gist.github.com/2554122 for a code (which
does not run).