[Haskell-cafe] Operator precedence and associativity on happy grammars

[j.romildo at gmail.com]

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
-------------- next part --------------
-- 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))
}