Qual é o procedimento comum usado quando os compiladores estaticamente checam expressões "complexas"?

23

Nota: Quando usei "complexo" no título, quero dizer que a expressão possui muitos operadores e operandos. Não que a expressão em si seja complexa.

Recentemente, estive trabalhando em um compilador simples para montagem de x86-64. Eu terminei o front end principal do compilador - o lexer e o analisador - e agora sou capaz de gerar uma representação da Árvore de Sintaxe Abstrata do meu programa. E como meu idioma será digitado estaticamente, agora estou fazendo a próxima fase: verificar o código-fonte. No entanto, cheguei a um problema e não fui capaz de resolvê-lo razoavelmente.

Considere o seguinte exemplo:

O analisador do meu compilador leu esta linha de código:

int a = 1 + 2 - 3 * 4 - 5

E o converteu no seguinte AST:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Agora ele deve digitar check the AST. começa pelo primeiro tipo, verificando o =operador. Primeiro, verifica o lado esquerdo do operador. Ele vê que a variável aé declarada como um número inteiro. Portanto, agora deve verificar se a expressão do lado direito é avaliada como um número inteiro.

Entendo como isso poderia ser feito se a expressão fosse apenas um único valor, como 1ou 'a'. Mas como isso seria feito para expressões com vários valores e operandos - uma expressão complexa - como a acima? Para determinar corretamente o valor da expressão, parece que o verificador de tipos precisaria executar a própria expressão e registrar o resultado. Mas isso obviamente parece derrotar o objetivo de separar as fases de compilação e execução.

A única outra maneira que imagino que isso possa ser feito é verificar recursivamente a folha de cada subexpressão no AST e verificar se todos os tipos de folha correspondem ao tipo de operador esperado. Então, começando com o =operador, o verificador de tipos examinaria todos os AST do lado esquerdo e verificaria se as folhas são inteiras. Em seguida, repetiria isso para cada operador na subexpressão.

Eu tentei pesquisar o tópico na minha cópia de "O Livro do Dragão" , mas ele não parece entrar em muitos detalhes e simplesmente reitera o que eu já sei.

Qual é o método usual usado quando um compilador é do tipo que verifica expressões com muitos operadores e operandos? Algum dos métodos mencionados acima foi usado? Caso contrário, quais são os métodos e como exatamente eles funcionam?

language-agnostic compiler type-systems type Christian Dean
fonte
8
Existe uma maneira óbvia e simples de verificar o tipo de uma expressão. É melhor você nos dizer o que a chama de "desagradável".
precisa saber é o seguinte
12
O método usual é o "segundo método": o compilador infere o tipo de expressão complexa a partir dos tipos de suas subexpressões. Esse foi o ponto principal da semântica denotacional e a maioria dos sistemas de tipos criados até hoje.
Joker_vD 4/17
5
As duas abordagens podem produzir um comportamento diferente: a abordagem de cima para baixo double a = 7/2 tentaria interpretar o lado direito como duplo; portanto, tentaria interpretar numerador e denominador como duplo e convertê-los se necessário; como resultado a = 3.5. O bottom-up executaria divisão inteira e converteria somente na última etapa (atribuição), portanto a = 3.0.
Hagen von Eitzen
3
Observe que a imagem do seu AST não correspondem à sua expressão int a = 1 + 2 - 3 * 4 - 5, mas paraint a = 5 - ((4*3) - (1+2))
Basile Starynkevitch
22
Você pode "executar" a expressão nos tipos e não nos valores; por exemplo, int + inttorna-se int.

Respostas:

14

A recursão é a resposta, mas você desce em cada subárvore antes de manipular a operação:

int a = 1 + 2 - 3 * 4 - 5

à forma de árvore:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

A inferência do tipo acontece primeiro andando pelo lado esquerdo, depois pelo lado direito e, em seguida, manipulando o operador assim que os tipos dos operandos forem inferidos:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> desça para lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> inferir a. aé conhecido por ser int. Estamos de volta ao assignnó agora:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> desça em rhs, depois nos lhs dos operadores internos até encontrarmos algo interessante

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> inferir o tipo de 1, que é int, e retornar ao pai

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> entre no rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> inferir o tipo de 2, que é int, e retornar ao pai

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> inferir o tipo de add(int, int), que é int, e retornar ao pai

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> desça para o rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

etc., até você acabar com

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Se a atribuição em si também é uma expressão com um tipo depende do seu idioma.

A dica importante: para determinar o tipo de qualquer nó do operador na árvore, você só precisa examinar seus filhos imediatos, que precisam ter um tipo já atribuído a eles.

