Parsec: не работает возврат

Question

Я пытаюсь разобрать синтаксис типа F #. Я начал писать грамматику [F] Parsec и столкнулся с проблемами, поэтому я упростил грамматику до этого:

type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+

После проблем с FParsec я переключился на Parsec, так как у меня есть полная глава книги, посвященная объяснению . Мой код для этой грамматики

typeP = choice [identP, arrowP]
identP = do
   id <- many1 (digit <|> letter <|> char '.' <|> char '`')
   -- more complicated code here later
   return id
arrowP = do
  domain <- typeP
  string "->"
  range <- typeP
  return $ "("++domain++" -> "++range++")"
run = parse (do t <- typeP
                eof
                return t) "F# type syntax"

Проблема в том, что Parsec по умолчанию не возвращается, поэтому

> run "int"
Right "int"
-- works! 
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!

Первым делом я попытался изменить тип P:

typeP = choice [arrowP, identP]

Но это просто переполнение стека, потому что грамматика является леворекурсивной - typeP никогда не пытается identP, потому что она продолжает пытаться arrowP снова и снова. Затем я попробовал try в разных местах, например:

typeP = choice [try identP, arrowP]

Но, похоже, ничто из того, что я делаю, не меняет базового поведения (1) переполнения стека или (2) непризнания "->" после идентификатора.

Моя ошибка, вероятно, очевидна для любого, кто успешно написал грамматику Парсека. Кто-нибудь может указать на это?

Answer 1

Я думаю, что проблема в том, и я делаю предположение для F # (потому что я этого не знаю), стрелки прямо ассоциативны. Я не уверен, насколько точной должна быть связанная грамматика, так как я плохо разбираюсь в разных грамматиках. Но если мы можем предположить, что стрелки являются ассоциативными справа, то это облегчает проблему.

Итак, с этим предположением мы можем сделать тривиально:

identP = many1 (digit <|> letter <|> char '.' <|> char '`')

typeP = try arrowP <|> identP

arrowP = do
  i <- identP
  string "->"
  t <- typeP
  return $ "(" ++ i ++ " -> " ++ t ++ ")"

run = flip parse "F# type syntax" $ do
        t <- typeP
        eof
        return t

Итак:

Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"

Более того, вас может сбить с толку то, что в этой грамматике написано тип -> тип, что означает, что у вас может быть стрелка слева. Это хорошо, но это должно быть в скобках. Что помогает, может быть, полезно видеть следующее в действии. Это помогло мне.

typeP = try arrowP <|> parens typeP <|> identP

arrowP = do
 i <- parens typeP <|> identP
 string "->"
 t <- typeP
 return $ "(" ++ i ++ " -> " ++ t ++ ")"

parens p  = between (char '(') (char ')') p

Теперь мы можем написать стрелки слева или справа от стрелки:

Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"

Answer 2

Я думаю, что вы должны выделить левую рекурсию из грамматики. Вместо

type ::= identifier | type -> type 
identifier ::= [A-Za-z0-9.`]+ 

вы получите что-то вроде

typeStart ::= identifier 
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+ 

Тогда я думаю, что это будет легче перевести прямо в парсек. (Можно было бы подумать, что try сработает, и я ожидаю, что это как-то сработает, но да, мой опыт также заключался в том, что я должен был быть по крайней мере по пояс в Parsec, прежде чем я когда-либо понял, "куда поместить try" заставить вещи работать.)

Рассмотрите также Монадные комбинаторы синтаксического анализатора в F # (а также 7 предыдущих записей в блоге C #) для некоторых основ. Я думаю, что parsec docs (попробуйте просто прочитать их сверху вниз, они приличны, если я правильно помню), а также некоторые примеры в различных исследовательских работах рассказывают о проблемах, подобных той, что была в вашем вопросе.

Answer 3

Это не поможет вам понять, в чем дело, но я бы посоветовал использовать sepBy1 для разбора типов, разделенных -> символами. Это даст вам список проанализированных типов, которые вы потом сможете снова превратить в типы функций.