[Haskell-cafe] Can we write a parser with both name resolution and error handling by using Happy?
Tsuyoshi Ito
tsuyoshi.ito.2006 at gmail.com
Mon Apr 30 02:00:59 CEST 2012
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).
More information about the Haskell-Cafe
mailing list