Compilador Compact

 

1 - Objectivo

O objectivo desta aula é o aluno tomar contacto com um compilador muito simples. Desta forma torna-se mais fácil compreender os processos e mecanismos utilizados:

  1. Geração do compilador através compilação dos ficheiros que o formam.
  2. Utilização do compilador gerado para produzir ficheiros executáveis a partir de exemplos dados e outros programas de teste que pretenda usar.
  3. Ganhar sensibilidade aos vários componentes do compilador, estabecendo a ligação com os componentes apresentados nas aulas teóricas, embora não seja suposto compreender o seu funcionamento interno.

 

2 - A linguagem COMPACT

A linguagem compact tal como no projecto de avaliação usa as ferramentas lex, yacc e burg para gerar código executável i386. A linguagem inclui expressões artiméticas e de comparação, instruções condicionais e de ciclo, instruções de leitura e escrita, bem como atribuições. A sintaxe é muito semelhante à da linguagem C, por forma a facilitar a sua compreensão. No entanto, a linguagem não suporta funções ou expressões lógicas e tem um único tipo de dados (inteiro).

 

3 - Geração das bibliotecas

Para a geração do compilador sugere-se a utilzação da Makefile, que depois de adaptada pode ser utilizada em outros projectos, nomeadamente no projecto de avaliação.

Antes de gerar o compilador é necessário gerar a biblioteca de desenvolvimento compiladores (-lutil) e a biblioteca de execução da linguagem (-lrun)

A biblioteca de desenvolvimento do compilador reside no directório lib, bastando executar o comando make nesse directório ou executar os comandos:

  1. compilação das rotinas de suporte à construção da árvore sintáctica (node.c), à construção da tabela de símbolos (tabid.c) e rotinas auxiliares (main.c):
      	prompt$  gcc -g -c node.c tabid.c main.c
      	
  2. geração da biblioteca:
      	prompt$  ar crl libutil.a node.o tabid.o main.o
      	

A biblioteca de desenvolvimento compilador inclui rotinas genéricas e que podem ser utilizadas por qualquer compilador gerado por este processo.

A biblioteca de execução da linguagem reside no directório runtime. Por omissão, a Makefile utiliza o suporte para i386 no directório linux32. Os outros directórios geram a biblioteca de execução que permite executar os exemplos da linguagem compact nesses processadores ou sistemas operativos. Notar que essas bibliotecas podem exigir ferramentas e opções que apenas existam nesses processadores ou sistemas operativos. A escolha do ambiente pode ser efectuada com a opção SYS da Makefile.

O comando make install permite copiar a biblioteca para o directório base (..). Para gerar a biblioteca basta executar o comando make nesse directório ou executar os comandos:

  1. compilação das rotinas de suporte ao arranque essenciais (linux.asm), rotinas auxiliares (lib.asm) e rotinas de interface com o sistema operativo (sys.asm), todas codificadas em assembly i386, além de rotinas de conversão de números reais em precisão dupla (dbl.c),:
      	prompt$  nasm -felf linux.asm
      	prompt$  nasm -felf lib.asm
      	prompt$  nasm -felf sys.asm
      	prompt$  gcc -c -DPOSTFIX dbl.c
      	
  2. geração da biblioteca:
      	prompt$  ar crl librun.a linux.o lib.o sys.o dbl.o
      	

Nos ambientes em que as rotinas são precedidas de underscore (_) pode ser necessário definir -Dunderscore na compilação de ficheiros C. Em alguns sistemas, nomeadamente algumas versões de Ubunto, pode ser necessário definir -fno-stack-protector quando se obtém o erro __stack_chk_fail.

A biblioteca de execução da linguagem inclui as rotinas que podem ser invocadas pelos programas gerados pelo compilador e não pelo compilador.

  1. linux.asm: _start invoca a rotina principal da linguagem (_main no caso da linguagem compact); prints imprime uma cadeia de caracteres terminada em zero; readb lê um único byte, devolvido como um inteiro;
  2. lib.asm: strlen e strlen como em C; printi, printsp e println imprime um valor inteiro, um espa&ccdeil;o branco e uma mudança de linha, respectivamente; readi e readln lê um valor inteiro e uma linha completa, respectivamente; argc, argv e envp devolve o número de argumentos, o n-ésimo argumento (ou zero, se não existir) e a n-ésima variável de ambiente (ou zero, se não existir), respectivamente; itoa converte um valor inteiro numa cadeia de caracteres;
  3. sys.asm: inclui quase todas as chamadas ao sistema unix (ver man 2 intro), como acesso a ficheiros ou manipulação de processos, entre outros;
  4. dbl.c: printd para imprimir valores reais em precisção dupla, read para ler valores reais em precisção dupla, atod converte uma cadeia de caractres para o seu valor real em precisção dupla, dtoa converte um valor real em precisção dupla numa cadeia de caracteres;

 

