Por que não armazenamos a árvore de sintaxe em vez do código-fonte?

108

Temos muitas linguagens de programação. Cada idioma é analisado e a sintaxe verificada antes de ser traduzida em código para que uma árvore de sintaxe abstrata (AST) seja construída.

Temos esta árvore de sintaxe abstrata, por que não armazenamos essa árvore de sintaxe em vez do código-fonte (ou próximo ao código-fonte)?

Usando um AST em vez do código-fonte. Cada programador em uma equipe pode serializar essa árvore para qualquer idioma que quiser (com a gramática livre do contexto apropriada) e analisar novamente para a AST quando terminar. Então, isso eliminaria o debate sobre as questões de estilo de codificação (onde colocar o {e}, onde colocar espaço em branco, recuo, etc.)

Quais são os prós e contras desta abordagem?

    
por Calmarius 10.11.2011 / 23:04
fonte

13 respostas

70

Espaços em branco e comentários

Geralmente, uma AST não inclui espaço em branco, terminadores de linha e comentários.

Formatação significativa

Você está correto que na maioria dos casos isso é positivo (elimina a formatação de guerras sagradas), há muitos casos em que a formatação do código original transmite algum significado, como em literais de várias linhas e "parágrafos de código" ( separando blocos de instruções com uma linha vazia).

Código que não pode ser compilado

Embora muitos analisadores sejam muito resistentes à falta de sintaxe, o código com erros geralmente resulta em uma árvore de sintaxe muito estranha, o que é bom e elegante até o ponto em que o usuário recarrega o arquivo. Já cometeu um erro no seu IDE e, de repente, todo o arquivo tem "squigglies"? Imagine como isso seria recarregado em outro idioma.

Talvez os usuários não cometam código não analisável, mas eles certamente precisam salvar localmente.

Não há duas combinações perfeitas

Como outros apontaram, quase não há duas linguagens que tenham paridade perfeita. O mais próximo que eu posso pensar é VB e C #, ou JavaScript e CoffeeScript, mas mesmo assim o VB tem recursos como XML Literais que não possuem equivalentes em C #, e o JavaScript para conversão CoffeeScript pode resultar em muitos literais JavaScript. / p> Experiência pessoal:

Em um aplicativo de software que eu escrevo, nós realmente precisamos fazer isso, já que os usuários devem inserir expressões "plain english" que são convertidas para JS em segundo plano. Consideramos apenas o armazenamento da versão JS, mas não encontramos quase nenhuma maneira aceitável de fazer isso de forma confiável carregada e descarregada, então acabamos sempre armazenando tanto o texto do usuário quanto a versão JS, assim como uma bandeira que indicava se "versão analisada perfeitamente ou não.

    
por 10.11.2011 / 23:27
fonte
42

Why don't we store this syntax tree instead of the source code? Every programmer in a team can serialize this tree to any language, they want and parse back to AST when they finished.

Na verdade, essa é uma ideia razoável. A Microsoft tinha um projeto de pesquisa na década de 1990 para fazer quase exatamente isso .

Vários cenários vêm à mente.

O primeiro é bastante trivial; como você diz, você poderia ter o AST renderizado em diferentes visualizações, dependendo das preferências de diferentes programadores para coisas como espaçamento e assim por diante. Mas armazenar um AST é um exagero para esse cenário; apenas escreva para você uma impressora bonita. Quando você carrega um arquivo em seu editor, execute a impressora bonita para colocá-lo em seu formato preferido e de volta ao formato original ao salvá-lo.

O segundo é mais interessante. Se você puder armazenar a árvore de sintaxe abstrata, a alteração de código de uma mudança não se torna textual, mas sim sintática. Refatorações onde o código é movido se tornam muito mais fáceis de entender. O lado ruim é que escrever os algoritmos tree-diff não é exatamente trivial e muitas vezes tem que ser feito em uma base por idioma. A diferença de texto funciona para praticamente qualquer idioma.

O terceiro é mais parecido com o que Simonyi imaginou para a Programação Intencional: que os conceitos fundamentais comuns às linguagens de programação são os serializados, e então você tem visões diferentes daqueles conceitos renderizados em diferentes linguagens. Embora seja uma bela ideia, o fato desagradável é que as línguas são suficientemente diferentes em seus detalhes, o que uma abordagem de menor denominador comum não funciona realmente.

