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).
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, Tsuyoshi