Aqui, tentei mostrar na prática quais são alguns conceitos importantes do campo da criação de compiladores. Existe a possibilidade de que essas histórias completas de 15 minutos possam ser uma boa maneira de mergulhar em tópicos complexos. Apenas seria bom não ler passivamente o que é apresentado abaixo, mas também verificar o código no trabalho.
Se a primeira experiência for bem-sucedida, no futuro você poderá esperar outros "esboços" de 15 minutos sobre o assunto dos compiladores.
O que será discutido
Vamos fazer um compilador de expressões aritméticas. Um que traduz o texto de origem na notação polonesa reversa (também é chamado RPN ou POLIZ) em código intermediário que funciona com a pilha. Mas podemos ficar sem intérpretes aqui. Em seguida, traduzimos imediatamente o resultado em uma representação C. Ou seja, obtemos um compilador do RPN para o C.
A propósito, escreveremos o compilador em Python. Mas não deixe isso parar aqueles que preferem alguma outra linguagem de programação. Aqui está um exercício útil para você: traduza o código abaixo para o seu idioma favorito. Ou use uma tradução já concluída:
Implementação de F # (por gsomix ):
primeira versão
Versão SSA
Vamos começar com a análise
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
O que fizemos aqui? A função de varredura recebe uma sequência do usuário na notação polonesa reversa ("2 2 +").
E na saída obtemos sua representação intermediária. Aqui está um exemplo:
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
Então, nós já temos o compilador. Mas ele é muito frívolo. Lembre-se de que inicialmente era sobre código C.
Vamos transmitir em C
def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
O que está acontecendo aqui? Vejamos a saída dessa função (usando o mesmo exemplo com "2 2 +").
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
Sim, ele já se parece com o código C. A matriz st desempenha o papel da pilha e sp é o ponteiro. Normalmente, as máquinas de pilha virtual trabalham com essas coisas.
Isso é apenas a própria máquina - o intérprete, nós não temos. Existe um compilador. O que nos resta? É necessário adicionar os quadros necessários para o programa C.
Nosso primeiro compilador finalizado
ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
Resta compilar a saída deste programa com o compilador C.
Você ainda está pronto para continuar? Então vamos discutir o que fizemos. Há um momento duvidoso - nosso compilador traduz expressões constantes, e você pode calculá-las simplesmente no estágio de compilação. Não faz sentido convertê-los em código. Mas vamos assumir por enquanto que alguns argumentos podem chegar à pilha do lado de fora. Vamos insistir no fato de que o significado prático de nosso desenvolvimento pode ser dado posteriormente. Agora, é importante ter uma idéia geral da criação dos compiladores mais simples, certo?
Você gosta do título? SSA - isso parece muito sólido para qualquer compilador. E agora vamos usar esse mesmo SSA. O que é isso? Vamos nos mover em ordem.
No momento, estamos gerando código C, sem nenhuma máquina virtual. Mas por que precisamos de um rudimento na forma de operações de pilha? Vamos substituir essas operações por trabalhar com variáveis comuns de C. Além disso, não salvaremos variáveis - teremos um novo nome para cada expressão. Deixe o compilador C lidar com tudo isso. Acontece que conosco, cada variável recebe um valor apenas uma vez. E esta, a propósito, é a forma da SSA .
Aqui está o nosso novo compilador.
C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
Observe que não há mais uma pilha no código C e o trabalho com ela é simulado durante a tradução. A pilha usada no processo de compilação não contém valores, mas nomes de variáveis.
Aqui está o resultado final:
#include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
Sumário
Parece que o tempo da nossa lição conjunta expirou. Estávamos empenhados em traduzir o programa de um idioma para outro. Isso é chamado de tradução fonte a fonte. Ou - apenas uma tradução, que pode ser considerada um sinônimo de compilação, mas geralmente o compilador traduz o programa de uma representação de alto nível para uma de baixo nível. Há também a palavra-chave "transpiler" para tradutor de fonte a fonte. Mas a menção do "transpiler" pode ser irritante para especialistas em compiladores, tenha cuidado!
Experimente o código. À espera de feedback!