Representação AST homogênea vs. heterogênea

5

Quais são as razões para escolher uma representação AST homogênea versus heterogênea para implementar uma linguagem de programação específica de domínio complexa?

Só para ficar bem claro sobre o que estou perguntando, aqui estão alguns detalhes extras:

Por homogênea, quero dizer uma árvore construída de nós que são um único tipo genérico . Por exemplo, acho que essa questão é realmente independente de linguagem, mas usando uma estrutura do tipo C ++ para ilustração, eu consideraria isso um nó de árvore de sintaxe abstrato homogêneo mínimo:

struct Node {
  int tag;
  void *data;

  Node *first_child;
  Node *next_sibling;
};

Por heterogêneo, quero dizer uma árvore construída de nós que são múltiplos tipos individuais (por exemplo, um para cada produção de gramática). Por exemplo, eu não quero assumir uma linguagem específica, mas novamente usando structs para ilustração em C ++, eu consideraria esses tipos parte de uma hierarquia usada para construir uma árvore de árvore de sintaxe abstrata heterogênea:

struct Node {};

struct Integer_Node : Node {
  int value;
};

struct Plus_Node : Node {
  Node *right;
  Node *left;
};

struct If_Statement : Node {
  Node *Condition;
  Node *Then_Expression;
  Node *Else_Expression;  
};

// ... more types, depending on the language ...

Ao longo dos anos, eu implementei vários pequenos compiladores para propósitos especiais, geralmente de maneira muito específica. Eu nunca usei muito "AST" real porque normalmente a tradução direta da sintaxe tem sido boa o suficiente.

Agora, estou no processo de projetar e implementar uma nova linguagem, muito mais complexa, na qual estarei construindo uma AST e, em seguida, percorrendo-a com vários passes para verificação, análise semântica e assim por diante.

Por exemplo, parece que usar um esquema homogêneo reduz a quantidade de código na frente, mas eu me pergunto se um esquema heterogêneo vai compensar melhor a longo prazo por razões que não estou considerando. Por outro lado, o esquema heterogêneo parece permitir beneficiar-se da verificação do tipo estático do compilador, do despacho do método virtual, etc, mas eu me pergunto se isso é realmente muito útil ao desenvolver passagens semânticas e assim por diante.

Basicamente, espero obter alguns insights daqueles que podem ter alguma experiência real aqui. Li muitos livros sobre compiladores e tenho uma quantidade moderada de experiência básica em compilação de compiladores, mas não vi essa dicotomia específica abordada em nenhuma literatura na qual eu possa colocar minhas mãos.

    
por wjl 27.05.2013 / 04:02
fonte

1 resposta

5

Para mim, a grande vantagem da AST heterogênea é que ela forma uma espécie de instrução switch anotada e forçada (assumindo uma linguagem semelhante a C).

Para o AST homogêneo, você geralmente acaba com algum tipo de rotina ou classe com uma grande declaração switch . Você precisa acompanhar qual nó filho é o que você mesmo. "Primeiro filho é o condicional, segundo o bloco verdadeiro, terceiro o falso bloco." Sempre que você altera o código, você se vê facilmente fazendo uma imagem mental de sua sintaxe DSL repetidas vezes.

É claro que você pode documentar muito, mas um bom programa deve ser auto-documentado o máximo possível. A AST heterogênea faz exatamente isso.

Além disso, você pode facilmente transformar uma AST heterogênea em uma homogênea, mas não o contrário. Adicione as informações da tag (o que é uma boa ideia, a menos que seu idioma ofereça suporte a uma consulta is-a barata). Você pode adicionar métodos Node(int index) para retornar os campos nomeados. Então você não perde nada em geral usando a AST heterogênea.

Não vou mencionar que o AST heterogêneo é ideal para o padrão Visitor, já que é tão fácil usar o padrão Strategy com a rotina switch homogênea. É mais fácil adicionar funcionalidade específica à própria AST heterogênea, no entanto. Se você quiser transformá-lo em um intérprete, tudo o que você precisa fazer é adicionar algum tipo de método "eval".

Eu consideraria uma AST homogênea se houvesse circunstâncias limitantes . Se você precisar portar o compilador para um sistema sem linguagem OOP disponível, ou se precisar otimizar a velocidade. O AST homogêneo é mais fácil de combinar com um FSM. O último também pode ser uma vantagem se você quiser ter um compilador multi-uso geral que carregue regras de sintaxe rapidamente. Mas é mais fácil começar com um AST heterogêneo que irá gerar essas tabelas, depois que o compilador tiver sido completamente testado.

Portanto, apesar de tudo, eu diria que nenhuma das árvores oferece vantagens específicas em termos de "essa árvore ajuda ou dificulta, digamos, 'passes semânticos'?" A vantagem do AST heterogêneo é, na minha experiência, reduzir a quantidade de pensamento e concentração que você tem que colocar na codificação do material tedioso do compilador. Há muita repetitividade e contabilidade acontecendo, então deixe o computador fazer o trabalho para você o máximo possível, é o meu lema.

    
por 17.06.2013 / 23:51
fonte