Construindo um compilador em java

O que você espera que a gente responda? O compilador inteiro pra você pronto?
Sem você dizer onde exatamente está sua dúvida, e postar o código do que tentou fazer, fica impossível te ajudar.

Você pode usar o ANTLR para facilitar sua tarefa?

Olá nathandoamaral

Gostei dessa ideia do compilador (infelizmente não posso te ajudar , pq não tenho todo esse conhecimento ), mas, não desamina não, se vc conseguir post o resultado pra gente ver, ok :?:

:thumbup:

Ferramentas para construir compiladores são o jbison e o jflex. Meu professor de compiladores sempre desenvolvia com java e eu achava um trabalho muito nobre. Eu não tenho know how nesse quesito para te ajudar.

bom, olhando apenas os automatos que você postou aqui está o que eu consegui observar:

1 - Você vai precisar de pelo menos dois tokkens para representar números (um para inteiro e outro para real), portanto ou seu procedimento número ira retornar 2 resultados dependendo se o cara digitou um ponto ou não, ou você ira criar um automato separado para tratar isso.

2- Geralmente identificadores não podem começar por digitos e seu procedimento identificador não trata isso.

Se você esta construindo o analisador léxico na mão, posta o trecho de código em que você esta com dificuldade se o problema não for com o automato.

Abs.

Carlos

nathandoamaral:

Galera to construindo um compilador em java e estou com dificuldades em implementa os operadores aritmeticos e em faze o programa distinguir inteiros de reais

esse é alguns automatos que tenho que passar para a linguagem java e não consigo

//procedimento para verificar simbolos (+,-,*,/) ou caracteres ( [ , ] , ( , ) )
procedimento identificador; 
{ 
 enquanto caracter é LETRA ou DÍGITO faça { 
  símbolo = símbolo || caracter; 
  caracter = leia_caracter(); 
 } 
 return( 1, símbolo); 
}
// procedimento para reconhecer um numero
procedimento número; 
{ 
 enquanto caracter é DÍGITO { 
  símbolo = símbolo || caracter; 
  caracter = leia_caracter(); 
 } 
 return( 2, símbolo ); 
}

//operadores
procedimento operador() 
{ 
 obteve_símbolo = TRUE; 
 se caracter = ?+? { 
  código = código_de_adição; 
 } senão se caracter = ?*? { 
  caracter = leia_caracter(); 
  se caracter = ?*? { 
   código = código_de_exponenciação; 
  } senão { 
   código = código_de_multiplicação; 
  } 
 } senão se caracter = ?=? { 
  código = código_atribuição; 
 } senão { 
  escreva advertência; 
  obteve_símbolo = FALSE; 
 } 
}

Que tal desenhar a máquina de estados que reconhece os símbolos? O autômato que você escreveu parece muito, muito, muito incompleto. Em particular, os autômatos para reconhecer números reais são normalmente bem complexos.

Dando um exemplo em:

http://flylib.com/books/en/2.354.1.107/1/

Veja o diagrama “Finite state machine recognizing floating-point numbers”

Escrever autômatos, sem ter um diagrama de estados tal como o que lhe indiquei, é bem complicado e fica basicamente um código impossível de debugar ou de entender.

Se puder, use um compilador de compiladores como o Antlr ou o Javacc.

