Какое самое идиоматическое представление абстрактного синтаксического дерева в C ++? - PullRequest
Новая
       21

Какое самое идиоматическое представление абстрактного синтаксического дерева в C ++?

0 голосов
/ 02 ноября 2019

Я хотел бы создать простой синтаксический анализатор / анализатор типов / вычислитель для просто типизированного лямбда-исчисления. Я уже реализовал такое в Rust, но, как новичок в C ++, я не уверен, как лучше представить AST. Например, в Rust я могу определить рекурсивный тип суммы. Затем я могу использовать сопоставление с образцом или шаблон посетителя для посещения подтерм. 

enum Term {
    // de Bruijn index
    Var(usize),
    // Lambda abstraction x: T. t
    Abs(Box<Term>, Box<Term>),
    // Application t1 t2
    App(Box<Term>, Box<Term>),
}

fn ex(term: &mut Term) {
    match term {
        Term::Var(idx) => {

        },
        Term::Abs(ty, tm) => {
            ex(tm.as_mut());
        },
        Term::App(t1, t2) => {
            // do something
        }
    }
}

Без типов сумм кажется, что есть два основных способа представления чего-то похожего в C ++: пара enum / union (которую ябудет использовать в C) или иерархию классов с шаблоном посетителя (полная реализация не показана) 

class Expr {
public:
  virtual void visit(Visitor &v) const = 0;
  virtual ~Expr() {}
};

class Var : public Expr {
public:
  Var(int idx) : debruijn{idx} {}

private:
  int debruijn;
};

class App : public Expr {
public:
  App(std::unique_ptr<Expr> t1, std::unique_ptr<Expr> t2)
      : e1{std::move(t1)}, e2{std::move(t2)} {}

private:
  std::unique_ptr<Expr> e1;
  std::unique_ptr<Expr> e2;
};

class Abs : public Expr {
public:
  Abs(Type ty, std::unique_ptr<Expr> e) : e{std::move(e)}, ty{ty} {}

private:
  Type ty;
  std::unique_ptr<Expr> e;
};

Это лучший способ сделать это? Я хотел бы начать свое изучение C ++ с написания кода в самом современном и идиоматическом стиле.

1 Ответ

0 голосов
/ 02 ноября 2019

Начиная с C ++ 17, C ++ имеет суммы типов - вроде, в стандартной библиотеке: std::variant.

И вы можете использовать std::visit с overloaded хаком для соответствия правильному классу случая. Использование этого для AST должно быть довольно идиоматичным в наши дни.

Кроме того, вы можете использовать std::optional<T> вместо std::unique_ptr<T>.

... В качестве альтернативы, вы можетевзгляните на библиотеку Boost.Spirit X3 , которая генерирует парсеры, и посмотрите, что там происходит под капотом. Это библиотека C ++ 14.

...