2

sexp是这样的：type sexp = Atom of string | List of sexp list，例如，"((a b) ((c d) e) f)"。

我写了一个解析器来解析一个 sexp 字符串的类型：

let of_string s =
  let len = String.length s in
  let empty_buf () = Buffer.create 16 in
  let rec parse_atom buf i =
    if i >= len then failwith "cannot parse"
    else 
      match s.[i] with 
      | '(' -> failwith "cannot parse"
      | ')' -> Atom (Buffer.contents buf), i-1
      | ' ' -> Atom (Buffer.contents buf), i
      | c when i = len-1 -> (Buffer.add_char buf c; Atom (Buffer.contents buf), i)
      | c -> (Buffer.add_char buf c; parse_atom buf (i+1))
  and parse_list acc i =
    if i >= len || (i = len-1 && s.[i] <> ')') then failwith "cannot parse"
    else 
      match s.[i] with
      | ')' -> List (List.rev acc), i
      | '(' -> 
        let list, j = parse_list [] (i+1) in
        parse_list (list::acc) (j+1)
      | c -> 
        let atom, j = parse_atom (empty_buf()) i in
        parse_list (atom::acc) (j+1)
  in 
  if s.[0] <> '(' then
    let atom, j = parse_atom (empty_buf()) 0 in
    if j = len-1 then atom
    else failwith "cannot parse"
  else 
    let list, j = parse_list [] 1 in
    if j = len-1 then list
    else failwith "cannot parse"

但我认为它太冗长和丑陋。

有人可以用一种优雅的方式帮助我编写这样的解析器吗？

实际上，我在编写解析器代码时总是遇到问题，我只能写这么丑的一个。

这种解析有什么技巧吗？如何有效地处理暗示递归解析的符号，例如(, ？)

4

1 回答 1

7

您可以使用词法分析器+解析器规则将词法语法的细节（主要是跳过空格）与实际的语法结构分开。对于这样一个简单的语法来说，这似乎有点矫枉过正，但只要您解析的数据有最轻微的错误机会，它实际上会更好：您真的想要错误位置（而不是自己实现它们）。

一种简单且提供简短解析器的技术是使用流解析器（使用用目标 Caml 开发应用程序一书中描述的 Camlp4 扩展）；您甚至可以通过使用Genlex模块免费获得一个词法分析器。

如果您想真正手动执行，如上面的示例所示，我建议您使用一个好的解析器结构。具有相互递归的解析器，每个语法类别都有一个，具有以下接口：

  • 解析器将开始解析的索引作为输入
  • 他们返回一对解析值和第一个索引不是值的一部分
  • 而已

您的代码不尊重这种结构。例如，如果你的原子解析器看到一个(. 那不是他的角色和责任：它应该简单地认为这个字符不是原子的一部分，并返回 atom-parsed-so-far ，表明这个位置不再在原子中。

这是此样式的代码示例，适用于您的语法。我已将带有累加器的解析器拆分为三元组（start_foo和parse_foo）finish_foo以分解多个起点或返回点，但这只是一个实现细节。

我使用 4.02 的新功能只是为了好玩，匹配异常，而不是显式测试字符串的结尾。恢复到不那么花哨的东西当然是微不足道的。

最后，如果有效表达式在输入结束之前结束，则当前解析器不会失败，它只返回侧面输入的结束。这对测试很有帮助，但无论这意味着什么，你都会在“生产”中做不同的事情。

let of_string str =
  let rec parse i =
    match str.[i] with
      | exception _ -> failwith "unfinished input"
      | ')' -> failwith "extraneous ')'"
      | ' ' -> parse (i+1)
      | '(' -> start_list (i+1)
      | _ -> start_atom i
  and start_list i = parse_list [] i
  and parse_list acc i =
    match str.[i] with
      | exception _ -> failwith "unfinished list"
      | ')' -> finish_list acc (i+1)
      | ' ' -> parse_list acc (i+1)
      | _ ->
        let elem, j = parse i in
        parse_list (elem :: acc) j
  and finish_list acc i =
    List (List.rev acc), i
  and start_atom i = parse_atom (Buffer.create 3) i
  and parse_atom acc i =
    match str.[i] with
      | exception _ -> finish_atom acc i
      | ')' | ' ' -> finish_atom acc i
      | _ -> parse_atom (Buffer.add_char acc str.[i]; acc) (i + 1)
  and finish_atom acc i =
    Atom (Buffer.contents acc), i
  in
  let result, rest = parse 0 in
  result, String.sub str rest (String.length str - rest)

请注意，在解析有效表达式（您必须至少读取一个原子或列表）或解析列表（您必须遇到右括号）时到达输入末尾是错误的，但它在一个原子的末端。

此解析器不返回位置信息。所有现实世界的解析器都应该这样做，这足以成为使用词法分析器/解析器方法（或您首选的单子解析器库）而不是手动完成的理由。在这里返回位置信息并不是很困难，但是，只需将i参数复制到当前解析字符的索引中，另一方面，将用于当前 AST 节点的第一个索引；每当您产生结果时，位置就是对 ( first index, last valid index)。

于 2014-05-25T14:49:01.243 回答