Hello World
Spiga

趣味编程:从字符串中提取信息(参考答案 - 下)

2009-10-22 01:04 by 老赵, 16631 visits

昨天我们观察了如何使用基于状态机的顺序解析方式来提取字符串中的信息,不过由于winter-cn的做法和我原始的想法不谋而合,但实现的更为清晰,因此我在不献丑的同时,又设法使用另外一种方式来解决这个问题。后来又看到许多朋友给出了各种各样的做法,有普通拆分的方式,有利用正则表达式的做法。于是最后,我“不得不”使用一种特别的方式:F#来编写这么一段解析逻辑。从中我们也可以看到F#在做一些解析工作时的方便之处,在今后我还会谈一下它对我编写C#代码时的启发。

在我看来,F#的解析逻辑相对前文的做法更容易理解一些,其中有个重要因素便是F#的语言特性,如自然的“元组”使用方式和直观的模式匹配语法。它可以帮助我们使用更精简的代码,更“声明式”而不是“过程式”的代码来解决问题。这个文章会涉及到F#的一些“基础”,我会在接下来的过程中慢慢谈到这些。

首先,第一个“概念”便是F#乃至普通函数式编程中最常见(没有之一)的数据结构:不可变的链表。在前一次“趣味编程”中,我们我们还对这样的链表进行了快速排序。不可变的链表是一个典型的单向链表,它的结构大致是这样的:

可见,这是一种递归的数据结构。每个链表会包含一个元素的“值”,以及另一个链表对象(在上图中,每个框就是一个链表对象)。对于每个链表对象来说,这个“值”便是它的“头(Head)”,而内部的链表对象则是它的“尾(Tail)”。不过方便起见,一个链表往往也会使用一种非递归的方式来表示,尤其是在书写的时候:

1 :: 2 :: 3 :: []

在F#中,图中的链表可以表示为上面这种形式。“::”符号在F#中表示链表的“头”和“尾”(即另一个链表)的连接操作。也就是说,连接符号的左运算数是一个元素,而右运算数是这个元素同类型的链表——嗯,泛性的链表。因此你可以理解,上面这个表达式的最后一个元素是一个空链表,而且连接符号是右关联的(也就是说,对连续的运算符,是从右往左依次计算的)。不过,这个表示方法还是不够简洁,在F#中还可以用下面几种方式来表示相同的链表:

[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]

也就是说,在F#中,一个链表可以表示为使用方括号包含的元素序列,元素之间使用分号隔开。这个表示法就简单多了。

链表在F#中有着非常重要的意义,我们可以对它使用非常直观的模式匹配方式来进行处理。因此,我们输入的字符串也会先被转化为一个“存放字符的链表”再进行处理——至于转化方式我们慢慢再说。假设我们已经得到了这样的链表,如这样的字符串:

"CPU-3.0G--Color-red-green-black--Price-2000-4000--Weight-'5-'--keywords-'levis'"

即可转化为这样的链表(自然中间省略了很多元素):

'C' :: 'P' :: 'U' :: '-' :: '3' :: ... :: 'l' :: 'e' :: 'v' :: 'i' :: 's' :: '\'' :: []

而我们的最终结果,便是这样一个parse方法:

let rec parse groups chars =                     // 1
    match chars with                             // 2
    | [] -> groups |> List.rev                   // 3
    | '-' :: '-' :: cs -> parse groups cs        // 4
    | _ –>                                       // 5
        let (g, rest) = readTokenGroup [] chars  // 6
        parse (g :: groups) rest                 // 7

