代码之家 › 专栏 › 技术社区 › 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 ]

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

推荐文章

batman · 如何用特定模式grep特定行及其子网行?

2 年前

user19251203 · ReactJs:Uncaught TypeError:无法读取未定义的属性(读取“0”)

2 年前

Jensen Holm · 在非常大的字符串中查找链接时遇到问题

2 年前

MBF · PHP导入/解析XML文件内容保存到数据库

2 年前

John Bustos · Javascript——基于字典/对象中的键解析字符串

2 年前

user10717742 · 用java编写的自定义文件解析器需要改进

2 年前

Taj Harris · JSONArray文本必须以“[”开头,位于1[字符2第1行]:需要帮助解析Json

2 年前

Muhsin Muhammed · 向文件中的行添加引号和逗号

2 年前

Felkru · 添加字符串会在Javascript中返回空字符串

2 年前

Mustard Tiger · 熊猫解析文本列

2 年前