解析任一类型的列表

Question

我正在为逻辑公式编写一个解析器，但它无法解析 Either 类型的列表。

解析器适用于所有情况，除了将函数替换为谓词之外 --

解析 P(f(x:X)=a:A,b:B) （使用 parsePredSub）应该返回替换 ((f,([(x,X)],A),(a,A)) 和谓词 (P, [(a,A),(b,B)])，但它只返回 (P, [Left b:B])。

然而解析 f(x:X)=a:A,b:B （使用 (commaSep ParseVSub)）返回 [Right (f(x:X),a:A),Left b:B]，这是正确的。不知何故，当我试图将其包装在“pparens”中时，“权利”被放弃了。

这可能是组合器语法的一个简单问题。所有的想法都受到赞赏。谢谢。

-- (types Pre and Var and Srt and Sym are String)
type VarSrt = (Var,Srt)
type Ctx = [VarSrt]
type Trm = (Sym,([VarSrt],Srt))
type Sub = (Trm,VarSrt)
type Bind = [Sub]
type Pred = (Pre, Ctx)
type PredSub = (Bind, Pred)

parseVS :: Parser VarSrt
parseVS = do {v<-identifier; string ":"; s<-identifier; return $ (v,s)}

pparens :: Parser a -> Parser (String,a)
pparens par = try $ do {p<-identifier; string "("; z <- par; string ")";
                        return (p,z)}

parseSub :: Parser Sub
parseSub =
  do {(f,a) <- pparens (commaSep parseVS); string "="; spaces;
       (x,s) <- parseVS; spaces;
       return $ ((f,(a,s)),(x,s))}

parseVSub :: Parser VSub
parseVSub = choice [Left <$> try parseVS, Right <$> try parseSub]

------- THE ISSUE --------
parsePredSub :: Parser PredSub
parsePredSub = try $ do {(p,bc) <- pparens (commaSep parseVSub);
                         return (rights bc,(p,lefts bc))}
--------------------------

lexeme :: Parser a -> Parser a
lexeme p = p <* whitespace

identifier :: Parser String
identifier = lexeme ((:) <$> firstChar <*> many nonFirstChar)
  where
    firstChar = letter <|> char '_'
    nonFirstChar = digit <|> firstChar

symbol :: String -> Parser String
symbol s = try $ lexeme $ do
    u <- many1 (oneOf "<>=+-^%/*!|,")
    guard (s == u)
    return s

Answer 1

我没有观察你所看到的行为。填写程序中缺少的部分并运行一些测试后：

main = do
  parseTest (commaSep parseVSub) "f(x:X)=a:A,b:B"
  parseTest parsePredSub "P(f(x:X)=a:A,b:B)"

我得到输出：

[Right (("f",([("x","X")],"A")),("a","A")),Left ("b","B")]
([(("f",([("x","X")],"A")),("a","A"))],("P",[("b","B")]))

换句话说，

commaSep parseVSub

返回一个二元素列表，一个绑定的权利：

Right (("f",([("x","X")],"A")),("a","A"))

第二个参数向左：

Left ("b","B")

而

parsePredSub

返回一对由所有权利（其中有一个）组成的对，以及由

Pred

加上所有左派（即左派）组成的

"P" :: Pre

作为其“参数”，如预期的那样:

([(("f",([("x","X")],"A")),("a","A"))],("P",[("b","B")]))
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     here is your "missing" right, right here...

也许您可以采用下面我的完整可运行示例并制定一个新的

main

函数来演示对您来说失败的确切测试用例：

import Control.Monad
import Data.Either
import Text.Parsec

type Parser = Parsec String ()

type Pre = String
type Var = String
type Srt = String
type Sym = String
type VSub = Either VarSrt Sub

commaSep :: Parser a -> Parser [a]
commaSep p = (:) <$> p <*> many (char ',' *> p)

whitespace :: Parser ()
whitespace = spaces

--
-- Your code starts here
--

-- (types Pre and Var and Srt and Sym are String)
type VarSrt = (Var,Srt)
type Ctx = [VarSrt]
type Trm = (Sym,([VarSrt],Srt))
type Sub = (Trm,VarSrt)
type Bind = [Sub]
type Pred = (Pre, Ctx)
type PredSub = (Bind, Pred)

parseVS :: Parser VarSrt
parseVS = do {v<-identifier; string ":"; s<-identifier; return $ (v,s)}

pparens :: Parser a -> Parser (String,a)
pparens par = try $ do {p<-identifier; string "("; z <- par; string ")";
                        return (p,z)}

parseSub :: Parser Sub
parseSub =
  do {(f,a) <- pparens (commaSep parseVS); string "="; spaces;
       (x,s) <- parseVS; spaces;
       return $ ((f,(a,s)),(x,s))}

parseVSub :: Parser VSub
parseVSub = choice [Left <$> try parseVS, Right <$> try parseSub]

------- THE ISSUE --------
parsePredSub :: Parser PredSub
parsePredSub = try $ do {(p,bc) <- pparens (commaSep parseVSub);
                         return (rights bc,(p,lefts bc))}
--------------------------

lexeme :: Parser a -> Parser a
lexeme p = p <* whitespace

identifier :: Parser String
identifier = lexeme ((:) <$> firstChar <*> many nonFirstChar)
  where
    firstChar = letter <|> char '_'
    nonFirstChar = digit <|> firstChar

symbol :: String -> Parser String
symbol s = try $ lexeme $ do
    u <- many1 (oneOf "<>=+-^%/*!|,")
    guard (s == u)
    return s

--
-- Your code ends here
--

main = do
  parseTest (commaSep parseVSub) "f(x:X)=a:A,b:B"
  parseTest parsePredSub "P(f(x:X)=a:A,b:B)"