4 - Geração do compilador

O processo de geração do compilador propriamente dito exige as ferramentas flex (versão 2.5.35 ou mais actual), byacc (versão 1.9 ou mais actual), pburg (versão disponibilizada na p&aaucte;gina da disciplina). As ferramentas flex e byacc podem já estar instaladas. Para gerar o compilador, executar no directório demo o comando makeou os comandos (a ordem das instruções é relevante):

  1. geração do analisador sintáctico (gera os ficheiros y.tab.c, y.tab.h e y.output):
      	prompt$  byacc -dv gram.y
      	
  2. geração do analisador lexical (gera o ficheiro lex.yy.c):
      	prompt$  flex -l scan.l
      	
  3. geração do gerador de código postfix para processadores Pentium de 32 bits(gera o ficheiro yyselect.c):
      	prompt$  pburg -T pfix.brg
      	
  4. geração dos ficheiros objecto relocatáveis:
      	prompt$  gcc -g -c -DYYDEBUG -I../lib y.tab.c lex.yy.c yyselect.c 
      	
  5. geração do compilador (geração de código para i386):
      	prompt$  gcc -o compact y.tab.o lex.yy.o yyselect.o -L../lib -lutil -lfl
      	

 

5 - Execução de aplicações escritas em compact

Uma vez produzido o compilador, podemos usá-lo para produzir programas e rotinas. Entre os ficheiros de exemplo disponibilizados no directório, temos:

  • div.cpt imprime os divisores de um número lido, ou imprime 'É primo' se for divível apenas pela unidade e por ele próprio.
  • gcd.cpt determina e imprime o maior divisor comum entre dois números introduzidos.
  • tri.cpt classifica o triângulo, dadas as dimensões dos seus lados.

Para gerar código assembly para linux-elf-i386, o primeiro passo consiste em compilar um ficheiro fonte para produzir o respectivo ficheiro assembly:

  	prompt$  ./compact div.cpt
  	

A produção do ficheiro objecto utiliza o assembler nasm:

  	prompt$  nasm -felf div.asm
  	

ficando gerado o ficheiro div.o.

Para produzir o executável final é necessário ligar o ficheiro objecto gerado com uma biblioteca. Tal deve-se ao facto de, na realidade, a execução dos programas não começa pela rotina main, mas pela rotina _start, devendo esta chamar a rotina main depois de ter efectuado as iniciações necessárias. De igual forma, a rotina _start é responsável por terminar o processo, quando o programa regressa da rotina main. Notar que o processador continuaria a executar instruções, a menos que se passe o controlo ao sistema operativo com o pedido de terminação: a chamada ao sistema _exit (semelhante ao exit do C).

As rotinas necessárias e outras rotinas de uso comum, como rotinas de leitura e impressão, estão incluídas no ficheiro lib.asm e no ficheiro linux.asm da biblioteca -lrun (que correspode ao ficheiro compact/runtime/librun.a).

O executável final é obtido através da junção do ficheiro objecto com a biblioteca de suporte à execução:

  	prompt$  ld -o div div.o -L../runtime -lrun
  	

O executável div pode ser executado como qualquer outro programa unix: prompt$ ./div
12
2
3
4
6

 

6 - As entranhas do compilador