以上7行代码便是parse函数的完整逻辑:

  1. 定义一个递归(rec)的parse方法,接受两个参数:groups(当前得到的token group链表)和chars(需要解析的字符链表)。
  2. F#中模式匹配的起始语法,匹配目标是chars参数,即需要解析的字符链表
  3. 如果chars为空链表(即“[]”),则意味着没有需要解析的内容了,于是将链表逆序输出。
  4. 如果chars链表的前两个字符都是“-”,则意味着它们是token groups之间的分隔符,于是忽略它们,继续解析char的剩余部分(cs)。
  5. 如果是其他任何情况——下划线“_”表示任意匹配
  6. 调用readTokenGroup方法解析一个完整的token group,输入一个空链表和chars数组,得到一个元组。第一个元素为解析出的token group,第二个元素为chars链表在token group后的剩余部分。
  7. 此时,g包含第6行解析得到的token group,rest为剩余字符链表。于是递归调用parse方法继续解析rest,其中第一个参数(当前得到的token group链表)为g并入原始groups后的结果。

从中我们可以看出F#中的许多独到之处:

  • 函数的定义是不需要指明参数的,同样也不需要指明返回值。F#编译器有着完整的类型推演(Type Inference)能力可以自动得到每个函数的实际签名。
  • F#的模式匹配可以使用多条规则,其中每条规则中“->”左侧为匹配条件,右侧为匹配结果。
  • 模式匹配左侧,既是“验证”又是“赋值”——确切地说是“绑定”。如第4行代码中,在验证chars前两个字符为“-”的同时,将char链表从第3个元素开始的部分绑定至cs中,于是在“->”符号右侧便可以使用cs了。
  • “纯正”的函数式编程中没有循环,如果要实现如C#中的循环效果,则需要使用递归。如parse便是一个递归函数,它会调用自身继续解析readTokenGroup返回的剩余部分。此外,这里还是“尾递归”。
  • 函数式编程中不需要return命令,因为函数式编程不同于命令式编程,不是由“语句”组成的,函数体也是另外的函数调用。如模式匹配的最后一条规则中,返回的便是parse函数递归调用的结果。
  • 由于链表的结构,向链表的前端添加元素是最为快速的(O(1)时间复杂度),因此我们每次都向groups参数头部添加数据,直到最后返回之前,才使用List模块的rev函数将链表逆序后输出。
  • ……(将视您的返回补充更多)

那么我们又该如何使用parse方法来解析text呢?事实上,我们使用的是这个方法:

let parse (text : string) =
    let rec parse' groups chars = 
        match chars with
        | [] -> groups |> List.rev
        | '-' :: '-' :: cs -> parse' groups cs
        | _ ->
            let (g, rest) = readTokenGroup [] chars
            parse' (g :: groups) rest
    text |> List.ofSeq |> parse' []

请注意,上面的parse函数已经变成了parse'(最后有个单引号),并且它是新的parse方法的“内部方法”——F#使用缩进来表示“代码的层次”,于是parse'函数便不会对外部公开了,它可以视为parse函数的辅助函数。而parse函数的返回值便是我们需要的结果:一个list<list<string>>对象(根据OCaml的写法,也可以写做string list list)。那么“|>”符号又是做什么的呢?它的作用是将一个参数“输入”给一个函数。例如,以下两种方式是完全等价的:

f x // F#中函数调用不需要括号
x |> f

因此,您可以把“|>”视为交换参数和函数顺序的方式。那么它的意义又是什么呢?其实,对于高级的函数式编程语言,如F#和Haskell,它们的许多特性的目的只有一个:帮助程序员开发出更易于理解的代码。例如,其实parse方法的最后一行也可以写做:

parse' [] (List.ofSeq text)

但是它就没有目前的写法来的流畅:把text传输给List.ofSeq函数,再把结果传输给parse作为最后一个参数(其实这里还用到了curry操作,不过您可以暂时不关心它)。因此,F#的许多函数都会把某个关键的参数放在最后,目的就是便于开发人员写出这种流畅的代码出来。其实,在设计C#类库的时候,我们也会有类似的考虑。至于List模块中的ofSeq方法,则是将一个seq<'a>对象——即IEnumerable<T>转化为T类型的链表。

