二进制表达式的递归模式匹配，非常接近

Question

我试图做一些简单的语义分析，并有一个困难的时间设置我的模式匹配正确。这是我的实际代码的一个淡化的例子，但它仍然抓住了思想。

type expr = LiteralInt of int 
      | LiteralString of string
      | Binop of expr * op * expr 
   and op = Add | Mult 
let rec expr_check = function 
    | Binop(LiteralInt(e1), _, LiteralString(e2)) -> false 
    | Binop(LiteralString(e1), _, LiteralInt(e2)) -> false
    | Binop(LiteralInt(e1), _, LiteralInt(e)) -> true
    | Binop(l, _, LiteralInt(a)) -> expr_check l 
    | Binop(l, _, LiteralString(a)) -> expr_check l
    | Binop(LiteralInt(e1), _, l) -> expr_check l
    | LiteralInt(a) -> true
    | LiteralString(a) -> true 
(* Should be false *)
let first_check = expr_check (Binop(LiteralInt(1), Add, LiteralString("hi")));;
(* Should be false for: 4 + 5 + "hello" *)
let second_check = expr_check (Binop(Binop(LiteralInt(4), Add, LiteralInt(5)), Add, LiteralString("hello")))

我也试过这个，但它也不起作用。

let rec expr_check = function 
    | Binop(LiteralInt(e1), _, LiteralString(e2)) -> false 
    | Binop(LiteralString(e1), _, LiteralInt(e2)) -> false
    | Binop(LiteralInt(e1), _, LiteralInt(e)) -> true
    | Binop(l, _, b) -> expr_check l && expr_check b
    | LiteralInt(a) -> true
    | LiteralString(a) -> true 

Answer 1

在我看来，您需要传播有关子树类型(用您的语言)的信息。你不能像你现在做的那样，只拿字面意思来比较。有时两个子树都不是文字。

您可能能够使用奇特的OCaml类型将语言的类型拉到OCaml类型系统中。但是直接的方法是将类型作为值携带。

type mytype = Mystring | Myinteger

这就是我要说的。我是否正确是另一回事:-)

假设您的输入看起来像这样(以通常的表达式形式):

("abc" + "def") + (3 + 5)

据我所知，你的模式都不会注意到这是错误的。内部节点的正确性并不仅仅基于子节点的正确性。它取决于子节点的类型。

Answer 2

好的，基于Jeffrey的回答和IRC上的一些帮助，谢谢Drup!，这是我最后做的一个子集。

exception SemanticError of string 
type typ = TInt | TString
(* Not an exhaustive match *)
let rec infer_typ = function
  | LiteralInt _ -> TInt
  | LiteralString _ -> TString
  | Binop (e1, op, e2) ->
      let (t1, t2, ret_typ) = infer_op_typ op in
      if check_expr e1 t1 && check_expr e2 t2
      then ret_typ (* Make this more informative *)
      else raise (SemanticError "Type problem with: ")
  | _ -> TInt 
and infer_op_typ = function
  | Add | Mult | Sub | Mult | Div | Equal | Neq | Less | Leq | Greater | Geq -> (TInt, TInt, TInt)
and check_expr e typ =
  let inf_typ = infer_typ e in
  typ = inf_typ

有更多的代码，但这至少是与回答这个问题相关的代码。