Tal como descrito nas aulas, o compilador é constituído por um analisador lexical, um analisador sintáctico e uma análise semântica, quase inexistente neste caso, dada a simplicidade da linguagem. A geração de código é efectuada directamente a partir da árvore sintáctica através da selecção das instruções disponibilizadas pelo processador alvo.

  • analisador lexical: como é sabido o analisador lexical lê os caracteres de um ficheiro e agrupa-os em conjuntos, designados lexemas: identificadores, literais (constantes), operadores, terminadores, delimitadores, brancos e comentários, estes dois últimos sem interesse para o resto do compilador. O ficheiro y.tab.h define os lexemas (tokens), com mais de um carácter, que o analisador sintáctico pede ao analisador lexical. A cada um destes lexemas corresponde uma expressão regular no ficheiro scan.l, o analisador lexical. Quando a sequência de caracteres de entrada verifica uma determinada expressão regular, o código C que lhe está associado é executado. Este código devolve o número do lexema encontrado e, caso seja necessário, o seu valor na variável yylval.
  • analisador sintáctico: constituído pelo ficheiro gram.y, define quais os lexemas (com mais de um carácter) que necessita (%token), define a prioridade dos operadores (%left, %right e %nonassoc) e uma gramática LALR(1) depois do separador %%. Quando a uma regra verifica a sequência de lexemas de entrada, é activada e o código associado é executado. Este código pode continuar as verificações sintácticas que não foi possível efectuar na gramática e fazer verificações semânticas (incluindo a tabela de símbolos), produzindo uma estrutura de dados intermádia (uma árvore, no exemplo em estudo) ou gerando directamente o código resultante, se for possível fazer uma geração dirigida pela sintaxe (linguagens simples). Notar que as rotinas, para as declarações existentes em node.h, e tabid.h, encontram-se na biblioteca -lutil (que correspode ao ficheiro compact/lib/libutil.a).
  • geração de código final: é efectuada, no ficheiro pfix.brg, percorrendo a ávore em profundidade e seleccionando as instruções do processador, dependendo dos seus custos relativos. Este ficheiro define a forma de acesso à árvore sintáctica, os símbolos terminais da árvore sintáctica e a gramá das instruções e respectivos custos. No entanto, esta gramática descreve as instruções do processador alvo e não da linguagem de programação. A geração das instruções utiliza as sequências definidas no ficheiro postfix.h, permitindo abstrair alguns dos pormenores do processador alvo. Para tal utiliza as rotinas e estruturas declaradas no ficheiro node.h (árvore sintáctica).

 

7 - Compiladores alternativos para a linguagem compact