Pra fazer o lexer (pra gerar os tokens), você precisa de um autômato determinístico finito (http://en.wikipedia.org/wiki/Deterministic_finite_automaton). Dá pra escrever na mão usando um switch para testar o estado do autômato e cada estado com um switch para testar cada caractere do input

O parser dá pra escrever na mão criando um Recursive Descent Parser (http://en.wikipedia.org/wiki/Recursive_descent_parser)

O parser retornaria uma árvore que aí você poderia criar os métodos eval() em cada classe da árvore

Acho que isso resolve seu problema

Na verdade esse é so um esboço do que eu quero o que tenho q fazer mesmo é uma classe que identifica operações aritmeticas e não to conseguindo escrever o codigo para tal o meu reconhecedor de palavras reservadas ta pronto minha tabela de tokens. outra coisa eh como definir o tamanho do meu numero tipo um smallint tem um tamanho e o interger tem outro como fazer esse calculo ja procurei na net e não acho nada e minha cabeça ta muito fraca pra fazer isso. alguem ajuda ai !!!

Cara, esse é o problema de querer fazer isso com uma linguagem de “alto nível”. Você não tem controle para criar novos tipos como na linguagem “c” com a palavra reservada typedef. Eu imagino que você terá de conviver com essa limitação. Posso estar enganado, mas seus tipos terão de se basear nos tipos da jvm, a não ser que você crie um linker a parte do hotspot.
A não ser que você queira desenvolver somente o analisador léxico e o semântico. Mas aí já não é um compilador.

Bom, você terá que tratar a questão do smallint e do integer nas fases de análise semântica (tratando como tipos diferentes, fazendo a checagem de tipos, verificando se estão atribuindo valores a suas variáveis do tamanho correto e tratando as coerções e casts necessários) e na geração de código você ira gerar o assembly correspondente daquele tipo (assumindo que você esta gerando código assembly).

Quanto ao problema do código, seria mais fácil você colocar aqui os trechos de código que você esta com dificuldade para o pessoal poder te ajudar melhor

juliocbq:

Cara, esse é o problema de querer fazer isso com uma linguagem de “alto nível”. Você não tem controle para criar novos tipos como na linguagem “c” com a palavra reservada typedef. Eu imagino que você terá de conviver com essa limitação. Posso estar enganado, mas seus tipos terão de se basear nos tipos da jvm, a não ser que você crie um linker a parte do hotspot.
A não ser que você queira desenvolver somente o analisador léxico e o semântico. Mas aí já não é um compilador.

Desculpe, não consegui entender o que você quis dizer. Se eu fizer um compilador em java que gere código assembly vou poder usar os tipos que quiser. Ano passado construi um compilador em Prolog como trabalho da universidade que gerava assembly e utilizava os tipos que eu quisesse definir (quero dizer, não fiquei limitado ao sistema de tipos do Prolog)

Primeira coisinha - você já desenhou o diagrama de mãquina de estados (ou então as expressões regulares que definem a linguagem BNF)?
Sem desenhar o tal diagrama de estados ou a gramática você não chega a lugar nenhum.
O autômato deve ser escrito só depois de desenhar o diagrama e definir a gramática - e é um trabalho meramente braçal.
Se você está pensando (e penando) para fazer o autômato, está fazendo errado e gastando errado seu tempo - você tem de caprichar na gramática.
Existem ferramentas, como o ANTLR e o JAVACC, que transformam a gramática em um autômato, economizando o trabalho braçal.

Não se preocupe, por enquanto, com essa sutileza do tipo “smallint” x “integer” (com “interger” você não vai achar as coisas “cetas” na “InteNet” … )
Em Java, por exemplo, todas as constantes inteiras são int, a menos que você use um “L” no final delas. Você não precisa seguir o Java, pode seguir a notação de outra linguagem. Por exemplo, você pode ter constantes de apenas 2 tipos - int quando você não tem um “.” ou um “E” na definição do constante, double quando você tem um “.” e/ou um “E” na definição da constante.

lordcarlos:

juliocbq:

Cara, esse é o problema de querer fazer isso com uma linguagem de “alto nível”. Você não tem controle para criar novos tipos como na linguagem “c” com a palavra reservada typedef. Eu imagino que você terá de conviver com essa limitação. Posso estar enganado, mas seus tipos terão de se basear nos tipos da jvm, a não ser que você crie um linker a parte do hotspot.
A não ser que você queira desenvolver somente o analisador léxico e o semântico. Mas aí já não é um compilador.

Desculpe, não consegui entender o que você quis dizer. Se eu fizer um compilador em java que gere código assembly vou poder usar os tipos que quiser. Ano passado construi um compilador em Prolog como trabalho da universidade que gerava assembly e utilizava os tipos que eu quisesse definir (quero dizer, não fiquei limitado ao sistema de tipos do Prolog)

É verdade, mas para você gerar assembly você precisa de um linker, que é a terceira parte para se ter um compilador. Qual você usou no seu compilador de prolog?
Também é uma dúvida que eu tenho. Como você definiu a quantidade de bits de cada tipo?

juliocbq:

É verdade, mas para você gerar assembly você precisa de um linker, que é a terceira parte para se ter um compilador. Qual você usou no seu compilador de prolog?
Também é uma dúvida que eu tenho. Como você definiu a quantidade de bits de cada tipo?

A sim, meu compilador apenas gerava o assembly, dai eu chamava o gas como assembler e o ld como linker.
Eu precisei tratar os tamanhos apenas na analise semantica, verificando se atribuições eram validas, necessidades de coerção etc, e na hora de gerar o assembly eu usava os tipos do gas para cada tipo de primitivo que meu compilador suportava.

Agora entendi o que você quis dizer, que se precisasse criar o assembler e o linker como parte do compilador isso poderia ser um problema. Mas pelo que eu estudei, e o que meu professor passou, os compiladore geralmente vão até o assembly apenas, delegando o resto do trabalho para outros softwares. O gcc funciona assim como pode ser visto no diagrama da página 5 deste pdf: http://gcc.gnu.org/ml/gcc-help/2004-10/msg00060/GccPorting.pdf

lordcarlos:

juliocbq:

É verdade, mas para você gerar assembly você precisa de um linker, que é a terceira parte para se ter um compilador. Qual você usou no seu compilador de prolog?
Também é uma dúvida que eu tenho. Como você definiu a quantidade de bits de cada tipo?

A sim, meu compilador apenas gerava o assembly, dai eu chamava o gas como assembler e o ld como linker.
Eu precisei tratar os tamanhos apenas na analise semantica, verificando se atribuições eram validas, necessidades de coerção etc, e na hora de gerar o assembly eu usava os tipos do gas para cada tipo de primitivo que meu compilador suportava.

Agora entendi o que você quis dizer, que se precisasse criar o assembler e o linker como parte do compilador isso poderia ser um problema. Mas pelo que eu estudei, e o que meu professor passou, os compiladore geralmente vão até o assembly apenas, delegando o resto do trabalho para outros softwares. O gcc funciona assim como pode ser visto no diagrama da página 5 deste pdf: http://gcc.gnu.org/ml/gcc-help/2004-10/msg00060/GccPorting.pdf

Sim, por exemplo o freepascal usa o mesmo linker que o gcc usa.
http://www.freepascal.org/

Mas a minha dúvida ainda é a seguinte. Imagine um compilador de pascal para bytecode jvm. Eu conseguiria criar um tipo primitivo inteiro de 16 bits por exemplo?

juliocbq:

Mas a minha dúvida ainda é a seguinte. Imagine um compilador de pascal para bytecode jvm. Eu conseguiria criar um tipo primitivo inteiro de 16 bits por exemplo?

Bom, não conheço muito sobre o funcionamento da jvm, mas acredito que seu compilador só precisara abrir um arquivo e escrever as instruções do seu programa em bytecode, a alocação de memória propriamente dita sera feita pela máquina virtual desde que você escreva no arquivo o tipo correto (colocando o equivalente a long ou integer no arquivo de bytecodes)

Por exemplo, numa pesquisa rápida encontrei a instrução em bytecode “dload”, que carrega um valor double para uma variável. Não importa muito como você represente esse valor double no seu computador (pode ser até como uma string por exemplo), desde que você escreva no arquivo .class a instrução corretamente a máquina virtual vai executa-la

juliocbq:

lordcarlos:

juliocbq:

É verdade, mas para você gerar assembly você precisa de um linker, que é a terceira parte para se ter um compilador. Qual você usou no seu compilador de prolog?
Também é uma dúvida que eu tenho. Como você definiu a quantidade de bits de cada tipo?

A sim, meu compilador apenas gerava o assembly, dai eu chamava o gas como assembler e o ld como linker.
Eu precisei tratar os tamanhos apenas na analise semantica, verificando se atribuições eram validas, necessidades de coerção etc, e na hora de gerar o assembly eu usava os tipos do gas para cada tipo de primitivo que meu compilador suportava.

Agora entendi o que você quis dizer, que se precisasse criar o assembler e o linker como parte do compilador isso poderia ser um problema. Mas pelo que eu estudei, e o que meu professor passou, os compiladore geralmente vão até o assembly apenas, delegando o resto do trabalho para outros softwares. O gcc funciona assim como pode ser visto no diagrama da página 5 deste pdf: http://gcc.gnu.org/ml/gcc-help/2004-10/msg00060/GccPorting.pdf

Sim, por exemplo o freepascal usa o mesmo linker que o gcc usa.
http://www.freepascal.org/

Mas a minha dúvida ainda é a seguinte. Imagine um compilador de pascal para bytecode jvm. Eu conseguiria criar um tipo primitivo inteiro de 16 bits por exemplo?

o freepascal gera bytecode jvm. achei interessante mas ainda tive de ver em detalhes.

GilsonNunes:

juliocbq:

lordcarlos:

juliocbq:

É verdade, mas para você gerar assembly você precisa de um linker, que é a terceira parte para se ter um compilador. Qual você usou no seu compilador de prolog?
Também é uma dúvida que eu tenho. Como você definiu a quantidade de bits de cada tipo?

A sim, meu compilador apenas gerava o assembly, dai eu chamava o gas como assembler e o ld como linker.
Eu precisei tratar os tamanhos apenas na analise semantica, verificando se atribuições eram validas, necessidades de coerção etc, e na hora de gerar o assembly eu usava os tipos do gas para cada tipo de primitivo que meu compilador suportava.

Agora entendi o que você quis dizer, que se precisasse criar o assembler e o linker como parte do compilador isso poderia ser um problema. Mas pelo que eu estudei, e o que meu professor passou, os compiladore geralmente vão até o assembly apenas, delegando o resto do trabalho para outros softwares. O gcc funciona assim como pode ser visto no diagrama da página 5 deste pdf: http://gcc.gnu.org/ml/gcc-help/2004-10/msg00060/GccPorting.pdf

Sim, por exemplo o freepascal usa o mesmo linker que o gcc usa.
http://www.freepascal.org/

Mas a minha dúvida ainda é a seguinte. Imagine um compilador de pascal para bytecode jvm. Eu conseguiria criar um tipo primitivo inteiro de 16 bits por exemplo?

o freepascal gera bytecode jvm. achei interessante mas ainda tive de ver em detalhes.

Gilson, o freepascal não compila para jvm. É só um exemplo que quis passar.

Gera sim.

veja esse link

http://wiki.freepascal.org/FPC_JVM

lordcarlos:

juliocbq:

Mas a minha dúvida ainda é a seguinte. Imagine um compilador de pascal para bytecode jvm. Eu conseguiria criar um tipo primitivo inteiro de 16 bits por exemplo?

Bom, não conheço muito sobre o funcionamento da jvm, mas acredito que seu compilador só precisara abrir um arquivo e escrever as instruções do seu programa em bytecode, a alocação de memória propriamente dita sera feita pela máquina virtual desde que você escreva no arquivo o tipo correto (colocando o equivalente a long ou integer no arquivo de bytecodes)

Por exemplo, numa pesquisa rápida encontrei a instrução em bytecode “dload”, que carrega um valor double para uma variável. Não importa muito como você represente esse valor double no seu computador (pode ser até como uma string por exemplo), desde que você escreva no arquivo .class a instrução corretamente a máquina virtual vai executa-la

sim, mas dload sempre carrega 64 bits? O que eu queria mesmo saber é se existe uma maneira de criar tipos primitivos. Por exemplo eu fazer um set de inteiros (jint8, jint16, jint32, …) e po aí vai. Porque até onde eu entendo todas as linguagens da jvm geram o mesmo bytecode, ou seja, tanto faz programar em java groovy ou scala para jvm. O desempenho desses programas sempre serão muito semelhantes no final. Agora do contrário, em c ou c++ eu consigo alocar a quantidade de recursos para o tipo que eu bem entender. Poderia ter um inteiro com 4 bits por exemplo. Eu digo isso porque a capacidade dos tipos influencia drasticamente no desempenho de um programa. Se você contar até 1000 por exemplo incrementando um inteiro de 16 bits vs um inteiro de 32 vai ver a difrença que isso gera no resultado final. Sei que o hotspot faz essas otimizações quando o jit entra em ação. Mas a nível de bytecode acredito que não há como eu fugir de um inteiro de 32 bits.

GilsonNunes:

Gera sim.

veja esse link

http://wiki.freepascal.org/FPC_JVM

Rapaz, muito interessante isso, Eu não sabia que ele compilava bytecode também.

juliocbq:

sim, mas dload sempre carrega 64 bits? O que eu queria mesmo saber é se existe uma maneira de criar tipos primitivos. Por exemplo eu fazer um set de inteiros (jint8, jint16, jint32, …) e po aí vai. Porque até onde eu entendo todas as linguagens da jvm geram o mesmo bytecode, ou seja, tanto faz programar em java groovy ou scala para jvm. O desempenho desses programas sempre serão muito semelhantes no final. Agora do contrário, em c ou c++ eu consigo alocar a quantidade de recursos para o tipo que eu bem entender. Poderia ter um inteiro com 4 bits por exemplo. Eu digo isso porque a capacidade dos tipos influencia drasticamente no desempenho de um programa. Se você contar até 1000 por exemplo incrementando um inteiro de 8 bits vs um inteiro de 16 vai ver a difrença que isso gera no resultado final. Sei que o hotspot faz essas otimizações quando o jit entra em ação. Mas a nível de bytecode acredito que não há como eu fugir de um inteiro de 32 bits.

Acredito que não, pelo que li a instrução dload sempre carrega 64 bits. A máquina virtual do java possui instruções específicas para cada tipo primitivo, então sem mudar o bytecode acho que não da para criar novos tipos primitivos como um inteiro de 128 bits por exemplo. Mas essa é uma limitação da máquina virtual, não do compilador. Uma vez disponibilizado essas instruções você pode alterar seu compilador para escrever elas e usar em sua linguagem que esta criando

dload carrega um double (tipo de ponto flutuante, de 64 bits). Tem certeza que vocês estavam falando de doubles?

De fato, na verdade é melhor você trabalhar com int em vez de char ou short (ambos tipos de 16 bits), mas isso também reflete as máquinas de 32 e de 64 bits, onde é muito mais rápido trabalhar com um int que trabalhar com um char ou short individualmente - normalmente uma instrução adicional de máquina é necessária para converter um short (16 bits) para um int de 32 bits ou um long de 64 bits. Em máquinas Intel, a instrução se chama MOVSX ou MOVSXD, ou então CBW ou CWDE.

Um algoritmo como o strlen (determina o comprimento de uma string em C procurando a posição do primeiro byte \0 ) normalmente nunca é implementado da forma estúpida:

int strlen (char *s) {
    int n = 0;
    while (*s++) 
        n++;
    return n;
}

Em vez disso, normalmente esse código é implementado em assembly carregando 4 ou 8 bytes de cada vez (em vez de um de cada vez) e determinando, através de uns truques, qual é a posição do primeiro byte 0 nos 4 bytes carregados.

É por isso que os Java bytecodes não têm instruções (exceto por bastore, castore, sastore, baload, caload, saload) que lidam diretamente com esses tipos de dados mais “estreitos” que os de 32 bits.

lordcarlos:

juliocbq:

sim, mas dload sempre carrega 64 bits? O que eu queria mesmo saber é se existe uma maneira de criar tipos primitivos. Por exemplo eu fazer um set de inteiros (jint8, jint16, jint32, …) e po aí vai. Porque até onde eu entendo todas as linguagens da jvm geram o mesmo bytecode, ou seja, tanto faz programar em java groovy ou scala para jvm. O desempenho desses programas sempre serão muito semelhantes no final. Agora do contrário, em c ou c++ eu consigo alocar a quantidade de recursos para o tipo que eu bem entender. Poderia ter um inteiro com 4 bits por exemplo. Eu digo isso porque a capacidade dos tipos influencia drasticamente no desempenho de um programa. Se você contar até 1000 por exemplo incrementando um inteiro de 8 bits vs um inteiro de 16 vai ver a difrença que isso gera no resultado final. Sei que o hotspot faz essas otimizações quando o jit entra em ação. Mas a nível de bytecode acredito que não há como eu fugir de um inteiro de 32 bits.

Acredito que não, pelo que li a instrução dload sempre carrega 64 bits. A máquina virtual do java possui instruções específicas para cada tipo primitivo, então sem mudar o bytecode acho que não da para criar novos tipos primitivos como um inteiro de 128 bits por exemplo. Mas essa é uma limitação da máquina virtual, não do compilador. Uma vez disponibilizado essas instruções você pode alterar seu compilador para escrever elas e usar em sua linguagem que esta criando

era isso que eu estava tentando explicar mais acima. Lidar com inteiros de 32 bits é muito custoso a não ser que haja um esquema debaixo do hotspot que ajusta tanto para 8, 16, 32, ou 64 de acordo com o algoritmo(algumas estruturas de laços) e plataforma alvo.