parsing - 一种解析 sexp 的优雅方式

Question

sexp 是这样的:type sexp = Atom of string | sexp 列表列表，例如，"((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"

但我认为它过于冗长和丑陋。

谁能帮我用一种优雅的方式来编写这样的解析器？

其实我写解析器的代码总是有问题，只能写这么难看。

这种解析有什么技巧吗？如何有效处理(, )等隐含递归解析的符号？

Answer 1

您可以使用词法分析器+解析器规则将词法语法的细节(主要是跳过空格)与实际语法结构分开。对于这样一个简单的语法来说，这似乎有点过分了，但实际上，只要您解析的数据有一点点出错的可能性，它就会更好:您确实需要错误定位(而不是自己实现它们)。

一种简单且提供短解析器的技术是使用流解析器(使用 Developping Applications with Objective Caml 书中描述的 Camlp4 扩展)；你甚至可以通过使用 Genlex 免费获得一个词法分析器模块。

如果你真的想手动做，就像上面的例子一样，我建议你有一个很好的解析器结构。具有相互递归的解析器，一个用于语法的每个类别，具有以下接口(interface):

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

您的代码不遵守此结构。例如，如果原子的解析器看到 (，它就会失败。这不是他的角色和责任:它应该简单地认为这个字符不是原子的一部分，并返回原子解析的-so-far，说明这个位置已经不在原子中了。

这里有一个语法代码示例。我将带有累加器的解析器分成三元组(start_foo、parse_foo 和 finish_foo)以分解多个起点或返回点，但这只是一个实现细节。

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

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

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)

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

此解析器不返回位置信息。所有现实世界的解析器都应该这样做，这足以成为使用词法分析器/解析器方法(或您首选的单子(monad)解析器库)而不是手动完成的理由。不过，这里返回位置信息并不难，一方面将 i 参数复制到当前解析字符的索引中，另一方面将第一个索引用于当前 AST 节点;无论何时产生结果，位置都是对(第一个索引，最后一个有效索引)。