Então, em suma, é uma idéia adorável, mas é uma enorme quantidade de trabalho extra para um benefício comparativamente pequeno. É por isso que dificilmente alguém faz isso.

    
por 11.11.2011 / 18:45
fonte
19

Você poderia argumentar que este é exatamente o código de bytes no .NET. O programa refletor da infact redgate traduz o código de bytes de volta para uma variedade de linguagens de programação .NET.

No entanto, existem problemas. A sintaxe é específica do idioma, pois há coisas que você pode representar em um idioma que não tem representação em outros idiomas. Isso ocorre no .NET, com o C ++ sendo a única linguagem .NET que tem acesso a todos os 7 níveis de acesso.

Fora do ambiente .NET, fica muito mais complicado. Cada idioma começa a ter seu próprio conjunto de bibliotecas associadas. Não seria possível refletir uma sintaxe genérica em C e Java que refletisse a mesma execução de instruções, pois elas resolvem problemas simulares de maneiras muito diferentes.

    
por 10.11.2011 / 23:17
fonte
12

Eu meio que gosto de algumas de suas ideias, mas você está superestimando significativamente como é fácil traduzir o idioma para o idioma. Se fosse assim tão fácil, você nem precisaria armazenar o AST, já que você poderia sempre analisar a linguagem X no AST e então passar da AST para a linguagem Y.

No entanto, eu gostaria que as especificações do compilador pensassem um pouco mais sobre a exposição de algumas das AST através de algum tipo de API. Coisas como programação orientada a aspectos, refatoração e análise de programa estática podem ser implementadas por meio de uma API desse tipo, sem que o implementador desses recursos precise refazer grande parte do trabalho já implementado pelos criadores de compiladores.

É estranho a frequência com que a estrutura de dados do programador para representar um programa é um monte de arquivos contendo strings.

    
por 10.11.2011 / 23:45
fonte
11

Acho que os pontos mais importantes são os seguintes:

  • Não há nenhum benefício. Você disse que isso significaria que todos poderiam usar seu idioma de estimação. Mas isso não é verdade - usar uma representação em árvore de sintaxe elidiria apenas as diferenças sintáticas, mas não as semânticas. Ele funciona até certo ponto para linguagens muito semelhantes - como VB e C #, ou Java e Scala. Mas nem mesmo lá completamente.

  • É problemático. Você ganhou liberdade de linguagem, mas perdeu a liberdade de ferramentas. Você não pode mais ler e editar o código em um editor de texto, ou mesmo qualquer IDE - você depende de uma ferramenta específica que fala sua representação AST para ler e editar o código. Não há nada ganho aqui.

    Para ilustrar este último ponto, dê uma olhada no RealBasic, que é uma implementação proprietária de um poderoso dialeto BASIC. Por um tempo, quase parecia que a linguagem poderia decolar, mas era completamente dependente do fornecedor, a ponto de você poder ver apenas o código em seu IDE, já que ele era salvo em um formato não-textual proprietário. Erro Grande .

por 11.11.2011 / 13:26
fonte
6

Eu acho que, se você armazenar tanto o texto quanto o AST, você não adicionou nada de útil, já que o texto já existe em um idioma, e o AST pode ser rapidamente reconstruído a partir do texto.

Por outro lado, se você armazenar apenas o AST, você perderá coisas como comentários que não podem ser recuperados.

    
por 10.11.2011 / 23:16
fonte
4

Eu acredito que a idéia é interessante na teoria, mas não muito prática, já que diferentes linguagens de programação suportam construções diferentes, algumas que não têm equivalentes em outras linguagens.

Por exemplo, o X ++ tem uma instrução 'while select' que não pode ser escrita em C # sem muito código extra (classes extras, lógica extra, etc). link

O que estou dizendo aqui é que muitas línguas têm açúcares sintáticos que se traduzem em grandes blocos de código da mesma língua ou até mesmo elementos que não existem em outros. Aqui está um exemplo porque a abordagem AST não funcionará:

A linguagem X tem uma palavra-chave K que é traduzida, em AST, em 4 declarações: S1, S2, S3 e S4. A AST agora é traduzida na linguagem Y e um programador altera S2. Agora, o que acontece com a tradução de volta para o X? O código é traduzido como 4 declarações em vez de uma única palavra-chave ...

O último argumento contra a abordagem AST são as funções da plataforma: o que acontece quando uma função é incorporada na plataforma? Como o Environment.GetEnvironmentVariable do .NET. Como você traduz isso?

    
por 11.11.2011 / 01:07
fonte
4

