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

Haskell中正确的ReadP用法

haskell parsing

dsign · 技术社区 · 14 年前

我用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 回复 | 直到 14 年前

luqui 14 年前

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 ]

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

推荐文章

the thinker · Literate Haskell为Cabal指定显式源路径

5 月前

Seeker · 如果我不使用第一个扩展,为什么在使用Safe扩展时,我会收到关于GeneralizedNewtypeDeriving扩展的警告?

5 月前

141592653 · GHCi未推断某些IO操作的实例

6 月前

Enlico · 运行monad变压器堆产生的任何东西都不是==无?

6 月前

The Oddler · TVar会阻止读取直到更改吗?

10 月前

user20102550 · 如果我们绑定两个解析器,而第二个解析器失败,字符串会被解析一次吗?

11 月前

141592653 · 为什么GHC的类型检查器接受这种UndeterminedInstance技巧?

11 月前

user20102550 · 如何在解析器中使用输入字符串

11 月前

kesarling · 这个Haskell列表理解是如何评估的?

12 月前

kesarling · haskell中的箭头运算符在使用多个参数的函数中有什么意义?

1 年前