AST 용 트리 구조

Question

나는 C#에서 인터프리터를 작성하려고하는데 파싱 단계입니다. 이 시점에서 Abstract Syntax Tree를 생성해야한다는 것을 알았지 만 C#으로 표현하는 방법을 모르겠습니다.

현재 나는 단지 List<object>을 사용하고 있지만 잘못하고 있다고 느낍니다.

고마워요.

Answer 1

"노드"유형 - "유형"태그가있는 필드의 큰 버킷 - 특정 클래스의 세부적인 계층 구조에 이르기까지 다양한 기술이 있습니다. 중요한 것은 트래버스 코드를 간단하고 강력하게 만드는 방법에 대해 생각하는 것입니다. 왜냐하면이 데이터 구조를 반복해서 탐색해야하기 때문입니다.

그러나 한 걸음 뒤로 물러나면 해석에 엄격하게 AST가 필요하지 않습니다. 많은 초기의 인터프리터는 스택을 기반으로하는 책 마킹 시스템을 통해 구현 된 코드 라인을 문자 그대로 읽거나, 파싱하고, 실행하거나, 루프 등으로 문자 그대로 읽습니다. 필자는 bash와 cmd.exe 같은 쉘 언어가 아직 이대로 작동하고 있다고 생각합니다.

Answer 2

대부분의 AST 노드 구현은 매우 간단합니다.

노드 유형 (일반적으로 정수), 하위 목록 (List는 정상이며 고성능 구현에는 통계적으로 공통 인 1st, 2nd , 세 번째 자식) 및 AST 노드 인스턴스에 특정한 값을 전달하기위한 몇 가지 추가 필드 (예 : AST 노드 "정수 상수"의 값 "5"). 어떤 노드에서부터 부모 노드까지 트리를 효율적으로 탐색 할 수 있도록하기 위해 종종 부모 노드에 대한 특별한 참조가 있습니다.

무엇을 가져야하는지 집합을 결정하는 것이 더 어렵습니다. 큰 문법의 경우 수백 개의 문구 집합을 정의해야하므로 불편합니다. 올바른 문법을 시도 할 때 문법을 수정할 때 문제가 발생합니다.

간단한 트릭은 문법 규칙에 따라 하나의 AST 노드를 정의하는 것입니다. (이것은 대부분 "구체적인 구문 트리"라고합니다). 그러나 그것은 두뇌가 없으며 당신은 무엇이든 놓치지 않습니다.

우리의 DMS Software Reengineering Toolkit은 문법 규칙에서 AST 노드 유형을 dirrectly 생성이 "간단한 트릭"아이디어를 따릅니다. 또한 값을 가지고 있지 않은 리프 AST 노드가 트리에 존재하지 않으며 단항 프로덕션의 노드가 트리에 존재하지 않으며 목록 생성 프로덕션에는 하위의 List 스타일이 있고 다른 노드 유형에는 아이들을위한 고정 슬롯 유형. 결과적으로 어쨌든 "추상적 인"구문 트리에 꽤 가까운 것입니다. 이 모든 것은 DMS 파서 생성기에 의해 자동으로 생성되므로 전혀 생각할 필요가 없습니다.

DMS에는 또한 잘 테스트 된 C# 4.0 프런트 엔드가 있습니다. AST를 정의하는 데 어려움을 겪으면 분석/변형/생성하고 DMS의 나머지 부분이 갑자기 분명히 가치가있게됩니다.

Answer 3

이 제한 사항과 사용자의 요구 사항이 무엇인지 명확하게 이해할 때까지 계속 List<object>을 사용하는 것이 좋습니다. 당신이 LISP 인터프리터를 작성하기 때문에 또는, 한 쌍의 클래스를 만들고와 object, null이 '()에 해당되는 것을 사용합니다

public sealed class Pair 
{ 
    public object Car ; 
    public object Cdr ; 
} 

는 S-식에 직접 입력을 구문 분석하고 직접와 통역 일이 그. 어쨌든 LISP는 ASTs 이전에 존재했습니다!