为什么在这个例子中不尝试触发回溯
Why does try not trigger backtracking in this example
我正在尝试在 Haskell 中使用 parsec 编写解析器,特别是回溯的工作原理。
采用以下简单的解析器:
import Text.Parsec
type Parser = Parsec String () String
parseConst :: Parser
parseConst = do {
x <- many digit;
return $ read x
}
parseAdd :: Parser
parseAdd = do {
l <- parseExp;
char '+';
r <- parseExp;
return $ l <> "+" <> r
}
parseExp :: Parser
parseExp = try parseConst <|> parseAdd
pp :: Parser
pp = parseExp <* eof
test = parse pp "" "1+1"
test
有价值
Left (line 1, column 2):
unexpected '+'
expecting digit or end of input
在我看来这应该会成功,因为我在 parseExp
.
的定义中对 parseConst
使用了 try
组合子
我错过了什么?我也对如何自己调试它的指针感兴趣,我尝试使用 parserTraced
这只是让我得出结论它确实不是回溯。
PS。
我知道这是编写表达式解析器的糟糕方法,但我想了解为什么它不起作用。
这里有很多问题。
首先,parseConst
永远无法正常工作。该类型表示它必须产生一个 String
,所以 read :: String -> String
。该特定 Read
实例要求输入是带引号的字符串,因此如果您尝试评估 read
将 0 个或多个数字字符传递给 read
总是会导致调用 error
它产生的价值。
其次,parseConst
可以成功匹配零个字符。我认为您可能想要 some
而不是 many
。如果遇到不是以数字开头的输入,这将使其实际上失败。
第三,(<|>)
没有按照你的想法去做。您可能认为 (a <* c) <|> (b <* c)
可以与 (a <|> b) <* c
互换,但事实并非如此。也没有办法将 try
放入并使其相同。问题是 (<|>)
提交到任何成功的分支,如果有的话。在 (a <|> b) <* c
中,如果 a
匹配,则以后没有办法回溯并在那里尝试 b
。无论你如何抛出 try
,都无法消除 (<|>)
致力于 a
的事实。相反,(a <* c) <|> (b <* c)
在 a
和 c
或 b
和 c
都匹配输入之前不会提交。
这就是您遇到的情况。经过一些内联后,您有 (try parseConst <|> parseAdd) <* eof
。因为 parseConst
总是会成功(见第二期),所以 parseAdd
永远不会被尝试,即使 eof
失败了。因此,在 parseConst
消耗了零个或多个前导数字后,解析将失败,除非那是输入的结尾。解决这个问题本质上需要仔细规划您的语法,以便 (<|>)
的任何使用都可以安全地在本地提交。也就是说,每个分支的内容不得以仅由语法的后面部分消除歧义的方式重叠。
请注意,(<|>)
的这种令人不快的行为是 parsec 系列库的工作方式,而不是 Haskell 中所有解析器库的工作方式。其他库在没有 parsec 家族选择的左偏或提交行为的情况下工作。
我正在尝试在 Haskell 中使用 parsec 编写解析器,特别是回溯的工作原理。
采用以下简单的解析器:
import Text.Parsec
type Parser = Parsec String () String
parseConst :: Parser
parseConst = do {
x <- many digit;
return $ read x
}
parseAdd :: Parser
parseAdd = do {
l <- parseExp;
char '+';
r <- parseExp;
return $ l <> "+" <> r
}
parseExp :: Parser
parseExp = try parseConst <|> parseAdd
pp :: Parser
pp = parseExp <* eof
test = parse pp "" "1+1"
test
有价值
Left (line 1, column 2):
unexpected '+'
expecting digit or end of input
在我看来这应该会成功,因为我在 parseExp
.
parseConst
使用了 try
组合子
我错过了什么?我也对如何自己调试它的指针感兴趣,我尝试使用 parserTraced
这只是让我得出结论它确实不是回溯。
PS。 我知道这是编写表达式解析器的糟糕方法,但我想了解为什么它不起作用。
这里有很多问题。
首先,parseConst
永远无法正常工作。该类型表示它必须产生一个 String
,所以 read :: String -> String
。该特定 Read
实例要求输入是带引号的字符串,因此如果您尝试评估 read
将 0 个或多个数字字符传递给 read
总是会导致调用 error
它产生的价值。
其次,parseConst
可以成功匹配零个字符。我认为您可能想要 some
而不是 many
。如果遇到不是以数字开头的输入,这将使其实际上失败。
第三,(<|>)
没有按照你的想法去做。您可能认为 (a <* c) <|> (b <* c)
可以与 (a <|> b) <* c
互换,但事实并非如此。也没有办法将 try
放入并使其相同。问题是 (<|>)
提交到任何成功的分支,如果有的话。在 (a <|> b) <* c
中,如果 a
匹配,则以后没有办法回溯并在那里尝试 b
。无论你如何抛出 try
,都无法消除 (<|>)
致力于 a
的事实。相反,(a <* c) <|> (b <* c)
在 a
和 c
或 b
和 c
都匹配输入之前不会提交。
这就是您遇到的情况。经过一些内联后,您有 (try parseConst <|> parseAdd) <* eof
。因为 parseConst
总是会成功(见第二期),所以 parseAdd
永远不会被尝试,即使 eof
失败了。因此,在 parseConst
消耗了零个或多个前导数字后,解析将失败,除非那是输入的结尾。解决这个问题本质上需要仔细规划您的语法,以便 (<|>)
的任何使用都可以安全地在本地提交。也就是说,每个分支的内容不得以仅由语法的后面部分消除歧义的方式重叠。
请注意,(<|>)
的这种令人不快的行为是 parsec 系列库的工作方式,而不是 Haskell 中所有解析器库的工作方式。其他库在没有 parsec 家族选择的左偏或提交行为的情况下工作。