No capítulo 1 de Fundamentos práticos para linguagens de programação , o autor menciona que as árvores de sintaxe abstratas estão associadas a tipos .
Intuitivamente, as classificações são como tipos, mas eu gostaria de saber se elas têm uma definição precisa. Ficaria feliz se algumas referências também forem fornecidas.
Depende da semântica que usaríamos para tipos e tipos. + No entanto, uma breve - pouca informal - definição pode ser + Os tipos são classes de ASTs e os tipos são classes de valores .
Na verdade, há muita semelhança entre as classificações para a sintaxe e os tipos abstact, como normalmente entendido. Porém, as sortes são um conceito sintático formal , e as árvores AS também são sintaxe, enquanto os tipos são um conceito semântico .
A terminologia vem do termo álgebra (também chamado de álgebra livre ) e álgebra universal . São teorias essencialmente sintáticas de estruturas algébricas, analisadas independentemente de quaisquer interpretações. Eles foram desenvolvidos na primeira metade do século XX.
Um termo pode ser visto como uma árvore, onde os nós são rotulados a partir de um conjunto finito de operadores, cada operador tendo uma aridade fixa que especifica o número de filhas na árvore. Arity 0 é para folhas. Nas álgebras com várias classificações, isso é refinado com classificações, de modo que cada operador pertence a uma classificação e as regiões são substituídas por uma lista ordenada de classificações, que corrige para cada filha o tipo de operador principal. O tipo de operador, juntamente com a lista dos tipos de sua filha, é chamado de assinatura do operador.
Nas álgebras universais, isso é refinado pela introdução de relações de equivalência definidas equacionalmente entre termos.
Embora pareça ter diminuído um pouco, esses conceitos eram bastante populares e muito estudados em ciência da computação no final do século XX, como álgebras abstratas, que eram vistas como uma base para tipos de dados abstratos, que é, em parte, precursor do que é nas classes em programação orientada a objetos.
As álgebras universais estão relacionadas ao desenvolvimento da teoria das categorias, que também é fundamental na visão atual de tipos e linguagens de programação.
As álgebras são objetos sintáticos e devem ser usadas com uma interpretação em alguns domínios semânticos correspondentes aos tipos. Uma interpretação é um homomorfismo que mapeia as classificações em domínios de valores (tipos) e os operadores em funções entre esses domínios, para que as assinaturas sejam respeitadas e as equações também no caso de uma álgebra equacional. É assim que você pode aplicar os resultados da teoria de grupos a qualquer domínio com uma operação que respeite a definição de um grupo.
Essa organização foi considerada muito conveniente pelos primeiros pesquisadores em linguagens de programação, especialmente aqueles preocupados com a formalização de linguagens de programação. Teve a vantagem de isolar sintaxe e semântica e de ser matematicamente bem compreendido.
Outro motivo para adotá-lo foi a preocupação com o desenvolvimento de uma ferramenta para manipular programas, seja em ambientes de desenvolvimento ou em sistemas formais para provar propriedades de programas (que se mostraram cada vez mais problemas gêmeos).
Isso levou ao surgimento do conceito de árvore de sintaxe abstrata (AST) para linguagens de programação, que são essencialmente termos de uma álgebra com classificação múltipla (algumas vezes refinada com o uso da união de classificação em alguns sistemas). O AST é a sintaxe de referência para uma linguagem, a partir da qual a semântica pode ser definida pelo homomorfismo, como na semântica denotacional.
Isso não é apenas conveniente para estudar semântica de linguagens, mas as árvores são mais bem estruturadas que as strings e, portanto, uma base melhor para o desenvolvimento de ferramentas de programação e ambientes de programação.
Ele permite isolar a análise, que era tradicionalmente uma parte confusa, pois as limitações da tecnologia de análise forçavam o uso de gramáticas distorcidas. Isso também leva em consideração os problemas de apresentação.
Ele permite várias representações concretas (de seqüência de caracteres ou gráficas) de programas, o que às vezes pode ser conveniente (não há motivo para usar a pontuação em vez de guias, ou o inverso, na sintaxe do programa deve ser imposta às pessoas).
Facilita a definição de muitas interpretações de programas e de vários tipos , a fim de analisar as propriedades do programa com interpretações abstratas.
É conveniente para escrever ferramentas de manipulação de programas (semi-) automatizadas, por exemplo, para transformações automáticas de programas ou traduções entre idiomas.
Às vezes, as coisas podem ser um pouco mais complicadas na prática, porque algumas formas da Sintaxe Abstrata permitem que alguns operadores construam árvores (expressões) que pertencem a vários tipos (uma maneira informal de ver isso). Por exemplo, pode haver uma classificação para construções sintáticas que representam variáveis (entidades atribuíveis) e outra para expressões. Mas qualquer variável pode ser usada como expressão, sendo o inverso falso.
Os primeiros artigos sobre isso, para linguagens de programação, datam de meados dos anos setenta. A conceituação da época destinava-se à produção de ambientes de programação conscientes em sintaxe (a palavra "direcionado" era então usada). Procure Mentor e Centaur na Europa e Cornell Program Synthesizer nos EUA. Eles foram os dois primeiros sistemas a realmente usar esses conceitos de maneira prática. Muitos outros foram desenvolvidos depois.
Mas a sintaxe abstrata é anterior a esses sistemas. A linguagem Lisp (1958) tinha sintaxe abstrata, o que não é surpresa, pois foi desenvolvida por um lógico e com o objetivo de criar programas que manipulam programas (veja também ML e LCF ... que vieram mais tarde). Mas Lisp não foi classificado: tudo era sintaticamente uma lista e uma estrutura mais refinada dependia essencialmente da semântica. Isso levou algumas pessoas a considerar, de maneira um tanto incorreta, que o Lisp não tinha sintaxe.
Parece no capítulo quatro que os tipos são para sintaxe e os tipos são para semântica.
O exemplo de gráfico de sintaxe na página 40 lida com os tipos no idioma L {num str}. Aparentemente, tipos são categorias na sintaxe do idioma.
Em particular, "mais" tem uma classificação, que é a categoria sintática do seu resultado. O tipo de operador "mais" é nomeado "Exp". Isso representa o fato de que, sintaticamente, uma invocação do operador "mais" é uma expressão. Uma invocação do operador "mais" pode preencher uma posição em uma árvore de sintaxe abstrata onde uma expressão é permitida. Esse é o tipo de construção que é um "mais". É assim que ele se encaixa na estrutura de um texto que representa um programa.
O sistema de tipos na página 41 lida com os tipos no idioma L {num str}. O tipo de operador "mais", considerando que seus operandos têm o tipo "num", é "num". Este julgamento é uma descrição parcial da semântica do operador "plus". Ou seja, parte do significado do operador "mais" é a combinação de dois números para produzir um número. Este significado distingue "mais" de outras expressões.
Além disso, existe uma classificação chamada "Typ" que contém os dois tipos, "num" e "str".
fonte
No início do capítulo 1, Harper dá uma dica do que ele quer dizer com a palavra tipo :
Ele define a palavra frase como uma árvore de sintaxe abstrata, que ele discute.
fonte