parser in haskell error

Question

I am supposed to make a parser for a language with the following grammar:

Program ::= Stmts "return" Expr ";"
Stmts   ::= Stmt Stmts
            |   ε
Stmt    ::= ident "=" Expr ";"
            |   "{" Stmts "}"
            |   "for" ident "=" Expr "to" Expr Stmt
            |   "choice" "{" Choices "}"
Choices  ::=  Choice Choices
         |  Choice
Choice  ::=  integer ":" Stmt
Expr    ::=  Shift
Shift   ::=  Shift "<<" integer
            |   Shift ">>" integer
            |   Term
Term   ::=  Term "+" Prod
       |    Term "-" Prod
       |    Prod
Prod    ::=  Prod "*" Prim
            |   Prim
Prim    ::= ident
            |   integer
            |   "(" Expr ")"

With the following data type for Expr:

data Expr = Var Ident
        | Val Int
        | Lshift Expr Int
        | Rshift Expr Int
        | Plus Expr Expr
        | Minus Expr Expr
        | Mult Expr Expr
        deriving (Eq, Show, Read)

My problem is implementing the Shift operator, because I get the following error when I encounter a left or right shift:

unexpected ">" expecting operator or ";"

Here is the code I have for Expr:

expr = try (exprOp) 
    <|> exprShift           

exprOp = buildExpressionParser arithmeticalOps prim <?> "arithmetical expression"

prim :: Parser Expr
prim = new_ident <|> new_integer <|> pE <?> "primitive expression"
            where 
                    new_ident = do {i <- ident; return $ Var i }
                    new_integer = do {i <- first_integer; return $ Val i }
                    pE = parens expr

arithmeticalOps = [ [binary "*" Mult AssocLeft],
                    [binary "+" Plus AssocLeft, binary "-" Minus AssocLeft]
                    ]

binary  name fun assoc = Infix (do{ reservedOp name; return fun }) assoc 

exprShift = 
            do
                e <- expr
                a <- aShift
                i <- first_integer
                return  $ a e i

aShift = (reservedOp "<<" >> return Lshift) 
            <|> (reservedOp ">>" >> return Rshift)

I suspect the problem is concerning lookahead, but I can't seem to figure it out.

In a nutshell your grammar has left recursion on the Shift production. For an LL parser (which Parsec is one) you really need to remove left recursion. "try" gives you lookahead but it doesn't really solve left recursion, ideally you want to refactor the grammar. — stephen tetley
For the record, the whole grammar is in LR form - directly suitable for an LR parser like YACC or Haskell's Happy, but not immediately suitable for an LL one like Parsec. — stephen tetley

stephen tetley stephen tetley · Accepted Answer · 2011-02-27T22:53:25

Here's a grammar with left recursion eliminated (untested). Stmts and Choices can be simplified with Parsec's many and many1. The other recursive productions have to be expanded:

Program ::= Stmts "return" Expr ";"

Stmts   ::= @many@ Stmt

Stmt    ::= ident "=" Expr ";"
            |   "{" Stmts "}"
            |   "for" ident "=" Expr "to" Expr Stmt
            |   "choice" "{" Choices "}"

Choices  ::=  @many1@ Choice

Choice  ::=  integer ":" Stmt

Expr    ::=  Shift

Shift   ::= Term ShiftRest

ShiftRest ::= <empty>
          | "<<" integer
          | ">>" integer


Term ::= Prod TermRest

TermRest ::= <empty> 
         | "+" Term
         | "-" Term

Prod ::= Prim ProdRest

ProdRest ::= <empty> 
         |   "*" Prod

Prim    ::= ident
        |   integer
        |   "(" Expr ")"

Edit - "Part Two"

"empty" (in angles) is the empty production, you were using epsilon in the original post, but I don't know its Unicode code point and didn't think to copy-paste it.

Here's an example of how I would code the grammar. Note - unlike the grammar I posted empty versions must always be the last choice to give the other productions chance to match. Also your datatypes and constructors for the Abstract Syntax Tree probably differ to the the guesses I've made, but it should be fairly clear what's going on. The code is untested - hopefully any errors are obvious:

shift :: Parser Expr
shift = do 
    t <- term
    leftShift t <|> rightShift <|> emptyShift t

-- Note - this gets an Expr passed in - it is the "prefix"
-- of the shift production.
--
leftShift :: Expr -> Parser Expr
leftShift t = do 
  reservedOp "<<" 
  i <- int
  return (LShift t i)

-- Again this gets an Expr passed in.
--
rightShift :: Expr -> Parser Expr
rightShift t = do 
  reservedOp ">>" 
  i <- int
  return (RShift t i)

-- The empty version does no parsing.
-- Usually I would change the definition of "shift"
-- and not bother defining "emptyShift", the last 
-- line of "shift" would then be:
--
-- > leftShift t <|> rightShift t <|> return t
--
emptyShift :: Expr -> Parser Expr
emptyShift t = return t

parser in haskell error

2 Answers