Hello.
I am learning how to use Happy (a LALR(1) parser generator) and I have a
question on a grammar based on an example from the manual. The input
file to Happy is attached to this message.
The grammar is:
Exp -> let var = Exp in Exp
Exp -> Exp + Exp
Exp -> Exp - Exp
Exp -> Exp * Exp
Exp -> Exp / Exp
Exp -> ( Exp )
This grammar is ambiguous, but the conflicts that will appear in the
parser table can be resolved with precedence and associativity
declarations for the operators that surround expressions:
%right in
%left + -
%left * /
giving right associativity to the in token, and left associativity to
the arithmetic operators, and giving lower precedence to in, followed by
+ and -, and then by * and /.
I see that if the token in is not given a precedence declaration, the
grammar still is ambiguous, as can be seen in the example of parsing the
expression:
let v = e1 in e2 + e3
which could be parsed as
(let v = e1 in e2) + e3
or
let v = e1 in (e2 + e3)
Giving the token in a lower precedence makes the parser choose the last
option.
My question is about the associativity of the token in? Does it make any
difference giving it left associativity, right associativity, or making
it non associative?
Regards.
José Romildo
-- calc3.y -*- mode: haskell -*-
{
module Main where
import Data.Char (isSpace, isDigit, isAlpha, isAlphaNum)
import Data.Maybe (fromMaybe)
}
%name calc
%tokentype { Token }
%error { parseError }
%token
let { TokenLet }
in { TokenIn }
int { TokenInt $$ }
var { TokenVar $$ }
'=' { TokenEq }
'+' { TokenPlus }
'-' { TokenMinus }
'*' { TokenTimes }
'/' { TokenDiv }
'(' { TokenLP }
')' { TokenRP }
%nonassoc in
%left '+' '-'
%left '*' '/'
%left NEG
%%
Exp : let var '=' Exp in Exp { \env -> $6 (($2,$4 env) : env) }
| Exp '+' Exp { \env -> $1 env + $3 env }
| Exp '-' Exp { \env -> $1 env - $3 env }
| Exp '*' Exp { \env -> $1 env * $3 env }
| Exp '/' Exp { \env -> $1 env `div` $3 env }
| '(' Exp ')' { $2 }
| '-' Exp %prec NEG { \env -> - ($2 env) }
| int { \env -> $1 }
| var { \env -> fromMaybe 0 (lookup $1 env) }
{
parseError :: [Token] -> a
parseError _ = error "Parse error"
data Token
= TokenLet
| TokenIn
| TokenInt Int
| TokenVar String
| TokenEq
| TokenPlus
| TokenMinus
| TokenTimes
| TokenDiv
| TokenLP
| TokenRP
deriving (Show)
lexer :: String -> [Token]
lexer [] = []
lexer (c:cs) | isSpace c = lexer cs
| isAlpha c = let (name,rest) = span isAlphaNum cs
tok = case c:name of
"let" -> TokenLet
"in" -> TokenIn
var -> TokenVar var
in tok : lexer rest
| isDigit c = let (num,rest) = span isDigit cs
in TokenInt (read (c:num)) : lexer rest
lexer ('=':cs) = TokenEq : lexer cs
lexer ('+':cs) = TokenPlus : lexer cs
lexer ('-':cs) = TokenMinus : lexer cs
lexer ('*':cs) = TokenTimes : lexer cs
lexer ('/':cs) = TokenDiv : lexer cs
lexer ('(':cs) = TokenLP : lexer cs
lexer (')':cs) = TokenRP : lexer cs
main = do input <- getContents
mapM_ print (map (($ []) . calc . lexer) (lines input))
}
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
