compi{LPD}lador

Introdução

Este projeto foi feito para a disciplina de Construção de Compiladores da PUC-Campinas e consiste na criação de um compilador para a linguagem didádica LPD.

Foi definida uma linguagem didática e simples para a elaboração do projeto, sendo uma linguagem de programação estruturada semelhante à linguagem de programação estruturada PASCAL. Esta linguagem tem o nome de LPD (Linguagem de Programação Didática).

O compilador desenvolvido para esta linguagem, nomeado compi{LPD}lador contém os módulos léxico, sintático e semântico, que fazem a análise do código, gerando no final um arquivo com linguagem de máquina onde o mesmo será interpretado e executado por uma máquina virtual também criada pela equipe.

Este projeto foi desenvolvido em JavaScript puro e estilizado em CSS também puro, sem o uso de qualquer framework ou extensão, sendo capaz de rodar em praticamente todos os navegadores!

Documentação

Abaixo disponibilizamos a documentação da linguagem e dos conceitos abordados pela disciplina de Construção de Compiladores, assim como um resumo de cada módulo e conceito utilizado no compilador.

Notas de Aula de Compiladores

Módulos do compilador

Léxico

Este módulo é responsável por realizar a análise léxica do código fonte, ou seja, a leitura do código fonte e a identificação dos tokens. Para isso, o módulo léxico deve realizar a leitura do código fonte e, a cada caractere lido, deve verificar se o mesmo pertence a algum dos conjuntos de caracteres definidos na tabela de símbolos. Caso o caractere pertença a algum conjunto, o mesmo deve ser concatenado a uma lista que representa os tokens identificados no código. Caso o caractere não pertença a nenhum conjunto, um erro deve ser lançado indicando a linha e coluna do mesmo. O módulo léxico deve ser capaz de identificar os seguintes tokens:

Palavras reservadas
Identificadores
Números
Operadores aritméticos
Operadores relacionais
Pontuação
Comentários

A implementação do módulo léxico pode ser encontrada no arquivo lexico.js.

Descrição em BNF da linguagem

Para a descrição da linguagem LPD, foi utilizado a notação BNF (Backus-Naur Form), sendo uma notação para especificar gramáticas formais.

Espaços, tabulações, caracteres não imprimíveis e quebras de linha são ignorados.

