具有循环函数依赖性的递归匹配函数

Question

我不确定标题是否解释了我的问题，但是在我想解释我的问题之后我可以改进它，因为几天来我都在为这个问题而烦恼。

我正在使用 Ocaml 为我的 class 开发静态分析，以检查我的 c（C 语言的子集）程序是否意味着真实的东西，我是新手（使用语言和范例以及编译器的东西）。

静态分析正在遍历抽象语法树 (Ast) 并对其进行一些检查（检查是 TODO 注释的问题），目前我正在开发数据结构，特别是 Symbol Table，实现遍历Ast的代码。

我的完整 Ast.

type binop = Add | Sub | Mult | Div  | Mod | Equal | Neq | Less | Leq |
             Greater | Geq | And | Or | Comma
             [@@deriving show]

type uop = Neg | Not [@@deriving show]

type identifier = string [@@deriving show]

type position = Lexing.position * Lexing.position
let dummy_pos = (Lexing.dummy_pos, Lexing.dummy_pos)

type 'a annotated_node = {loc : position[@opaque]; node : 'a}[@@deriving show]

type typ =
  | TypInt                             (* Type int                    *)
  | TypBool                             (* Type bool                   *)
  | TypChar                             (* Type char                   *)
  | TypArray of typ * int option         (* Array type                  *)
  | TypPoint of typ                      (* Pointer type                *)
  | TypVoid                             (* Type void                   *)
  [@@deriving show]

and expr =  expr_node annotated_node
and expr_node =
  | Access of access                 (* x    or  *p    or  a[e]     *)
  | Assign of access * expr          (* x=e  or  *p=e  or  a[e]=e   *)
  | Addr of access                   (* &x   or  &*p   or  &a[e]    *)
  | ILiteral of int                  (* Integer literal             *)
  | CLiteral of char                 (* Char literal                *)
  | BLiteral of bool                 (* Bool literal                *)
  | UnaryOp of uop * expr            (* Unary primitive operator    *)
  | BinaryOp of binop * expr * expr  (* Binary primitive operator   *)
  | Call of identifier * expr list   (* Function call f(...)        *)
  [@@deriving show]

and access = access_node annotated_node
and access_node =
  | AccVar of identifier             (* Variable access        x    *)
  | AccDeref of expr                 (* Pointer dereferencing  *p   *)
  | AccIndex of access * expr        (* Array indexing         a[e] *)
  [@@deriving show]

and stmt = stmt_node annotated_node
and stmt_node =
  | If of expr * stmt * stmt         (* Conditional                 *)
  | While of expr * stmt             (* While loop                  *)
  | For of expr option * expr option * expr option * stmt (* For loop *)
  | Expr of expr                     (* Expression statement   e;   *)
  | Return of expr option            (* Return statement            *)
  | Block of stmtordec list          (* Block: grouping and scope   *)
  [@@deriving show]

and stmtordec = stmtordec_node annotated_node
and stmtordec_node =
  | Dec of typ * identifier          (* Local variable declaration  *)
  | Stmt of stmt                     (* A statement                 *)
  [@@deriving show]

type fun_decl = {
  typ : typ;
  fname : string;
  formals : (typ*identifier) list;
  body : stmt;
}[@@deriving show]

type topdecl = topdecl_node annotated_node
and topdecl_node =
  | Fundecl of fun_decl
  | Vardec of typ * identifier
  [@@deriving show]

type program = Prog of topdecl list [@@deriving show]

我的问题是如何遍历 stmt 因为里面包含 Block of stmtordec list 和 stmtordec 并且有 stmt 在这种情况下，我在我无法使用匹配函数解决的循环依赖。

我想遍历它是有一个 OCaml 函数 check_stm -> check_blk -> check_stm，但是我如何用代码解决这个想法？

目前我的代码就是这样，但不要编译器，因为我无法同时将函数放入 OCaml 范围。

我的代码是

open Ast
open Symbol_table
open Easy_logging

let logger = Logging.make_logger "Semant" Debug [Cli Debug]

(* Global Scope: This scope contains all the Global declaration
   Global declaration types:
   - Int, Bool, Char, Array.
   - Struct
   - function declaration
*)

let global_scope = empty_table

let check_blk blkstm =
  match blkstm.node with
  | Ast.Dec(tipe, id) ->
    begin
      logger#debug "Variable declaration check";
      (* TODO: I'm missing the variable duplication *)
      Symbol_table.add_entry id tipe global_scope
    end
  | Ast.Stmt(stm) ->
    begin
      logger#debug "Stm check (recursive call)";
      check_stm stm
    end

let check_stm node =
  match node with
  | Ast.If(ex, ifs, els) -> logger#debug "TODO: If stm check"
  | Ast.While(ex, stm) -> logger#debug "TODO: While stm check"
  | Ast.For(ex1, ex2, ex3, stm) -> logger#debug "TODO: For stm check"
  | Ast.Expr(ex) -> logger#debug "TODO: Expression check"
  | Ast.Return(optex) -> logger#debug "TODO: Return stm check"
  | Ast.Block(blkstm) -> List.iter check_blk blkstm


let check_fundec node =
  match node with
  | fun_decl as f ->
    begin
      logger#debug "Checking function declaration";
      (* TODO: how I can managed the parameter of the function?*)
      global_scope = Symbol_table.begin_block global_scope;
      check_stm f.body.node
    end


let rec match_type ast_elem =
  match ast_elem.node with
  | Vardec(tipe, id) ->
    begin
      logger#debug "Global variable found";
      add_entry id tipe global_scope;
      ()
    end
  | Fundecl(fundec) ->
    begin
      logger#debug "Function analysis found";
      Symbol_table.add_entry fundec.fname fundec.typ global_scope;
      check_fundec fundec;
    end


let check (Ast.Prog(topdecls)) = List.iter match_type topdecls

也许这个问题很愚蠢，也许我的想法有问题，但我想谈谈这个问题来解决它并学习如何使用OCaml语言

p.s：目前 Symbol_table 实现是一个空实现

Answer 1

如果我正确理解你的问题，你只需明确指定相互递归函数即可。您可以使用 and 关键字来执行此操作，就像使用类型定义一样，但还必须使用 rec 关键字，因为默认情况下函数定义不是递归的，这与类型定义不同：

let rec check_blk blkstm = ...

and check_stm node = ...

具有循环函数依赖性的递归匹配函数

Recursive match function with cyclic function dependences

ocaml