Substituindo um ou mais ficheiros do compilador anterior pode-se produzir:

  1. Geração de código ARM.
    A geração de có para o processador ARM é idêntica ao compilador original para Pentium, onde o seleccionador de instruções pfix.brg é subtituído por arm.brg:
      	prompt$  byacc -dv gram.y
      	prompt$  flex -l scan.l
      	prompt$  pburg -T arm.brg
      	prompt$  gcc -o pfarm -DpfARM -DYYDEBUG -I../lib y.tab.c lex.yy.c yyselect.c -L../lib -lutil -lfl
      	
    Notar que a alteração reside em indicar a opção de compilação -DpfARM, que substitui as sequências de instruções necessárias. Existem opções para gerar código i386 em formato AT&T (-DpfI386GAS, usando as em vez de nasm) ou 64-bits (-DpfAMD64, usando runtime/linux64/librun.a e nasm -felf64 em vez de nasm -felf).

    A execução dos exemplos necessita de um processador ARM (um sistema android, por exemplo):

      	prompt$  ./pfarm div.cpt
      	prompt$  as div.asm
      	prompt$  ld -o div div.o ../runtime/arm/librun.a
      	prompt$  ./div
      	
    ou de um emulador como, por exemplo o gnuarm:
      	prompt$  ./pfarm div.cpt
      	prompt$  arm-elf-as div.asm
      	prompt$  arm-elf-ld -o div div.o ../runtime/arm/librun.a
      	prompt$  arm-none-linux-gnueabi div
      	
  2. Compilador dirigido pela sintaxe.
    Como a linguagem compact é muito simples, é possível gerar o código durante a análise sintática. Para tal o ficheiro syntax.y é utilizado, em vez do gram.y, com
      	prompt$  byacc -dv syntax.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o syntax -DYYDEBUG -I../lib y.tab.c lex.yy.c -L../lib -lutil -lfl
      	
  3. Interpretador.
    Em vez de compilar cada programa em compact para um executável para posterior execução, um interpretador executa o imediatamente o programa. Para construir o interpretador, o analisador sintático é substituído pelo ficheiro tree.y que produz uma árvore sintática genérica. A interpretação da árvore é efectuada pelo ficheiro interp.c. O compilador é gerado com
      	prompt$  byacc -dv tree.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o interp -DYYDEBUG -I../lib y.tab.c lex.yy.c interp.c -L../lib -lutil -lfl
      	
    Para interpretar um programa escrito em compact basta passar como argumento o ficheiro (com a extensão cpt) a ser executado:
      	prompt$  ./interp div.cpt
      	
  4. Geração de código C.
    Em vez de compilar para código máquina (Pentium ou outro), o compilador pode gerar uma outra linguagem de alto nível que seja, pelo menos, tão poderosa como a linguagem a processar. Assim, para gerar C a partir de compact basta produzir código C a partir da árvore sintática genérica, como no caso do interpretador, com
      	prompt$  byacc -dv tree.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o trans -DYYDEBUG -I../lib y.tab.c lex.yy.c trans.c -L../lib -lutil -lfl
      	
    Para traduzir um programa escrito em compact para a linguagem C e gerar um executável pelo compilador de C:
      	prompt$  ./trans div.cpt
      	prompt$  cc -o div div.c
      	prompt$  ./div
      	
  5. Geração de código Pentium com reserva de registos greedy.
    Em vez de usar as sequências definidas no ficheiro postfix.h, pode-se gerar directamente as instruções do processador. Para tal, acede-se directamente aos registos do processador, sendo necessário efectuar a reserva dos registos a utilizar. Neste exemplo, utiliza-se o algoritmo mais simples, e menos eficiente, onde os registos são reservados sempre que pedidos e libertados de seguida (reserva greedy). Para mais, não se efectua spilling, isto é, quando os registos são insuficientes é gerado um erro, em vez de procurar libertar um registo que não seja imediatamente necessário, voltando a recarregar mais tarde o valor libertado (temporariamente salvaguardado na memória, em geral na pilha).
      	prompt$  byacc -dv gram.y
      	prompt$  flex -l scan.l
      	prompt$  pburg -T i386.brg
      	prompt$  gcc -o compact -DYYDEBUG -I../lib y.tab.c lex.yy.c yyselect.c -L../lib -lutil -lfl
      	
    Existe também uma versão para arm designada por android.brg, pelo que basta substituir i386.brg por android.brg no exemplo acima.
  6. Geração de código Pentium sem optimização.
    Caso não se utilize o seleccionador de instruções pburg (ou equivalente), pode-se assumir que o processador não possui registos permanentes e guardar os valores nas pilha. O processo fica simplificado pois existe uma só instrução para cada operação da árvore sintática genérica. Os ficheiros postfix.h e postfix.c contêm as instruções Pentium de pilha (não tirando partido de nenhum dos registos) e o gerador que percorre a árvore. Assim, para gerar código Pentium de pilha a partir da árvore sintática genérica, como no caso do interpretador, basta substituir o ficheiro interp.c pelo ficheiro postfix.c, com
      	prompt$  byacc -dv tree.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o postfix -DYYDEBUG -I../lib y.tab.c lex.yy.c postfix.c -L../lib -lutil -lfl
      	
  7. Geração de código de debug com postfix para Pentium .
    O ficheiro stab.c gera código de debug para permitir que o gdb possa executar os exemplos escritos na linguagem compact. Assim, pode-se visualizar, linha a linha, a execução do exemplo e inspeccionar ou alterar os valores das variáveis, tal como num programa em C. A rotina stab() define os tipos de dados (por exemplo, inteiro em vez de int), o ficheiro com o código fonte e os números de linha das instruçães geradas. O código gerado deve ser montado (assembled) pelo as (não pelo nasm, pois este não sabe processar o formato de debug do gdb).
  8. Geração de bytecodes Java.
    A máquina virtual Java já é um processador de pilha, pelo que o processo de geração é semelhante à geração postfix
      	prompt$  byacc -dv tree.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o javacpt -DYYDEBUG -I../lib y.tab.c lex.yy.c javacpt.c -L../lib -lutil -lfl
      	
    Os ficheiros gerados pelo compilador (.j) devem ser compilados em .class pela ferramenta jasmin antes de serem executados, pois o compilador apenas gera bytecodes java:
      	prompt$  ./javacpt div.cpt
      	prompt$  jasmin div.j
      	prompt$  java div
      	
  9. Geração de bytecodes .net.
    Tal como a máquina virtual Java, o ambiente .net utiliza uma linguagem assembly, designada por MSIL, sendo o compilador gerado com
      	prompt$  byacc -dv tree.y
      	prompt$  flex -l scan.l
      	prompt$  gcc -o msilcpt -DYYDEBUG -I../lib y.tab.c lex.yy.c msilcpt.c -L../lib -lutil -lfl
      	
    Os ficheiros gerados pelo compilador (.il) devem ser compilados antes de serem executados, pois o compilador gera assembly:
      	prompt$  ./msilcpt div.cpt
      	prompt$  ilasm div.il
      	prompt$  ./div