Clique para expandir


                        <programa>::= programa <identificador> ; <bloco>.
                        

                        <bloco>::= [<etapa de declaração de variáveis>][<etapa de declaração de sub-rotinas>]<comandos>
                        

                        //Declarações
                        

                        <etapa de declaração de variáveis>::= var <declaração de variáveis>;{<declaração de variáveis>;}
                        

                        <declaração de variáveis>::= <identificador> {, <identificador>} : <tipo>
                        

                        <tipo> ::= (inteiro | booleano)
                        

                        <etapa de declaração de sub-rotinas> ::= (<declaração de procedimento>;|<declaração de função>;){<declaração de procedimento>;|<declaração de função>;}
                        

                        <declaração de procedimento> ::= procedimento <identificador>;<bloco>
                        

                        <declaração de função> ::= funcao <identificador>: <tipo>;<bloco>
                        

                        //Comandos
                        

                        <comandos>::= inicio<comando>{;<comando>}[;]fim
                        

                        <comando>::= (<atribuição_chprocedimento>|<comando condicional> |<comando enquanto> |<comando
                                        leitura> |<comando escrita> |<comandos>)
                        

                        <atribuição_chprocedimento>::= (<comando atribuicao>|<chamada de procedimento>)
                        

                        <comando atribuicao>::= <identificador> := <expressão>
                        

                        <chamada de procedimento>::= <identificador>
                        

                        <comando condicional>::= se <expressão> entao <comando> [senao <comando>]
                        

                        <comando enquanto> ::= enquanto <expressão> faca <comando>
                        

                        <comando leitura> ::= leia ( <identificador> )
                        

                        <comando escrita> ::= escreva ( <identificador> )
                        

                        //Expressões
                        

                        <expressão>::= <expressão simples> [<operador relacional><expressão simples>]
                        

                        <operador relacional>::= (!= | = | < | <= | > | >=)
                        

                        <expressão simples> ::= [ + | - ] <termo> {( + | - | ou) <termo> }
                        

                        <termo>::= <fator> {(\* | div | e) <fator>}
                        

                        <fator> ::= (<variável> | <número> | <chamada de função> | (<expressão>) | verdadeiro |
                            falso | nao <fator>)
                        

                        <variável> ::= <identificador>
                        

                        <chamada de função> ::= <identificador >
                        

                        //Números e identificadores
                        

                        <identificador> ::= <letra> {<letra> | <dígito> | \_ }
                        

                        <número> ::= <dígito> {<dígito>}
                        

                        <dígito> ::= (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
                        

                        <letra> ::= (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|
                                        A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)
                        

                        //Comentários
                        /*Uma vez que os comentários servem apenas como documentação do código fonte, ao realizar
                                        a compilação deste código faz-se necessário eliminar todo o conteúdo entre seus
                                        delimitadores.*/
                        

                        delimitadores : { }

Sintático

Este módulo é responsável por realizar a análise sintática do código fonte, ou seja, a verificação da estrutura gramatical do código fonte. Para isso, o módulo sintático deve realizar a leitura dos tokens gerados pelo módulo léxico e verificar se estes tokens estão de acordo com a gramática definida para a linguagem. Caso o token lido não esteja de acordo com a gramática, um erro deve ser lançado indicando a linha e coluna do mesmo

A partir do sintático os outros módulos são requisitados, fazendo com que o sintático seja o "motor" de todo o compilador orquestrando todos os outros módulos, produzindo no final de toda a execução o código em linguagem de máquina.

A implementação do módulo sintático pode ser encontrada no arquivo sintatico.js.

Semântico

Este módulo é responsável por realizar a análise semântica do código fonte, ou seja, verifica se as sentenças tem um significado coerente do ponto de vista da semântica da linguagem. O módulo possui funções que consultam a tabela de símbolos durante a analise de uma expressão e verifica se a sentença faz sentido verificando a tipagem e significado dos tokens.

O módulo possui funções como a conversão para o formato pós-fixo de expressões matemáticas facilitando várias tarefas de verificação como as definidas a seguir, além de controlar a inserção e manutenção da tabela de símbolos.

Verificação da ocorrência da duplicidade na declaração de um identificador
Verificação de uso de identificadores não declarados
Verificação de compatibilidade de tipos
Verificação dos comandos escreva e leia (variável inteira)
Verificação de chamadas de procedimento e função
Verificação dos operadores unários – , + , nao

É fácil perceber que as chamadas para o analisador semântico não passam de linhas de comandos a serem inseridos no “corpo” do analisador sintático, nos locais apropriados. Vale lembrar que a Linguagem LPD não permite a passagem de parâmetros nos procedimentos e funções. Caso isso fosse permitido, então deveríamos também verificar a consistência no número de argumentos e parâmetros, bem como sua compatibilidade de tipos.

A implementação do módulo semântico pode ser encontrada no arquivo semantico.js.

Tabela de Símbolos

A tabela de símbolos é uma estrutura de dados contendo um registro para cada identificador, com os campos contendo os atributos do identificador. As informações sobre o identificador são coletadas pelas fases de análise de um compilador e usada pelas fases de síntese de forma a gerar o código-alvo. Durante a Análise Lexical a cadeia de caracteres que forma um identificador é armazenada em uma entrada da tabela de símbolos. As fases seguintes do compilador acrescentam informações a esta entrada. A fase de geração utiliza as informações armazenadas para gerar o código adequado.

Para este projeto foi utilizado a tabela de símbolos como uma pilha sendo que uma vez terminada a compilação de um procedimento os símbolos locais são descartados.

Este modelo para a tabela, usando um vetor, supõe que as buscas serão sequenciais. Isso pode ser proibitivo se o número de símbolos for muito grande. A mesma “lógica” de funcionamento pode ser aplicada a outras organizações de tabela visando a melhoria no tempo de acesso.

A implementação da tabela de símbolos pode ser encontrada no arquivo tabelaSimbolos.js.

Geração de código

O módulo de geração de código é responsável por gerar o código em linguagem de máquina a partir do código fonte. Para isso é necessário que o código fonte esteja de acordo com a gramática da linguagem e que não haja erros semânticos para isso o módulo de geração de código é o último módulo a ser executado, pois ele é o responsável por gerar o código em linguagem de máquina, ou seja, o código final.

A seguir estão listadas as definições das instruções em linguagem de máquina:

START - Inicia o programa. Deve ser a primeira instrução do programa.
HLT - Finaliza o programa. Deve ser a última instrução do programa.
LDV k - Carrega o valor do local de memoria k no topo da memória.
LDC n - Carrega o valor n no topo da memória.
STR v - Armazena no local de memoria v o valor do topo da memória.
ADD - Soma os dois valores do topo da memória e armazena o resultado no topo da memória.
SUB - Subtrai os dois valores do topo da memória e armazena o resultado no topo da memória.
MULT - Multiplica os dois valores do topo da memória e armazena o resultado no topo da memória.
DIVI - Divide os dois valores do topo da memória e armazena o resultado no topo da memória.
INV - Inverte o sinal do valor do topo da memória.
AND - Realiza a operação lógica AND entre os dois valores do topo da memória de operandos e armazena o resultado no topo da memória.
OR - Realiza a operação lógica OR entre os dois valores do topo da memória de operandos e armazena o resultado no topo da memória.
NEG - Realiza a operação lógica NOT entre os dois valores do topo da memória de operandos e armazena o resultado no topo da memória.
CME - Compara se o valor do topo da memória é menor que o valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
CMA - Compara se o valor do topo da memória é maior que o valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
CEQ - Compara se o valor do topo da memória é igual ao valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
CDIF - Compara se o valor do topo da memória é diferente do valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
CMEQ - Compara se o valor do topo da memória é menor ou igual ao valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
CMAQ - Compara se o valor do topo da memória é maior ou igual ao valor do topo menos 1 da memória. Se for, o valor 1 é armazenado no topo da memória. Caso contrário, o valor 0 é armazenado no topo da memória.
RD - Lê um valor do teclado e armazena no topo da memória.
PRN - Imprime o valor do topo da memória.
ALLOC b,o - Aloca espaço na memória sendo b=base e o=offset.
DALLOC b,o - Desaloca espaço na memória sendo b=base e o=offset.
CALL f - Chama uma função f.
RETURN - Retorna o valor de uma função.
JMP p - Desvia o fluxo de execução para uma instrução com o rotulo p.
JMPF p - Desvia o fluxo de execução para uma instrução com o rotulo p se o valor do topo da memória for igual a 0.
NULL - Instrução nula. Não faz nada.

A implementação do módulo de geração de código pode ser encontrada no arquivo gerador.js.

Máquina virtual

A máquina virtual é responsável por executar o código gerado pelo compilador. Ela é composta por um conjunto de instruções, definidas anteriormente, que são executadas sequencialmente. A máquina virtual é composta por um espaço de programa e um espaço de memória.

O espaço de programa é composto por um conjunto de instruções que são executadas sequencialmente, salvo quando há uma instrução de desvio de fluxo. O espaço de memória é composto por um conjunto de células de memória que podem ser acessadas por meio de um endereço. Cada célula de memória pode armazenar um valor inteiro.

A máquina possui também uma interface para depuração, que permite visualizar o estado da máquina em cada instrução executada.

A implementação da máquina virtual pode ser encontrada no arquivo maquina.js.

Agradecimentos

Agradecemos ao professor Ricardo Luís de Freitas pela oportunidade de participar do projeto e por todo o conhecimento compartilhado durante o desenvolvimento do mesmo.

A todos os outros grupos que desenvolveram o mesmo projeto, e que contribuiram de alguma forma para o nosso aprendizado.