第一个例子主要是用来展示一些F#中的语言特性,但没有涉及到太多的逻辑。接下来的进度就会比较快了,例如我们在parse’函数里使用的readTokenGroup函数便是如下定义:

// readTokenGroup函数有两个参数,tokens和chars,
// tokens表示当前group中已经收集到的token(字符串链表),而
// chars表示待解析的字符(字符链表)
let rec private readTokenGroup tokens chars = 
    match chars with
    // 如果是空链表
    | []
    // 或者前两个字符都是分隔符“-”, 
    // 则表示当前token group已经解析完了,
    // 于是将tokens逆序后输出(理由同parse'方法)
    | '-' :: '-' :: _ -> (tokens |> List.rev, chars)
    // 如果第一个字符为分隔符“-”,则忽略它,
    // 继续解析字符链表的剩余部分
    | '-' :: cs -> readTokenGroup tokens cs
    // 如果发现这个token group中的第一个token以单引号开头,
    // 则表明是一个使用单引号包裹的,带有特殊字符的token,
    // 于是使用readToken函数读取这个token,得到一个元组,
    // 其第一个字符为读到的token,rest为剩余部分,
    // 再递归调用readTokenGroup函数处理rest。
    | '\'' :: cs -> 
        let (t, rest) = readToken true [] cs
        readTokenGroup (t :: tokens) rest
    // 如果是其他字符,同样使用readToken方法读取第一个token,
    // 不过传入的第一个参数为false,表明不在引号内,
    // 其余逻辑和上一个模式的处理方式相同
    | _ ->
        let (t, rest) = readToken false [] chars
        readTokenGroup (t :: tokens) rest

readTokenGroup的职责是读取一个完整的token group,它会的返回值为一个元组,包含了表示一个token group的list<string>对象和字符串链表的剩余部分。其中会用到readToken来读取单个token。请注意,如果遇到了以单引号开头的token,它传给readToken函数的参数是不带这个单引号的——也就是说,readToken所接受的字符串链表永远不会包含第一个用于包裹token的单引号的。至于readToken函数代码如下:

// readToken有三个参数,
// inQuote表示是否正在读取引号内的token,
// tokenChars表示已经收集的token字符,
// restChars表示待解析的字符链表。
let rec private readToken inQuote tokenChars restChars =
    let chars2Token chars = new string(chars |> Array.ofList |> Array.rev)
    if inQuote then
        match restChars with
        | '\'' :: [] -> (chars2Token tokenChars, [])
        | '\'' :: '-' :: cs -> (chars2Token tokenChars, '-' :: cs)
        | '\'' :: '\'' :: cs -> readToken true ('\'' :: tokenChars) cs
        | c :: cs -> readToken true (c :: tokenChars) cs
        | _ -> 
            let rest = new string(restChars |> Array.ofList);
            failwith ("expect an close quote but failed. rest: " + rest)
    else
        match restChars with
        | []
        | '-' :: _  -> (chars2Token tokenChars, restChars)
        | '\'' :: _ -> failwith "start quote unexpected."
        | c :: cs -> readToken false (c :: tokenChars) cs

我想,经过了上面两个函数的详细说明之后,readToken函数已经没有什么特殊的语法了——可能构造字符的辅助函数char2Token算一个,它是将一个字符链表转化一个数组,再逆序后用于构造一个字符串。还有便是使用failwith抛出一个异常。readToken的逻辑应该还是非常直观的,因此我在这里没有进行注释。不过,如果您对这段内容有所疑惑的话,也可以提出,如果有较多朋友认为注释还是有必要的话,那么我也会对此进行补充。

至此,F#代码的实现就完成了,您可以在此浏览全部代码:http://gist.github.com/215256。在我看来,使用F#的模式匹配来操作链表可以得到非常紧凑而直观的代码,我们只需要按照正常的“读取思路”进行解析便可以了。做到这一点和F#的语言特性不无关系,而C#要实现这样的功能,可能就需要大量的if...else了。不过,F#的语言特性也给了一些C#编程方面的启发。此外,F#本身的这种链表操作方式也有一些天生的缺陷存在,它也是实际开发过程中不可回避的一点——不过这些话题都是有待以后讨论的内容,目前就先谈到这里吧。

