무손실 구문 트리

그래서 프로그래밍 언어를 해석하고 싶어요.일부 텍스트를 사용자가 작성한 프로그램 구조를 나타내는 의미 데이터 구조로 바꾸기를 원합니다.
그러나 당신은 도대체 어떻게 이런 의미 모델을 세웠습니까?해석 트리(구체적 문법 트리 또는 CST라고도 부른다)는 ANTLR와 같은 문법 기반 해석 도구가 일반적으로 이 목적을 위해 생성된다.이는 잘못된 뜻을 없애는 데 쓰이는 무의식적인 문법을 포함하지만 빈칸이나 주석 같은 어느 곳에서든 허용되는 자질구레한 일은 포함하지 않는다.이런 방법에 대한 전통적인 개선은 anAbstract Syntax Tree이라고 하는데 줄여서AST라고 하는데 문법에서 의미가 있는 부분만 모델링한다.
그러나 IDE 컴파일러에 대해 우리는 두 가지 관건적인 속성을 실현해야 한다. 해석기는 용착성이 있어야 하고 순환이 가능해야 한다.우리는 불완전하거나 부정확한 입력에 직면하더라도 문법 트리를 생성해야 하기 때문에 진행 중인 코드에 문법적 하이라이트 디스플레이와 완성 등의 기능을 제공할 수 있다.IDE의 코드는 작성할 때 대부분의 시간을 불완전하게 보냅니다.roundtrippable에 대해 IDE에서 문법 트리를 변환하고 형식과 주석 등 내용을 유지하기를 희망합니다.이 두 가지 속성을 얻기 위해 우리는 rowan를 사용한다. 이것은 라이브러리로 업데이트된 문법 트리 설계를 실현했다. 이를 무손상 문법 트리†라고 부른다.
Rowan LST의 관건적인 기교는 동적 유형의 CST를 구성하는 것이다. 이렇게 하면 우리는 CST에서 구조화된 유형의AST 보기를 제공할 수 있다.CST의 비유형화 특성도 우리의 용착성을 나타낸다. 모든 노드에 임의의 하위 노드가 있을 수 있다. 우리의 해석기가 충분하면 어느 노드가 어디에 있는지 찾아낼 수 있다.
이것은 사용한red-green tree처럼 한 종류in Roslyn를 사용했다.녹색 트리는 CST로서 일반적인 단일 체인 트리와 유사합니다. 각 노드에는 하위 노드의 목록이 있습니다.트리는 노드의 텍스트 너비 옆에 하나만 저장하기 때문에 동적 형식입니다. #[repr(u16)] enum SyntaxKind붉은 나무는 녹색 나무의 보기이고 녹색 나무는 필요에 따라 동적 구조로 되어 있으며 부모 지침과 절대 편이량을 포함한다.AST층은 주어진 노드에 대한 작업을 수행하기 위해 빨간색 트리에 추가 형식 정보를 추가합니다. 모든 액세서리가 구체적인 트리의 동태성을 표시하기 위해 Option 를 되돌려야 하기 때문에 잘못된 원본 코드를 표시할 수 있습니다.
이 점에 대한 컴파일러를 구축하려면 먼저 재구성을 해야 한다.지금까지 설계는 믿을 만하지만, 일부 조정은 해석기를 위해 준비할 것이다.우선, 우리는 유행이 지난 의존항을 업데이트해야 한다. cargo upgrade --all --allow-prerelease는 이 기교를 실현했고 본문을 작성할 때[email protected]를 [email protected]로 업그레이드하기만 하면 된다.
이제 우리가 사용하고 있는 문법을 살펴보자.

Program = Statement*;
Statement =
  | If:{ "if" cond:(Expression::Parenthesized) then:Statement { "else" else:Statement }? }
  | While:{ "while" cond:(Expression::Parenthesized) then:Statement }
  | Block:{ "{" then:Statement* "}" }
  | Expression:{ then:Expression? ";" }
  ;
Expression =
  | Parenthesized:{ "(" Expression ")" }
  | Assignment:{ id:Identifier "=" val:Expression }
  | Comparison: #[associativity(left)] { lhs:Expression "<" rhs:Expression }
  | Addition: #[associativity(left)] { lhs:Expression "+" rhs:Expression }
  | Subtraction: #[associativity(left)] { lhs:Expression "-" rhs:Expression }
  | Term:Term
  ;
Term =
  | Identifier:Identifier // token
  | Integer:Integer // token
  | Expression:(Expression::Parenthesized)
  ;

(만약 이 내용을 발표할 때 계속 관심을 가지고 있다면, 이것은 내가 지금까지 사용한 문법과 다르다는 것을 알 수 있습니다. 이것은 해상도를 실현하기 시작하고 개선점을 찾은 것입니다.)
여기서 우리는 하나Program가 0 개 또는 여러 개Statement로 구성된 것을 보았다.aStatement는Statement::If,Statement::While,Statement::Block 또는Statement::Expression이다.화Statement::If는 하나의 문자if, 그 뒤에 하나Expression::Parenthesized와 하나Statement, 선택할 수 있는 뒤에 한 문자else와 다른 하나Statement이다.이것은 정확한 나무의 구조를 묘사하였다.종결되지 않은 기호를 syntax.toml에 추가합니다.

nonterminals = [
    "program",
    "statement if",
    "statement while",
    "statement block",
    "statement expression",
    "expression parenthesized",
    "expression assignment",
    "expression comparison",
    "expression addition",
    "expression subtraction",
    "expression term",
    "term identifier",
    "term integer",
    "term expression",
]

