OCaml 期望在模式匹配期间不会出现在任何地方的模式

Question

行

Concat((a,b)) -> let x = regexp_to_nfa a and y = regexp_to_nfa b in match x.fs with [t] ->

报错

37 |   Concat((a,b)) -> let x = regexp_to_nfa a and y = regexp_to_nfa b in match x.fs with [t] ->
       ^^^^^^^^^^^^^
Error: This pattern matches values of type regexp_t
       but a pattern was expected which matches values of type
         int list * int list

为什么编译器会认为 int list * int list 需要匹配，而 a、b 显然需要类型 regexp_t 以便 regexp_to_nfa 函数使用它们？

有类似错误的问题表明该错误源于先前具有类型 int list * int list 的表达式。但是，如果我将 Concat 行移动到开头（在 Empty_String -> 之前），我会得到错误

33 |   Empty_String -> let x = fresh() and y = fresh() in
       ^^^^^^^^^^^^
Error: This variant pattern is expected to have type int list
       The constructor Empty_String does not belong to type list

，这表明 Concat((a,b)) 或使用它的行中的某些内容具有类型 int list，这更没有意义。

作为参考，这些是我正在使用的类型和我正在尝试调试的函数的代码：

type ('q, 's) transition = 'q * 's option * 'q
type ('q, 's) nfa_t = {
    sigma : 's list;
    qs : 'q list;
    q0 : 'q;
    fs : 'q list;
    delta : ('q, 's) transition list;
}

type regexp_t =
  | Empty_String
  | Char of char
  | Union of regexp_t * regexp_t
  | Concat of regexp_t * regexp_t
  | Star of regexp_t

let fresh =
  let cntr = ref 0 in
  fun () ->
    cntr := !cntr + 1 ;
    !cntr

let rec regexp_to_nfa (regexp: regexp_t) : (int, char) nfa_t = match regexp with
  Empty_String -> let x = fresh() and y = fresh() in 
  {sigma = []; qs = [x;y]; q0 = x; fs = [y]; delta = []}|
  Char(a) -> let x = fresh() and y = fresh() in 
  {sigma = [a]; qs = [x;y]; q0 = x; fs = [y]; delta = [(x,Some a,y)]}|
  Union((a,b)) -> let x = regexp_to_nfa a and y = regexp_to_nfa b and r = fresh() and s = fresh() in match (x.fs, y.fs) with ([t],[u]) -> 
  {sigma = Sets.union x.sigma y.sigma; qs = Sets.union (Sets.union x.qs y.qs) [r;s]; q0 = r; fs = [s]; 
  delta = Sets.union (Sets.union x.delta y.delta) [(r, None, x.q0); (r,None,y.q0); (t,None,s); (u,None,s)]}|
  Concat((a,b)) -> let x = regexp_to_nfa a and y = regexp_to_nfa b in match x.fs with [t] -> 
  {sigma = Sets.union x.sigma y.sigma; qs = Sets.union x.qs y.qs; q0 = x.q0; fs = y.fs; 
  delta = Sets.union (Sets.union x.delta y.delta) [(t,None,y.q0)]} |
  Star(a) -> let x = regexp_to_nfa a and r = fresh() and s = fresh() in match x.fs with [t] -> 
  {sigma = x.sigma; qs = Sets.union x.qs [r;s]; q0 = r; fs = [s]; 
  delta = Sets.union x.delta [(r, None, x.q0);(r,None,s);(s,None,r);(t, None, r)]}

Answer 1

您有一个嵌套 match。因此，Concat 模式被解析为嵌套匹配的一部分。

您需要使用 begin/end 或括号来隔离嵌套在另一个 match.

中的 match

如果您继续使用嵌套匹配，您还需要处理 (x.fs, y.fs) 不具有预期形式的情况（即其中一个列表的长度不是 1 的情况） .如果您确定它们永远不会为空，您可以这样重写：

Union((a,b)) ->
    let x = regexp_to_nfa a
    and y = regexp_to_nfa b
    and r = fresh()
    and s = fresh() in
    { sigma = Sets.union x.sigma y.sigma;
      qs = Sets.union (Sets.union x.qs y.qs) [r;s];
      q0 = r;
      fs = [s]; 
      delta = Sets.union (Sets.union x.delta y.delta)
                    [(r, None, x.q0);
                     (r, None, y.q0);
                     (List.hd x.fs, None, s);
                     (List.hd y.fs, None, s)]
    }|
Concat((a,b)) -> . . .

（值得一提的是，您使用的是一种极其密集的编码风格。恕我直言，最好将格式设置得更松散一点，或者甚至使用格式设置工具自动布置代码。）

OCaml 期望在模式匹配期间不会出现在任何地方的模式

OCaml expects pattern which doesn't appear anywhere during pattern matching

ocaml

types

pattern-matching