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

有没有更有效的方法从多行标记计算下一行/列号?

ChaosPandion · 技术社区 · 14 年前

因此,我正在使用解析器组合器构建一个lexer/解析器对,这给我留下了一些有趣的问题。现在这个问题所涉及的具体问题我已经解决了,但我对我的解决方案并不完全满意。

module Program =            

    type Token = { value:string; line:int; column:int; }

    let lineTerminators = set ['\u000A'; '\u000D'; '\u2028'; '\u2029']

    let main () =

        let token = { value = "/*\r\n *\r\n *\r\n \n */"; line = 1; column = 1; }

        let chars = token.value.ToCharArray()

        let totalLines =
            chars
            |> Array.mapi(
                fun i c ->
                    if not (lineTerminators.Contains c)  then 
                        0 
                    else
                        if c <> '\n' || i = 0 || chars.[i - 1] <> '\r' then 
                            1 
                        else 
                            0
            )
            |> Array.sum

        let nextLine = token.line + totalLines

        let nextColumn =
            if totalLines = 0 then 
                token.column + token.value.Length 
            else
                1 + (chars 
                     |> Array.rev 
                     |> Array.findIndex lineTerminators.Contains)


        System.Console.ReadKey true |> ignore

    main()

1 回复 | 直到 14 年前

Community CDub 5 年前

let terminators = [ ['\r'; '\n']; ['\r']; ['\n'] ]

顺序是重要的-如果我们先找到“\r\n”,那么我们希望跳过2个字符(这样我们就不会将下一个“\n”字符作为下一个终止符)。不幸的是 “跳过2个字符” mapi 函数,它为每个元素调用函数。

使用递归函数的直接实现可以如下所示:

let input = "aaa\nbbb\r\nccc" |> List.ofSeq

// Returns Some() if input starts with token (and the returned
// value is the rest of the input with the starting token removed)
let rec equalStart input token = 
  match input, token with
  | _, [] -> Some(input) // End of recursion
  | a::input, b::token when a = b -> equalStart input token // Recursive call
  | _ -> None // Mismatch

// Counts the number of lines...
let rec countLines count input = 
  // Pick first terminator that matches with the beginning of the input (if any)
  let term = terminators |> List.tryPick (equalStart input)
  match term, input with 
  | None, _::input -> countLines count input  // Nothing found - continue
  | None, [] -> count + 1 // At the end, add the last line & return
  | Some(rest), _ -> countLines (count + 1) rest  // Found - add line & continue

如果您使用的是某个解析器组合器库(例如 FParsec ),然后您可以使用内置的解析器来处理大多数事情。实际上我没有尝试这个,但这里有一个粗略的草图-您可以将终止符列表存储为字符串列表,并为每个字符串生成解析器:

let terminators = [ "\r\n"; "\r"; "\n" ]
let parsers = [ for t in terminators -> 
                  parser { let! _ = pstring t  
                           return 1 } ] // Return '1' because we found next line

这将为您提供一个解析器列表,在结尾有终止符时返回1—现在您可以使用 <|> (或combinator),然后运行组合解析器。如果失败,您可以跳过第一个字符(将其与另一个解析器结合起来)并递归地继续。唯一的问题是解析器组合符通常返回所有可能的派生(“\r\n”可以解释为两个换行符..),因此您需要只得到第一个结果。。。

(从你的问题来看,不清楚你是否真的想使用解析器组合器库,所以我没有详细说明这个主题-如果你感兴趣,你可以问更多细节…)