OCaml에서 구문 트리를 추출하기위한 S- 표현 트리

Question

OCaml에서 심볼릭 언어를 구현 중이며 s- 표현식 트리를 추상 구문 트리로 변환하는 데 어려움을 겪고 있습니다.

의 S-식 트리가 추상 구문 트리가

(* ast.ml *) 
open Sexpr 

type sym = string 

(* abstract syntax tree nodes *) 
type expr = 
    | Expr_unit 
    | Expr_int of int 
    | Expr_sym of sym 

(* Sexp.atom -> Ast.expr *) 
let ast_of_atom a = 
    match a with 
     | Atom_unit -> Expr_unit 
     | Atom_int n -> Expr_int n 
     | Atom_sym s -> Expr_sym s 

(* Sexp.expr -> Ast.expr *) 
let rec ast_of_sexpr sx = match sx with 
    | Expr_atom a -> ast_of_atom a 
    | Expr_list l -> 
    match l with 
     | [] -> ast_of_atom Atom_unit 
     | [x] -> ast_of_sexpr x 
     | h::t -> ignore (ast_of_sexpr h); ast_of_sexpr (Expr_list t) 

유형 서명

val ast_of_sexpr : Sexpr.expr -> expr을 준수 할 필요가 ast_of_sexpr 기능입니다

(* sexpr.mli *) 
type atom = 
    | Atom_unit 
    | Atom_int of int 
    | Atom_sym of string 

type expr = 
    | Expr_atom of atom 
    | Expr_list of expr list 

입니다.

이것은 나의 도전 과제입니다. 유형 서명을 준수하는 방법을 알아내어 s- 표현식 트리 (즉, 중첩 된 목록)로 재귀 적으로 표현하고 s- 표현식 트리 노드를 추상 구문 트리 노드로 변환 할 수 없습니다.

이상적인 세계에서 나는 목록 머리를 평가하고 꼬리를 한 표현으로 되풀이 할 수 있습니다. 이 이상을 시퀀싱을 사용하여 에뮬레이트하려고했습니다. 그러나 이것은 물론 왼쪽 값을 무시하고 파싱 된 토큰 스트림을 인쇄 할 때 마지막 값만 출력합니다.

누구나 값을 무시하지 않고 의 머리글을 평가하는 방법을 제안하고 s- 표현 트리를 더 자세히 재귀 할 수 있습니까? 나는 두 나무 사이를 번역 할 때 더 나은 해결책을 읽을 수 있습니다. 나는 이것이 당신이 요구하는지 모르겠어요

let v = <calculate> in 
let w = <calculate> in 
<expression using v and w> 

하지만,이 사람들이 OCaml의로 시작하는 개념 어려움입니다 :

Answer 1

Ast.expr 형식 정의가 틀린 것처럼 보입니다. 추상 구문 트리가 아니라 원자 표현식의 구문을 나타냅니다. 이것은 유형이 재귀 적이 아니기 때문에 유형이라고 할 수 없습니다. 이에 비해 Sexp.expr은 재귀 유형입니다. 이 작업이 완료되면

type expr = 
    | Expr_unit 
    | Expr_int of int 
    | Expr_sym of sym 
    | Expr_call of expr list 

는 두 가지 유형이 실질적으로 동일하므로 변환은 간단하게 :

내 생각 엔 당신이 예를 들어, 타입 정의 경우를 잊고 있다는 것입니다.

Answer 2

은 매우 일반적으로, 여기 "를 무시하지 않고"일부 값을 계산하는 방법 (IMHO).