Парсек:возврат не работает
-
18-09-2019 - |
Вопрос
Я пытаюсь проанализировать синтаксис типа 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) нераспознавание «->» после идентификатора.
Моя ошибка, вероятно, очевидна для любого, кто успешно написал грамматику парсека.Может ли кто-нибудь указать на это?
Решение
Я думаю, что проблема в том, что (и я делаю предположение для 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)"
Другие советы
Я думаю, вам следует исключить левую рекурсию из грамматики.Вместо
type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+
вы получаете что-то вроде
typeStart ::= identifier
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+
Тогда, я думаю, это будет проще перевести непосредственно в парсек.(Можно было бы подумать, что try
сработает, и я ожидаю, что это каким-то образом сработает, но да, мой опыт также показал, что мне нужно было быть хотя бы по пояс в парсеке, прежде чем я понял, «куда вставить try
"чтобы все работало.)
Рассмотрите возможность посмотреть также Комбинаторы монадического парсера в F# (а также семь предыдущих записей в блоге C#) для получения некоторых основ.я думаю документы по парсеку (попробуйте просто прочитать их сверху вниз, они приличные, если я правильно помню), а также некоторые примеры в различных исследовательских работах говорят о проблемах, подобных той, что в вашем вопросе.
Это не поможет вам понять, в чем вы ошибаетесь, но я бы предложил изучить возможность использования sepBy1
для анализа типов, разделенных ->
символы.Это даст вам список проанализированных типов, которые вы затем сможете снова превратить в функциональные типы.