Existe um sistema construído em torno desta ideia: JetBrains MPS . Um editor é um pouco estranho, ou apenas diferente, mas em geral não é um problema tão grande. O maior problema é, bem, que não é mais um texto, então você não pode usar nenhuma das ferramentas baseadas em texto - outros editores, grep , sed , ferramentas de mesclagem e de diferenças, etc. / p>     

por 11.11.2011 / 14:00
fonte
4

Na verdade, existem vários produtos, geralmente conhecidos como "workbenches de linguagem", que armazenam ASTs e apresentam, em seus editores, uma "projeção" da AST em um idioma específico. Como o @ sk-logic disse, o MPS da JetBrains é um desses sistemas. Outro é o Intentional Workbench da Intentional Software.

O potencial para as bancadas de idiomas parece muito alto, particularmente na área de idiomas específicos de domínio, já que você pode criar uma projeção específica de domínio. Por exemplo, o Intentional demonstra uma DSL relacionada à eletricidade que se projeta como um diagrama de circuito - muito mais fácil e preciso para um especialista em domínio discutir e criticar do que um circuito descrito em uma linguagem de programação baseada em texto.

Na prática, as workbenches de idiomas demoraram a perceber porque, além do trabalho com DSL, os desenvolvedores provavelmente prefeririam trabalhar em uma linguagem de programação geral e familiar. Quando comparados frente-a-frente com um editor de texto ou programação IDE, as workbenches de idiomas têm toneladas de sobrecarga e suas vantagens não são tão claras. Nenhuma das workbenches de linguagem que vi se encaixou no ponto em que é possível estender facilmente seus próprios IDEs - ou seja, se as workbenchs de linguagens são ótimas para produtividade, por que as ferramentas de workbench de idiomas não se tornam melhores e-melhor em taxas mais rápidas e mais rápidas?

    
por 11.11.2011 / 20:13
fonte
3

Você tem lido minha mente.

Quando fiz um curso de compiladores, há alguns anos, descobri que, se você pegar um AST e serializá-lo, com a notação de prefixo em vez da notação infixa usual, e usar parênteses para delimitar instruções inteiras, você obterá Lisp. Enquanto eu aprendi sobre Scheme (um dialeto de Lisp) em meus estudos de graduação, eu nunca realmente ganhei uma apreciação por isso. Eu definitivamente ganhei uma apreciação por Lisp e seus dialetos, como resultado desse curso.

Problemas com o que você propõe:

  1. é difícil / lento compor um AST em um ambiente gráfico. Afinal, a maioria de nós pode digitar mais rápido do que podemos mover um mouse. E ainda, uma questão emergente é "como você escreve código de programa com um tablet?" Digitar em um tablet é lento / incômodo, comparado a um teclado / laptop com um teclado de hardware. Se você pudesse criar uma AST arrastando e soltando componentes de uma paleta em uma tela em uma tela grande, a programação do dispositivo touchscreen em um tablet poderia se tornar uma coisa real.

  2. poucas / nenhuma de nossas ferramentas existentes suportam isso. Temos décadas de desenvolvimento envolvidos na criação de IDEs cada vez mais complexos e editores cada vez mais inteligentes. Temos todas essas ferramentas para reformatar texto, comparar texto, pesquisar texto. Onde estão as ferramentas que podem fazer o equivalente a uma pesquisa de expressão regular em uma árvore? Ou um diff de duas árvores? Todas essas coisas são facilmente feitas com texto. Mas eles só podem comparar as palavras. Altere o nome de uma variável, de forma que as palavras sejam diferentes, mas o significado semântico é o mesmo, e essas ferramentas de diferenças têm problemas. Tais ferramentas, desenvolvidas para operar em ASTs ao invés de texto, permitiriam que você chegasse mais perto de comparar o significado semântico. Isso seria uma coisa boa.

  3. enquanto transformar o código-fonte do programa em um AST é relativamente bem compreendido (temos compiladores e intérpretes, não é?), transformar um AST em código de programa não é tão bem compreendido. Multiplicar dois números primos para obter um grande número composto é relativamente simples, mas incluir um número grande e composto em números primos é muito mais difícil; é aí que estamos analisando vs descompilando ASTs. É aí que as diferenças entre idiomas se tornam um problema. Mesmo dentro de um idioma específico, existem várias maneiras de descompilar um AST. Iterando através de uma coleção de objetos e obtendo algum tipo de resultado, por exemplo. Use um loop for, percorrendo uma matriz? Isso seria compacto e rápido, mas há limitações. Use um Iterator de algum tipo, operando em uma coleção? Essa coleção pode ser de tamanho variável, o que aumenta a flexibilidade com a (possível) despesa de velocidade. Mapear / Reduzir? Mais complexo, mas implicitamente paralelizável. E isso é apenas para Java, dependendo de suas preferências.

