녹 데이터 구조에서 재귀 EBNF 문법을 나타내는 법?

Question

다음 예제 EBNF 문법이 있다고 가정 해 봅니다. 이것은 완벽한 문법은 아니지만 문제를 올바르게 설명해야합니다. Word는 문자와 숫자의 일부 번호와 Number입니다

Statement = FunctionDefinition | Assignment | Expr ; 
Expr = { Term | "(" , Expr , ")" } ; 

Assignment = Word , "=" , Expr ; 
FunctionDefinition = Word , { Word } , "=" , Expr ; 

Term = Word | Number 

은 유효한 숫자 리터럴입니다.

나는과 같이 녹이를 표현하기 시작할 수 있습니다하지만 이미 여기에 문제가 있습니다

enum Statement { 
    FunctionDefinition { 
     name: String, 
     params: Vec<String>, 
     body: Expr, 
    }, 
    Assignment { 
     name: String, 
     body: Expr, 
    }, 
    //TODO: Expr 
} 

. Expr을 어떻게 추가합니까? Expr은 여러 다른 장소에서도 사용되기 때문에 자체 정의가 있어야합니다. Expr에 별도의 정의를 부여한 다음이 열거 형에이를 추가하면 다시 정의됩니다.

어쨌든 계속 Expr을 정의하려고 시작하면, 난 더 많은 문제로 실행 :

type Expr = Vec<...?...>; 
// or maybe... 
struct Expr { 
    terms: Vec<Expr>, // but what about Term?? 
} 

내가 Expr는 반드시이기 때문에 그 자신의 구조체 또는 열거 할 필요가 없기 때문에 type를 사용하려고 Term 또는 기타 Expr의 모음입니다. 재귀 적으로 이것을 정의하는 것은 어렵다. Expr 및 Term에 대한 공용체 형식을 에뮬레이트하기 위해 열거 형을 사용하려고하면 해당 열거 형에 Expr을 재정의해야하며 열거 형 내에 Term을 정의해야합니다.이 형식을 사용하면 다른 구조에서는 사용할 수 없게됩니다.

Answer 1

Expr은 type 별칭이 될 수 있지만 대체 번호를 나타내려면 을 정의해야합니다. Term도 별도의 enum이어야합니다.

enum Statement { 
    FunctionDefinition { 
     name: String, 
     params: Vec<String>, 
     body: Expr, 
    }, 
    Assignment { 
     name: String, 
     body: Expr, 
    }, 
    Expr(Expr), 
} 

type Expr = Vec<ExprItem>; 

enum ExprItem { 
    Term(Term), 
    Parenthesized(Expr), 
} 

enum Term { 
    Word(String), 
    Number(f64), 
}