Skip to content

Home

Jump to bottom
Iago Lourenço edited this page Nov 13, 2022 · 4 revisions

Introdução

A linguagem LPD é uma linguagem de programação simples, desenvolvida para a disciplina de Contrução de Compiladores

O intuito deste projeto é criar um compilador para essa linguagem descrevendo os módulos léxico, sintático e semântico, gerando no final um arquivo com linguagem de máquina.

E também criar uma máquina virtual onde esse código de máquina (assembly) será executado.

Documentação

Descrição BNF da Linguagem de Programação Simplificada

<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 : { }

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 .

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.

Tecnologias utilizadas:

@iaglourenco @fabioirokawa @marcoslelis

© 2022 Todos os direitos reservados.

Clone this wiki locally