Com o tempo, o esforço de desenvolvimento será gasto e estaremos desenvolvendo usando telas de toque e ASTs. A digitação se tornará menos necessária. Eu vejo isso como uma progressão lógica de onde estamos, olhando como usamos computadores, hoje, Isso vai resolver # 1.

Já estamos trabalhando com árvores. Lisp é meramente serializado ASTs. XML (e HTML, por extensão) é apenas uma árvore serializada. Para pesquisar, já temos alguns protótipos: XPath e CSS (para XML e HTML, respectivamente). Quando são criadas ferramentas gráficas que nos permitem criar seletores e modificadores no estilo CSS, teremos resolvido parte do # 2. Quando esses seletores puderem ser estendidos para suportar regexes, estaremos mais próximos. Ainda procurando uma boa ferramenta de comparação gráfica para comparar dois documentos XML ou HTML. À medida que as pessoas desenvolvem essas ferramentas, o nº 2 será resolvido. As pessoas já estão trabalhando nessas coisas; eles simplesmente não estão lá ainda.

A única maneira que eu vejo para poder descompilar os ASTs para o texto da linguagem de programação seria algo que busca objetivos. Se estou modificando o código existente, o objetivo pode ser alcançado por um algoritmo que torna meu código modificado o mais semelhante possível ao código inicial (diff textual mínimo). Se eu estou escrevendo código a partir do zero, o objetivo pode ser o código mais pequeno e mais tight (provavelmente um loop for). Ou pode ser um código que paralelize de forma tão eficiente quanto possível (provavelmente um mapa / reduzir ou algo que envolva CSP). Assim, a mesma AST poderia resultar em código significativamente diferente, mesmo na mesma linguagem, com base em como as metas foram definidas. Desenvolver tal sistema resolveria o nº 3. Seria computacionalmente complexo, o que significa que provavelmente precisaríamos de algum tipo de arranjo cliente-servidor, permitindo que seu tablet portátil descarregasse muito trabalho pesado em algum servidor baseado em nuvem.

    
por 19.06.2014 / 16:27
fonte
1

Se sua intenção é eliminar o debate sobre estilos de formatação, talvez o que você queira é um editor que leia um arquivo de origem, formate-o de acordo com sua preferência pessoal para exibição e edição, mas ao salvá-lo reformata o arquivo escolhido. estilo que a equipe usa.

É muito fácil usar um editor como o Emacs . Alterar o estilo de formatação de um arquivo inteiro é uma tarefa de três comandos.

Você também deve ser capaz de criar os ganchos para transformar automaticamente um arquivo em seu próprio estilo no carregamento e transformá-lo no estilo de equipe ao salvar.

    
por 11.11.2011 / 15:23
fonte
1

É difícil ler e modificar um AST, em vez do código-fonte.

No entanto, algumas ferramentas relacionadas ao compilador permitem usar o AST. O bytecode Java e o código .NET Intermediate funcionam de maneira semelhante a um AST.

    
por 11.11.2011 / 00:39
fonte
0

é uma boa ideia; mas a AST de cada idioma é diferente de todas as outras.

a única exceção que eu sei é para VB.NET e C #, onde a microsoft argumenta que eles são "exatamente a mesma linguagem com sintaxe diferente". Até mesmo outras linguagens .NET (IronPython, F #, whatever) são diferentes no nível AST.

A mesma coisa com as linguagens da JVM, todas elas têm como alvo o mesmo bytecode, mas as construções da linguagem são diferentes, tornando diferentes idiomas e diferentes ASTs.

Mesmo linguagens de 'camada fina', como CoffeScript e Xtend, compartilham muito da teoria das linguagens subjacentes (JavaScript e Java, respectivamente); mas introduza conceitos de nível superior que são (ou deveriam ser) mantidos no nível AST.

se o Xtend pudesse ser reconstruído a partir de um Java AST, eu acho que ele teria sido definido como um 'uncompiler' Java-to-Xtend que magicamente cria abstrações de nível mais alto a partir do código Java existente, você não acha?

    
por 11.11.2011 / 15:05
fonte