Skip to content

Compiler Construction

Jump to bottom
João Medeiros edited this page Dec 11, 2023 · 12 revisions

Introduction

O processo de construção de compiladores envolve a criação de um software, denominado parser, capaz de reconhecer e analisar um programa escrito na linguagem definida por uma gramática.

Dado um programa escrito na linaguem definida, o parser deve ser capaz de construir uma estrutura de dados, normalmente uma árvore sintática ou alguma outra estrutura hirárquica, enquanto verifica se a sintáxe do programa está correta. Eles podem ser definidos em dois grupos:

  • Top down: ;
  • Bottom up: .

Classificação dos tipos clássicos de parsers.

flowchart LR
    parser --> top-down
    parser --> bottom-up

    top-down --> RD
    top-down --> LL

    RD --> PEG
    LL --> LL1["LL(1)"]

    bottom-up --> LR
    bottom-up --> OP

    LR --> LR0["LR(0)"]
    LR --> SLR1["SLR(1)"]
    LR --> LALR1["LALR(1)"]
    LR --> CLR1["CLR(1)"]
Loading
  • Recursive descent (RD): ;
  • Left-to-right, leftmost derivation (LL): ;
  • Left-to-right, rightmost derivation (LR): ;
  • Operator Precedence (OP): .

Hand-written

Tools

Lexical Analisys

Flex

%{
// prologue
%}

%%
// lexical rules
%%

// epilogue

%{ 
#include<stdio.h> 
#include<string.h> 
%} 
  
%% 
\+ {printf(" add ");}

- {printf(" sub ");}

([0-9])* {printf(" num ");}

[a-z]([a-z0-9])* {printf(" id ");}
%% 
  
int yywrap(void){} 
  
int main() 
{    
    yylex(); 
  
    return 0; 
}

Syntactical Analysis

Bison

Manual.

%{
// prologue
%}

// bison declarations

%%
// grammar rules
%%

// epilogue

Semantic Analysis

Code Generation

Considere o seguinte progama minimalista escrito em linguagem C.

#include <stdlib.h>

void main(void)
{
    exit(0);
}

Em termos gerais, esse programa apenas inicia a função main() e termina sua execução em seguida com uma chamada de sistema a função exit() passando como parâmetro o valor 0 (zero). Um programa que simplismente termina de forma correta é um ponto de partida razoável para entender como o programa em questão se comunica com o sistema operacional. Para que possamos escrever um programa equivalente em linguagem de montagem, é necessário compreender que a comunicação com o sistema operacional se dá por meio de passagem de parâmetros por registradores e uma posterior chamada de sistema. No exemplo minimalísta em C, a função exit() é responsável, dentre outras coisas, por utilizar a chamada de sistema exit. Utilizando o comando man 2 exit, é possível verificar a seguinte sinopse da chamada de sistema.

SYNOPSIS
       #include <unistd.h>

       void _exit(int status);

Cada função de chamada de sistema possui um número associado, definido pelo sistema operacional, que é utilizado para informá-lo por meio de um registrador. No caso da arquitetura em questão, esse registrador é o rax. Dessa forma, para que o sistema operacional execute a chamada exit, é necessário descobrir o valor associado à ela. Como descrito no trecho do manual acima, essa informação pode ser encontrado no arquivo unistd.h. Na máquina utilizada nesse experimento, essa informação encontra-se no arquivo /usr/include/x86_64-linux-gnu/asm/unistd_64.h.

[...]
#define __NR_exit 60
[...]

Portanto, para que o sistema operacional execute a chamada exit, é necessário antes colocar no registrador rax o valor 60. Isso pode ser feito com o operador mov, resultando na instrução: mov rax, 60. Em seguida, é necessário informar o parâmetro status 0 da função exit. Isso deve ser feito por meio do registrador rdi. Utilizando novamente o operador mov, tem-se a instrução : mov rdi, 0. Após essas duas instruções, é possível realizar a chamada de sistema exit utilizando a chamada syscall. A seguir, é apresentado o programa equivalente em linguagem de montagem para a arquitetura Intel x86_64.

        global _start          ; ponteiro de entrada padrao

        section .text          ; segmento de texto
_start: mov rax, 60            ; rax <- exit syscall number
        mov rdi, 0             ; exit 1o parametro (0)
        syscall                ; chamada de sistema

Além das instruções descritas para realizar a chamada de sistema, tem-se nas duas primeiras linhas: (1) o uso da diretiva global e do rótulo _start para indicar ao linker o endereço de memória que deve ser executado no início do programa; e (2) o uso da diretiva section para indicar o começo do segmento de texto .text do programa.

NOTA - No contexto de programação em linguagem de montagem, tem-se que o programa pode ser dividio em até 3 segmentos principais: .text, .data e .bss. O primeiro é para o código em si, o segundo para dados inicializados e o terceiro para dados não inicializados (ver mais).

Para transformar o programa em linaguem de montagem acima em código objeto executável, é possível utitilizar o assembler nasm e o linker ld.

term@sec$ nasm -f elf64 minimal.asm
term@sec$ ld minimal.o -o minimal

A opção -f elf64 do comando nasm indica o formato de código objeto que deve ser gerado pelo nasm. Nesse experimeto, o tipo deve ser ELF64, uma vez que a arquitetura da máquina é x86_64. O programa nasm utiliza a descrição em linguagem de montagem minimal.asm para criar o código objeto minimal.o no formato ELF64. Após isso, o programa ld processa o código objeto minimal.o para criar o arquivo executável minimal (nome indicado pela opção -o).

term@sec$ ./minimal
term@sec$ echo $?
0

Como esperado, a execução do programa inicia e termina com sucesso. É possível verificar o valor do parâmetro da chamada de sistema exit(0) imprimindo com o comando echo o conteúdo da variável de ambiente $?, que guarda o falor de retorno do último programa executado.

NOTA - Como exercício, pode-se verificar que ao alterar a instrução mov rdi, 0 para, por exemplo, mov rdi, 1 o valor de retorno verificado pelo comando echo $? passa a ser 1.

            global _start           ; ponteiro de entrada padrao

; -----------------------------------------------------------------------------
            section .text           ; segmento de texto

_start:
            xor rax, rax
            xor rcx, rcx
            mov al, [var_a]
            mov cl, [var_b]
            cmp al, cl
            je equal

print:      mov rax, 1              ; system call for write
            mov rdi, 1              ; file handle 1 is stdout
            mov rsi, message_a      ; address of string to output
            mov rdx, 7              ; number of bytes
            syscall                 ; chamada de sistema

equal:      mov rax, 1              ; system call for write
            mov rdi, 1              ; file handle 1 is stdout
            mov rsi, message_b      ; address of string to output
            mov rdx, 9              ; number of bytes
            syscall                 ; chamada de sistema

            mov al, [var_a]
            sub al, 1
            mov [var_a], al
            cmp al, 0
            jg _start              ; while true

exit:       mov rax, 60             ; rax <- exit syscall number
            mov rdi, 0              ; exit 1o parametro (0)
            syscall                 ; chamada de sistema

; -----------------------------------------------------------------------------
            section .data           ; segmento de dados
var_a:      db  3                   ; 
var_b:      db  3                   ; 
message_b:  db  " equal ", 10       ; note the newline at the end
message_a:  db  " not "             ; note the newline at the end

; -----------------------------------------------------------------------------
            section .bss            ; segmento de blocos
buffer:     resb    64              ; reserve 64 bytes
result:     resw    1               ; reserve a word
vector:     resq    10              ; array of ten reals

Clone this wiki locally