Simon Richter
fonte
43

Qual é o método geralmente usado quando um compilador é o tipo que verifica expressões com muitos operadores e operandos.

Leia as páginas sobre sistema de tipos e inferência de tipos e sobre o sistema de Hindley-Milner , que usa a unificação . Leia também sobre semântica denotacional e semântica operacional .

A verificação de tipo pode ser mais simples se:

  • todas as suas variáveis ​​como asão explicitamente declaradas com um tipo. Isso é como C ou Pascal ou C ++ 98, mas não como C ++ 11, que possui alguma inferência de tipo auto.
  • todos os valores literais gosta 1, 2ou 'c'tem um tipo inerente: um int literal sempre tem o tipo int, um caractere literal sempre tem o tipo char, ....
  • funções e operadores não estão sobrecarregados, por exemplo, o +operador sempre tem tipo (int, int) -> int. C possui sobrecarga para operadores ( +funciona para tipos inteiros assinados e não assinados e para duplos), mas não sobrecarrega funções.

Sob essas restrições, um algoritmo de decoração do tipo AST recursivo de baixo para cima pode ser suficiente (isso se preocupa apenas com tipos , não com valores concretos, portanto, é uma abordagem em tempo de compilação):

  • Para cada escopo, você mantém uma tabela para os tipos de todas as variáveis ​​visíveis (chamadas de ambiente). Após uma declaração int a, você adicionaria a entrada a: intà tabela.

  • A digitação de folhas é o caso básico da recursão trivial: o tipo de literal como 1já é conhecido e o tipo de variável como apode ser consultado no ambiente.

  • Para digitar uma expressão com algum operador e operando de acordo com os tipos previamente calculados dos operandos (subexpressões aninhadas), usamos recursão nos operandos (para que digitemos primeiro essas subexpressões) e siga as regras de digitação relacionadas ao operador .

Portanto, no seu exemplo, 4 * 3e 1 + 2são digitados intporque 4& 3e 1& 2foram digitados anteriormente inte suas regras de digitação dizem que a soma ou o produto de dois int-s é um inte assim por diante (4 * 3) - (1 + 2).

Leia o livro Tipos e idiomas de programação de Pierce . Eu recomendo aprender um pouquinho de Ocaml e λ-calculus

Para linguagens de tipo mais dinâmico (como Lisp), leia também o Lisp In Small Pieces do Queinnec

Leia também o livro Pragmático de linguagens de programação de Scott

BTW, você não pode ter um código de digitação independente de idioma, porque o sistema de tipos é uma parte essencial da semântica do idioma .

Basile Starynkevitch
fonte
2
Como o C ++ 11 autonão é mais simples? Sem ele, você precisa descobrir o tipo no lado direito e ver se há uma correspondência ou conversão com o tipo no lado esquerdo. Com autovocê, basta descobrir o tipo do lado direito e pronto.
Nwp 5/07
3
@nwp A idéia geral das definições de variáveis C ++ auto, C # vare Go :=é muito simples: digite check no lado direito da definição. O tipo resultante é o tipo da variável no lado esquerdo. Mas o diabo está nos detalhes. Por exemplo, as definições de C ++ podem ser autorreferenciais, portanto você pode se referir à variável que está sendo declarada no rhs, por exemplo int i = f(&i). Se o tipo de ifor inferido, o algoritmo acima falhará: você precisa saber o tipo de iinferir o tipo de i. Em vez disso, você precisaria de inferência de tipo no estilo HM com variáveis ​​de tipo.
amon
13

Em C (e francamente na maioria das linguagens de tipo estaticamente baseadas em C), todo operador pode ser visto como um açúcar sintático para uma chamada de função.

Portanto, sua expressão pode ser reescrita como: 

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Em seguida, a resolução de sobrecarga entrará em ação e decidirá que todas as funções são do tipo (int, int)ou (const int&, const int&).

Dessa forma, a resolução do tipo é fácil de entender e seguir e (mais importante) fácil de implementar. As informações sobre os tipos fluem apenas de uma maneira (das expressões internas para fora).

Essa é a razão pela double x = 1/2;qual resultará x == 0porque 1/2é avaliada como uma expressão int.

