一种解析sexp的优雅方式

Question

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"

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

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

实际上,我总是在编写解析器代码时遇到问题,而我只能编写这样一个丑陋的代码.

这种解析的任何技巧？如何有效应对符号,如(,)即意味着递归解析？

Answer 1

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

一种简单且提供简短解析器的技术是使用流解析器(使用Camlp4扩展,在开发应用程序与Objective Caml一书中描述); 您甚至可以使用Genlex模块免费获得词法分析器.

如果你想真正做手动,如上例所示,我建议你有一个很好的解析器结构.使用以下接口,为每个语法类别提供相互递归的解析器:

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

您的代码不尊重此结构.例如,如果遇到原子,则原子的解析器将失败(.这不是他的角色和责任:它应该只考虑这个角色不是原子的一部分,并返回原子解析的那么远,表明这个位置不再存在于原子中.

以下是此语法的代码示例.我曾与三元蓄电池拆分解析器(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)

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

此解析器不返回位置信息.所有真实世界的解析器都应该这样做,这足以成为使用词法分析器/解析器方法(或您首选的monadic解析器库)而不是手动执行的理由.这里返回位置信息并不是非常困难,但是,i一方面将参数复制到当前解析的字符的索引中,另一方面复制用于当前AST节点的第一个索引; 无论何时生成结果,位置都是对(first index,last valid index).