ошибка синтаксического анализатора в haskell

Question

Я должен сделать парсер для языка со следующей грамматикой:

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 ")"

Со следующим типом данных для 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)

Моя проблема заключается в реализации оператора Shift, потому что я получаю следующую ошибку, когда сталкиваюсь со сдвигом влево или вправо:

неожиданное ">" ожидающий оператор или ";"

Вот код, который у меня есть для 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)

Я подозреваю, что проблема связана с предвкушением, но я не могу понять это.

Answer 1

Вот грамматика с удаленной рекурсией (не проверено).Stmts и Choices могут быть упрощены с помощью parsec's many и many1.Другие рекурсивные производства должны быть расширены:

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 ")"

---

Правка - "Часть вторая"

"empty" (в углах) - это пустое производство, вы использовали epsilon воригинальный пост, но я не знаю его кодовую точку Unicode и не думал копировать и вставлять его.

Вот пример того, как я буду кодировать грамматику.Обратите внимание - в отличие от грамматики, которую я разместил, пустые версии всегда должны быть последним выбором, чтобы дать возможность другим продуктам соответствовать.Кроме того, ваши типы данных и конструкторы для Абстрактного синтаксического дерева, вероятно, отличаются от предположений, которые я сделал, но должно быть достаточно ясно, что происходит.Код не проверен - надеюсь, любые ошибки очевидны:

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

Answer 2

Parsec по-прежнему греческий для меня, но мое смутное предположение состоит в том, что aShift должен использовать try.

В документах parsec для Hackage есть пример, объясняющий использование try с <|>, которые могут вам помочь.