Can we write a parser with both name resolution and error handling by using Happy?

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Can we write a parser with both name resolution and error handling by using Happy?

Tsuyoshi Ito-2

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.

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

A compilable Calc.y file is available from

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 : ...

          : 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.

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 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 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 for a code (which
does not run).

From this, it does not seem that name resolution can be performed
inside a parser if we need any error handling better than calling
`error`.  Is this really the case?  Because the combination of parsing
and name resolution is very natural (which is why the example in
Section 2.1 is so appealing), it is hard to believe that it cannot be
done nicely.

Am I missing something?  In case it matters, I am using Haskell
Platform 2011.4.0.0 on Windows.

(Just in case, I am aware that we can split parsing and name
resolution, in which case a parser generates an abstract syntax tree
(AST) with unresolved names and a name resolver converts it to an AST
with resolved names.  But is that a recommended way to use Happy?  If
so, the example in Section 2.1 is misleading at best.)

Best regards,

Haskell-Cafe mailing list
[hidden email]