F#已经明确成为.NET 4.0中的一等公民了,它的重要程度甚至高于.NET上的Python和Ruby语言实现。因为它是真正意义上一们.NET平台上从未有过的语言,一门函数式编程语言。它有许多特性可以简化我们的开发生活,我认为它很可能是未来和C#配合最为紧密的语言了。因此,如果您想要学习新的语言,不妨试着尽早开始接触F#吧。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

35 条回复

  1. 睡觉了[未注册用户]
    *.*.*.*
    链接

    睡觉了[未注册用户] 2009-10-22 01:08:00

    赵先生,请珍惜生命,早点睡觉!

    夜夜笙歌是对亲人极不负责任的一种行为!

  2. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-22 01:23:00

    F#还没看过 老赵的板凳 继续对楼上怨念

  3. 老赵
    admin
    链接

    老赵 2009-10-22 09:01:00

    @睡觉了
    我虽夜夜,但没笙歌,谢谢……

  4. 老赵
    admin
    链接

    老赵 2009-10-22 09:03:00

    @winter-cn
    F#是好东西,嗯嗯。

  5. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 09:24:00

    其实和我写的链式处理的差不多了,只不过C#没有现成的管道等运算符。其次是内部函数的运用比较巧妙。

    但总的来说,我觉得应该还有更优美的办法。

    这种解决方式的好处在于,规则小变程序也只需要小变就可以了。灵活性应该比纯粹状态机的好。

  6. 老赵
    admin
    链接

    老赵 2009-10-22 09:30:00

    @Ivony...
    嗯嗯,直接的解析做法。状态机的理解始终略有门槛,想比更适合复杂的规则。

  7. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 09:49:00

    如果在C#里面提供一些类型来完成一些辅助功能,我们用最简单自然的语法来描述这种逻辑,将会是什么样呢?

    我的设想是这样的:

    首先用纯粹的代码来描述逻辑:

    
    !inQuote :
      instance == "--" : AddGroup()
      instance == "-" : AddToken() 
      instance == "'" && tokenFirst : EnterQuote()
      instance == "'" : "'"//或者是Syntax Error?
    inQuote :
      instance == "''" && inQuote : "'"
      instance == "'" :
        tokenEnd : ExitQuote()
        other : error( "Syntax Error" )
    other : instance
    
    


    如何能最贴近这种语法呢?

  8. 老赵
    admin
    链接

    老赵 2009-10-22 09:56:00

    @Ivony...
    没看懂你的意思,我目前的设想大致是类似这样的C#模式匹配写法

    var lazyString = new LazyString(text);
    
    LazyString rest;
    char c;
    
    if (lazyString.Match('-', '-', out rest))
    {
        ...
    }
    else if (lazyString.Match('_', out c, LazyString.Empty))
    {
        ...
    }
    

    LazyString是一个对string的封装,维护一个原始string和一个起始index,这样目的是避免对string进行大量的拆分,我还倾向于把它设计为struct。

    以上是专门针对字符串的匹配方式,事实上我觉得如果在C#里实现针对通用链表的“模式匹配”,似乎也是蛮像样的。

  9. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-22 09:59:00

    Ivony...:
    如果在C#里面提供一些类型来完成一些辅助功能,我们用最简单自然的语法来描述这种逻辑,将会是什么样呢?

    我的设想是这样的:

    首先用纯粹的代码来描述逻辑:

    
    !inQuote :
      instance == "--" : AddGroup()
      instance == "-" : AddToken() 
      instance == "'" && tokenFirst : EnterQuote()
      instance == "'" : "'"//或者是Syntax Error?
    inQuote :
      instance == "''" && inQuote : "'"
      instance == "'" :
        tokenEnd : ExitQuote()
        other : error( "Syntax Error" )
    other : instance
    
    


    如何能最贴近这种语法呢?


    描述语法还是用巴斯克范式方便

  10. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 10:05:00

    
    !inQuote :
      instance == "--" : AddGroup()
      instance == "-" : AddToken() 
      instance == "'" :
        tokenFirst : EnterQuote()
        other : error( "Syntax Error" )
    inQuote :
      instance == "''" : "'"
      instance == "'" :
        tokenEnd : ExitQuote()
        other : error( "Syntax Error" )
    other : instance
    
    



    这段代码的含义是:

    如果在引号外,则
      当前是--,新增一个Group
      当前是-,新增一个Token
      当前是'则
        如在Token的开始,则进入引用
        否则语法错误
    如果在引号内,则
      当前是''添加'
      当前是',则
        如在token结尾,则退出引用
        否则语法错误
    如果以上规则都不匹配,则添加当前字符。
    

  11. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 10:15:00

    winter-cn:
    描述语法还是用巴斯克范式方便




    Google大神没找到“巴斯克范式”


    我想应该不是描述语法,如果纯粹描述语法的话,那就不如直接转换成正则去匹配了。


    不过这问题想多了也就真不如直接正则了。算鸟。

  12. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-22 10:35:00

    @Ivony...

    Ivony...:

    winter-cn:
    描述语法还是用巴斯克范式方便




    Google大神没找到“巴斯克范式”


    我想应该不是描述语法,如果纯粹描述语法的话,那就不如直接转换成正则去匹配了。


    不过这问题想多了也就真不如直接正则了。算鸟。


    不好意思 口误 是巴克斯/巴科斯
    http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

  13. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 10:44:00

    原来就是BNF,,,嗯嗯。


    话说最近玩字符串解析,我忽然想做个HTML的解析器了。

  14. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-10-22 12:11:00

    正则表达式只能描述正则语言的文法。不过老赵这道题正好是正则语言。像HTML和编程语言都不是正则语言,用正则表达式没法描述。

  15. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-10-22 12:12:00

    【广告】写Parser请使用VBF.ParserCombinator

  16. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 12:28:00

    脑袋挖坑兼广告。。。。。

  17. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-22 13:11:00

    Ivony...:
    原来就是BNF,,,嗯嗯。


    话说最近玩字符串解析,我忽然想做个HTML的解析器了。


    XHTML=XML+HTML Schema
    ^^

  18. dark
    *.*.*.*
    链接

    dark 2009-10-22 13:32:00

    话说 老赵 前段时间看你的blog中说建议我们学Python说 有利于编码规范. 于是俺去租了本Python的书,今天又建议俺们学F# ..... 我是不是要去买本F#的书? 还是乘早学F# 或者继续学Python....

  19. 老赵
    admin
    链接

    老赵 2009-10-22 13:55:00

    @dark
    我的说法是,我会建议不注意格式的人写Python,没有说建议学Python,前提要看清啊!
    当然,这次我的确建议学F#,但如果你已经在Python上投入了不少,那么就继续Python吧。

  20. 老赵
    admin
    链接

    老赵 2009-10-22 13:56:00

    装配脑袋:【广告】写Parser请使用VBF.ParserCombinator


    马鹿野狼!强烈要求更多信息。

  21. dark
    *.*.*.*
    链接

    dark 2009-10-22 14:06:00

    @Jeffrey Zhao
    那我要不要学Python - -| 哎.... 算了 都不学了.研究C#3.0设计模式罢了

  22. 老赵
    admin
    链接

    老赵 2009-10-22 14:18:00

    @dark
    要专一

  23. dark
    *.*.*.*
    链接

    dark 2009-10-22 14:29:00

    @Jeffrey Zhao

  24. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 15:51:00

    winter-cn:

    Ivony...:
    原来就是BNF,,,嗯嗯。


    话说最近玩字符串解析,我忽然想做个HTML的解析器了。


    XHTML=XML+HTML Schema
    ^^




    我说的HTML解析器,是可以解析非XML良好格式的HTML。换言之要能自动闭合标签啥的。。。。。

  25. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-22 15:53:00

    Jeffrey Zhao:

    装配脑袋:【广告】写Parser请使用VBF.ParserCombinator


    马鹿野狼!强烈要求更多信息。




    http://sourceforge.net/projects/vbf/


    不过我很确信那啥源代码定然是VB的。。。。

  26. Jeffrey Chan
    *.*.*.*
    链接

    Jeffrey Chan 2009-10-22 18:49:00

    F#的List跟Scala的List差不多,都是不可变的。Scala里面强调不可变的数据结构。赵帅能不能提供一个Scala的实现?

  27. 老赵
    admin
    链接

    老赵 2009-10-22 19:23:00

    @Jeffrey Chan
    文章里写了,这个List是“F#乃至普通函数式编程中最常见(没有之一)的数据结构”。
    Scala和F#差不多,就语法上有点不一样,自己琢磨一下吧。

  28. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-22 20:16:00

    说实话,你要是在C#里面也愿意用递归,那其实也长不了多少。那个pattern matching用string.StartWith代替就好了。

  29. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-22 20:18:00

    @Jeffrey Zhao
    以前实现过一门没有class(当然是haskell的class,不是F#那种OOP的class)的haskell,虽然那个虚拟机的效率很烂。

  30. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-22 20:19:00

    @装配脑袋
    我也写过一个ParserCombinator,可惜submit上当unit test用了,根据惯例不能拿出来献丑。

  31. 老赵
    admin
    链接

    老赵 2009-10-22 20:33:00

    vczh:说实话,你要是在C#里面也愿意用递归,那其实也长不了多少。那个pattern matching用string.StartWith代替就好了。


    StartWith只能“判断”但不能“绑定”,要绑定的话还要自己分解,所以写出来不好看。
    用各种语言,不都是为了写出来精确,紧凑,容易理解嘛。C#语言特性不够,只能为C#设计API了。

  32. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-23 09:45:00

    其实我还在期待更优美的做法,如果纯粹追求代码简短,使用正则或直接Splite会更好,这样就只需要处理单引号了。但这样效率显然不如一个一个字符读取。。。。

  33. JeeChang
    124.73.45.*
    链接

    JeeChang 2011-01-16 03:39:00

    太困了,代码没测试就提交了,不好意思。这个是测试后的。不知道效率怎么样。如果经常用的话,可以考虑把正则编译下。那样多次使用效率会好很多

    MatchCollection mc = Regex.Matches(str,
        @"(?n)(?<=^|--) 
            (
                (?<=^|-)
                    (?<push>')?
                    (?<type>
                        (?(push)
                            (?:[^']|'')+
                            |
                            [^-]+
                        )
                    )
                    (?(push)'|)
                (?(--|$)|-)
            )+
        (?=$|--) 
        ", RegexOptions.IgnorePatternWhitespace);
    
    List<string[]> result = new List<string[]>();
    foreach (Match m in mc)
    {
        List<string> s = new List<string>();
        foreach (Capture c in m.Groups["type"].Captures)
        {
            s.Add(c.Value.Replace("''","'"));
        }
        result.Add(s.ToArray());
    }
    
  34. 链接

    ClarenceAu 2012-03-28 16:40:44

    昨天从微薄上看到winter老师提到这篇文章,然后看到你写了个F#的实现. 然后想了想,就去试着用Erlang实现了一次. https://gist.github.com/2224723 功能上应该是正确的.不过感觉没你写的F#那么明了.

  35. liuyang1
    61.171.240.*
    链接

    liuyang1 2016-01-20 21:58:53

    My solution in Python, I think it's simple and clear.

    https://github.com/liuyang1/test/blob/master/lang/python/zhao/tokstr.py

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我