代码之家 › 专栏 › 技术社区 › dsign

Haskell中正确的ReadP用法

haskell parsing

7

dsign · 技术社区 · 15 年前

我用Haskell中的ReadP对文件中的数字列表做了一个非常简单的解析器。它能工作,但是它很慢。。。这是这类解析器的正常行为还是我做错了什么?

import Text.ParserCombinators.ReadP
import qualified Data.IntSet as IntSet
import Data.Char

setsReader :: ReadP [ IntSet.IntSet ]
setsReader = 
    setReader `sepBy` ( char '\n' )

innocentWhitespace :: ReadP ()
innocentWhitespace = 
    skipMany $ (char ' ') <++ (char '\t' )

setReader :: ReadP IntSet.IntSet
setReader =  do 
    innocentWhitespace
    int_list <- integerReader `sepBy1`  innocentWhitespace
    innocentWhitespace 
    return $ IntSet.fromList int_list

integerReader :: ReadP Int
integerReader = do
    digits <- many1 $ satisfy isDigit 
    return $ read digits

readClusters:: String -> IO [ IntSet.IntSet ]
readClusters filename = do 
    whole_file <- readFile filename 
    return $ ( fst . last ) $ readP_to_S setsReader whole_file

1 回复 | 直到 15 年前

1

13

luqui 15 年前

setReader 具有指数行为,因为它允许数字之间的空白 可选择的 . 所以对于这一行:

12 34 56

它看到了这些解析:

[1,2,3,4,5,6]
[12,3,4,5,6]
[1,2,34,5,6]
[12,34,5,6]
[1,2,3,4,56]
[12,3,4,56]
[1,2,34,56]
[12,34,56]

你可以看到这怎么可能失控的长队。 ReadP 回报 全部的 有效的解析以递增的长度顺序进行,因此要到达最后一个解析,必须遍历所有这些中间解析。更改:

int_list <- integerReader `sepBy1` innocentWhitespace

致:

int_list <- integerReader `sepBy1` mandatoryWhitespace

为了一个合适的定义 mandatoryWhitespace 压制这种指数行为。parsec使用的解析策略对这种错误的抵抗力更强,因为它是贪婪的——一旦它在给定的分支中使用了输入,它就会被提交到该分支,并且永远不会返回(除非您明确要求它返回)。所以一旦正确解析 12 ,它将永远不会返回到解析 1 2 . 当然,这意味着你以什么顺序陈述你的选择是很重要的,我总是觉得这是一个有点痛苦的想法。

我还将使用:

head [ x | (x,"") <- readP_to_S setsReader whole_file ]

为了提取一个有效的整个文件解析,万一它很快消耗了所有的输入,但是有无数种方法来解释这个输入。如果你不在乎歧义,你可能宁愿它返回第一个而不是最后一个,因为第一个会更快到达。