递归函数处理拆分字符串出错：OCaml析取式转换函数语法问题

给定如下格式的字符串：

"+x1 +x2 -x3
+x4      +x5 -x6
..."

以及OCaml定义的谓词逻辑公式类型：

type formula =
  | Bot
  | Top
  | Atom of string
  | Imp of (formula * formula)
  | Or of (formula * formula)
  | And of (formula * formula)
  | Not of formula

let atom x = Atom x

需求是编写一个函数，接收一行字符串，拆分后转换为析取式（比如第一行输入应生成类似Or(Atom "x1", Atom "x2", Not(Atom "x3"))的嵌套结构）。

我编写了以下代码：

let string_to_disj st =
  let lst = Str.split (Str.regexp " \t") st in
  let rec total lst = 
    match lst with
    | [] -> Or (Bot, Bot) (*Is this correct btw?*)
    | h :: t -> Or (string_to_lit h, total t);;

辅助函数定义如下：

let string_to_lit = 
  match String.get s 0 with
  | '+' -> atom (String.sub s 1 (String.length s-1))
  | '-' -> Not(atom(String.sub s 1 (String.length s-1)))
  | _ -> atom(s);;

但string_to_disj函数在| h :: t -> Or (string_to_lit h, total t)行触发语法错误，请问我哪里出错了？

你的代码存在语法和逻辑层面的多个问题，逐一说明并修正：

1. 辅助函数string_to_lit的语法错误 #

string_to_lit定义时未声明参数，直接使用了未定义的变量s，正确写法需要将s作为函数参数传入：

let string_to_lit s = 
  match String.get s 0 with
  | '+' -> atom (String.sub s 1 (String.length s - 1))
  | '-' -> Not (atom (String.sub s 1 (String.length s - 1)))
  | _ -> atom s

2. string_to_disj的语法错误 #

OCaml中局部递归函数需要用let rec ... in的完整结构闭合，你的代码写完total的匹配分支后直接用;;结束，没有添加in来调用局部函数，导致语法结构不完整。

3. 析取式的逻辑错误 #

• 空列表返回Or(Bot, Bot)不符合语义：空析取式等价于Bot（没有任何析取项为真），而非两个Bot的析取。
• 原正则表达式" \t"会把连续空白符拆分成多个空字符串元素，导致后续处理出错，需要改用"[ \t]+"匹配一个或多个空白字符，得到干净的字面量列表。
• 单个元素的场景可以直接返回对应字面量，避免多余的Or嵌套。

修正后的完整代码 #

open Str

type formula =
  | Bot
  | Top
  | Atom of string
  | Imp of (formula * formula)
  | Or of (formula * formula)
  | And of (formula * formula)
  | Not of formula

let atom x = Atom x

let string_to_lit s = 
  match String.get s 0 with
  | '+' -> atom (String.sub s 1 (String.length s - 1))
  | '-' -> Not (atom (String.sub s 1 (String.length s - 1)))
  | _ -> atom s

let string_to_disj st =
  let lst = Str.split (Str.regexp "[ \t]+") st in
  let rec total lst = 
    match lst with
    | [] -> Bot
    | [h] -> string_to_lit h
    | h :: t -> Or (string_to_lit h, total t)
  in total lst

内容的提问来源于stack exchange，提问作者Ld B