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.

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.

                        <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.