catraca arrepiante
fonte
6
Quase verdadeiro para C, onde +não é tratado como chamadas de função (uma vez que tem tipagem diferente para doublee para intoperandos)
Basile Starynkevitch
2
@BasileStarynkevitch: Ele é implementado como uma série de funções sobrecarregadas: operator+(int,int), operator+(double,double), operator+(char*,size_t), etc. O analisador só tem que manter o controle de qual deles está selecionado.
Mooing Duck
3
@aschepler Ninguém foi sugerindo que no nível especificação origem- e, C , na verdade, tem sobrecarregado funções ou funções de operador
gato
1
Claro que não. Apenas salientando que, no caso de um analisador C, uma "chamada de função" é outra coisa com a qual você precisa lidar, que na verdade não tem muito em comum com "operadores como chamadas de função", conforme descrito aqui. De fato, em C descobrir o tipo de f(a,b)é um pouco mais fácil do que descobrir o tipo de a+b.
aschepler
2
Qualquer compilador C razoável possui várias fases. Perto da frente (após o pré-processador), você encontra o analisador, que cria um AST. Aqui é bastante claro que os operadores não são chamadas de função. Mas na geração de código, você não se importa mais com qual construção de idioma criou um nó AST. As propriedades do próprio nó determinam como o nó é tratado. Em particular, + pode muito bem ser uma chamada de função - isso geralmente acontece em plataformas com matemática de ponto flutuante emulada. A decisão de usar a matemática FP emulada acontece na geração de código; não há diferença AST prévia necessária.
MSalters
6

Focalizando seu algoritmo, tente alterá-lo para baixo. Você conhece o tipo pf variáveis ​​e constantes; identifique o nó que carrega o operador com o tipo de resultado. Deixe a folha determinar o tipo de operador, também o oposto da sua ideia.

JDługosz
fonte
6

Na verdade, é bastante fácil, desde que você pense +que é uma variedade de funções e não um conceito único.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

Durante o estágio de análise do lado direito, o analisador recupera 1, sabe que é um int, depois analisa +e armazena isso como um "nome de função não resolvido", depois analisa 2, sabe que é um inte, em seguida, retorna essa pilha. O +nó da função agora conhece os dois tipos de parâmetros, portanto pode resolver o +into int operator+(int, int), então agora conhece o tipo dessa subexpressão e o analisador continua em seu caminho alegre.

Como você pode ver, uma vez que a árvore esteja totalmente construída, cada nó, incluindo as chamadas de função, conhece seus tipos. Isso é fundamental porque permite funções que retornam tipos diferentes dos seus parâmetros.

char* ptr = itoa(3);

Aqui, a árvore é:

    char* itoa(int)
     /           \
  ptr(char*)      3
Mooing Duck
fonte
4

A base para a verificação de tipo não é o que o compilador faz, é o que a linguagem define.

Na linguagem C, todo operando tem um tipo. "abc" tem o tipo "array of const char". 1 tem o tipo "int". 1L tem o tipo "long". Se x e y são expressões, existem regras para o tipo de x + y e assim por diante. Portanto, o compilador obviamente tem que seguir as regras da linguagem.

Em idiomas modernos como Swift, as regras são muito mais complicadas. Alguns casos são simples como em C. Outros casos, o compilador vê uma expressão, já foi informado de antemão que tipo a expressão deve ter e determina os tipos de subexpressões com base nisso. Se xey forem variáveis ​​de tipos diferentes e uma expressão idêntica for designada, essa expressão poderá ser avaliada de uma maneira diferente. Por exemplo, atribuir 12 * (2/3) atribuirá 8,0 a um Duplo e 0 a um Int. E você tem casos em que o compilador sabe que dois tipos estão relacionados e descobre quais tipos eles são baseados nisso.

Exemplo rápido: 

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

imprime "8.0, 0".

Na atribuição x = 12 * (2/3): o lado esquerdo tem um tipo conhecido Double, portanto o lado direito deve ter o tipo Double. Há apenas uma sobrecarga para o operador "*" retornando Double, e é Double * Double -> Double. Portanto, 12 deve ter o tipo Double, assim como 2 / 3. 12 suporta o protocolo "IntegerLiteralConvertible". Double possui um inicializador que aceita um argumento do tipo "IntegerLiteralConvertible", portanto, 12 é convertido em Double. 2/3 deve ter o tipo Double. Há apenas uma sobrecarga para o operador "/" retornando Double, e isso é Double / Double -> Double. 2 e 3 são convertidos para o dobro. O resultado de 2/3 é 0,66666666. O resultado de 12 * (2/3) é 8,0. 8.0 é atribuído a x.

Na atribuição y = 12 * (2/3), y no lado esquerdo tem o tipo Int, portanto o lado direito deve ter o tipo Int, para que 12, 2, 3 sejam convertidos em Int com o resultado 2/3 = 0, 12 * (2/3) = 0.

gnasher729
fonte