Парсек:возврат не работает

Question

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

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!

Первое, что я попробовал, — это изменить порядок typeP:

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 сработает, и я ожидаю, что это каким-то образом сработает, но да, мой опыт также показал, что мне нужно было быть хотя бы по пояс в парсеке, прежде чем я понял, «куда вставить try"чтобы все работало.)

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

Answer 3

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