또한 나는 error 클래스를 메타데이터 파일에 열거된 내용에서 템플릿 파일의 마지막으로 명확하게 열거된 내용으로 업그레이드했다.비록 이것은 일종의 노드 유형이지만 적당한 나무의 실제 노드와 다르기 때문에 특수 처리를 해야 한다.현재 우리는 기존의 SyntaxKind 를 TokenKind 로 바꾸어 영패에 사용된 것임을 밝히고 SyntaxKind 비단말기를 포함하는 새 템플릿을 만들어야 한다.

{%- set empty = [] -%}
// Separate variables for terminals and nonterminals
{%- set terminals = empty
    | concat(with=keywords)
    | concat(with=literals)
    | concat(with=punctuation | map(attribute="name"))
    | concat(with=tokens)
-%}
{%- set all_kinds = empty
    | concat(with=terminals)
    | concat(with=nonterminals)
-%}

#[repr(u16)]
#[allow(missing_docs)]
// Add serde to runtime dependencies.
// TokenKind should impl `Serialize` as well.
#[derive(serde::Serialize)]
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub enum SyntaxKind {
    {%- for kind in all_kinds %}
    {{ kind | camel_case }},
    {%- endfor %}
    ERROR,
}

impl SyntaxKind {
    /// The name of this syntax kind.
    pub fn name(self) -> &'static str {
        match self {
            {%- for kind in all_kinds %}
            SyntaxKind::{{ kind | camel_case }} => "{{ kind | camel_case }}",
            {%- endfor %}
            SyntaxKind::ERROR => "ERROR",
        }
    }
}

// We need to convert from TokenKind to SyntaxKind.
// This could be explicitly zero-cost by using a transmute,
// but we stick here to the safe version and let it optimize.
impl From<TokenKind> for SyntaxKind {
    fn from(token: TokenKind) -> SyntaxKind {
        match token {
            {%- for kind in terminals %}
            TokenKind::{{ kind | camel_case }} => SyntaxKind::{{ kind | camel_case }},
            {%- endfor %}
            TokenKind::ERROR => SyntaxKind::ERROR,
        }
    }
}

// For rowan, we also want conversions to/from u16.
impl From<SyntaxKind> for u16 {
    fn from(kind: SyntaxKind) -> u16 {
        kind as u16
    }
}

// This could be explicitly zero-cost by using a transmute,
// but we stick here to the safe version and let it optimize.
impl From<u16> for SyntaxKind {
    fn from(raw: u16) -> SyntaxKind {
        match raw {
            {%- for kind in all_kinds %}
            {{ loop.index }} => SyntaxKind::{{ kind | camel_case }},
            {%- endfor %}
            _ => SyntaxKind::ERROR,
        }
    }
}

또한 Token 패브릭을 tinyc_lexer에서 tinyc_grammar로 가져와 tinyc_lexer에서 다시 내보내기를 원합니다.

use serde::ser::{Serialize, Serializer};

include!(concat!(env!("OUT_DIR"), "/token_kinds.rs"));
include!(concat!(env!("OUT_DIR"), "/syntax_kinds.rs"));

#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct Token {
    pub kind: TokenKind,
    pub len: u32,
}

impl Serialize for Token {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_variant(
            "Token",
            u16::from(self.kind).into(),
            self.kind.name(),
            &self.len,
        )
    }
}

이것은 tinyc_grammar 원시 데이터 상자에 사용되는 쪽지 상자입니다. tinyc_lexer 이것은 우리가lexer를 실현하는 쪽지 상자입니다.다른 판자 상자는 쉽게 소비할 수 있을 뿐만 아니라Tokenlexer에 의존할 필요가 없다.
이러한 개선을 통해 우리는 다음부터 해상도를 실현할 준비가 되어 있다.
Discuss this below! | See the result on GitHub!
이번에 나는 코드 밀도 방면에서 어떻게 했습니까?지난번에 나는 코드가 너무 많다고 생각했기 때문에 이번에는 구체적인 실현이 아니라 개념에 중점을 두려고 했다.
† 특정 구문 트리라는 손상되지 않은 구문 트리도 볼 수 있습니다.이 개념에 대해 저는 LST를 더 좋아합니다. 왜냐하면 해석 트리는 어느 정도에 LST가 아니라 CST라고 불리기 때문입니다.일반적으로 LST는 문법 트리라고도 간단하게 불린다.구문 트리가 CST, AST 또는 LST를 나타낼지는 컨텍스트에 따라 다릅니다.물론 이 세 가지 유형 사이에 있는 다른 문법 트리 방법도 있다.
실제로 로완은 내부에 하나struct SyntaxKind(u16)를 사용하고 사용자의 문법 종류와 더 높은 단계에서 매거진적으로 전환했다.이것은 일반적인 확산을 줄이고 라이브러리 사용자가 필요할 때 C 스타일보다 더 복잡한 구와 유형을 사용할 수 있도록 한다.

관련 읽기

마테클라드Modern Parser Generator

녹식분석기architecture overview

[비디오] rust analyzer syntax trees

녹슬기"libsyntax 2.0" RFC

케이스 회사From AST to Lossless Syntax Tree

사례 연구:

JetBrains Program Structure Interface

코틀린PSI

스위프트libSyntax

녹식분석기ra_parser와ra_syntax

로즈린