Compiladores..
Vanessa Leite
=D
--
>>Vanessa Leite
---
"Não se preocupe em entender. A vida ultrapassa todo entendimento." (Clarisse Lispector)
---
Ciência da Computação
Universidade Federal do Maranhão - UFMA
Laboratório de Processamento e Análise de Imagens - LabPAI
Rodrigo Strauss
polonesa, como se trata isso usando pilhas (existem vários exemplos na
net). Se quiser usar C++ para fazer :-D, veja o boost::tokenizer.
Rodrigo Strauss
Wanderley Caloni Jr
calculadora com notação polonesa. Muito bacana e fácil de entender.
Para C++ o Stroustrup faz o mesmo. Igualmente simples de entender (talvez mais).
[]s
Em 12/02/07, Vanessa Leite<vanessinhal...@gmail.com> escreveu:
--
Wanderley Caloni
http://www.caloni.com.br
Vanessa Leite
Para C d� uma olhada no livro do K&R, um dos cap�tulos implementa uma
calculadora com nota��o polonesa. Muito bacana e f�cil de entender.
Para C++ o Stroustrup faz o mesmo. Igualmente simples de entender (talvez mais).
[]s
Em 12/02/07, Vanessa Leite<vanessinhal...@gmail.com> escreveu:
> Voc�s alguma vez j� construiram algum compilador?? Estou com um trabalho
> desses pra fazer ( uma especie de compilador pra calculos..) . Alguem pode
> me ajudar??
> =D
>
> --
> >>Vanessa Leite
> ---
> "N�o se preocupe em entender. A vida ultrapassa todo entendimento."
> (Clarisse Lispector)
> ---
> Ci�ncia da Computa��o
> Universidade Federal do Maranh�o - UFMA
> Laborat�rio de Processamento e An�lise de Imagens - LabPAI
Alberto Fabiano
Thiago Adams
disponível para as pessoas do grupo comentarem.
Tenho certeza que iria servir como aprendizado para muita gente.
DQ
(como Lex e Yacc), é mais divertido e instrutivo fazer "na raça".
Onde eu vi uma introdução muito boa foi no clássico "Algorithms + Data
Structures = Programs" de Niklaus Wirth. O livro tem um exemplo
completo, um compilador de uma linguagem fictícia (PL/0), obviamente
escrito em Pascal (Wirth foi o inventor do Pascal). Infelizmente este
livro está esgotado, mas talvez você ache na biblioteca. Vale a pena.
No compilador que eu fiz eu me baseie em uma apostila de um professor
da USP (Valdemar Setzer - http://www.ime.usp.br/~vwsetzer/). A
apostila também tem exemplos em Pascal, mas não tive dificuldade em
converter para C. Esta apostila virou um livro (A Construção de um
Compilador) que também está esgotado. Obs.: Não se assuste pela
objeção dele ao uso de computadores por crianças!
Vou ver se acho a apostila em casa e coloco aqui um resumo das
técnicas utilizadas.
Thiago Adams
Era uma linguagem de script orientado a objetos. Fiz tudo a mão e não
me basei em nenhum livro.
A linguagem usava internamente um tipo de dado "variant" embora na
hora de declarar fosse declarado com o tipo. (eu pretendia futuramente
fazer internamente usar o tipo correto para otimizar, mas nunca fiz
isso)
Todo codigo virava dados (este variant) e comandos. Os comandos era
ponteiros para funcao direto. O runtime era extremamente simples, era
uma maquina de pilha que trabalhava so com o tipo variant e chamava o
ponteiro de funcao para executar o comando.
Para uma linguagem de script era bem rapido, 10x mais rapido que o
VBScript.
Thiago Silva
>
> Bem, eu já fiz um compilador. Embora existam ferramentas para isto
> (como Lex e Yacc), é mais divertido e instrutivo fazer "na raça".
Definitivamente mais instrutivo.
Eu utilizei o flex e o bison mas, posteriormente, mudei para o antlr.
Este ultimo nao produz um codigo tao rapido quanto os primeiros, mas
suporta varias linguagens alvo e eh uma verdadeira alegria brincar com
ele.
Este assunto (compiladores e linguagens), particularmente, desperta
meu interesse mais que qualquer outro mas, infelizmente, nao conheco
muita literatura atual a respeito. Se algum colega souber de artigos
ou livros, agradeco desde ja.
--
Thiago Silva
Blog: http://www.sourcecraft.info/blog
Jabber: tsi...@jabber.org
Thiago Adams
Exemplo de programa:
Class CA
public m_x As Integer
public Sub XX()
Console.WriteLn("teste");
End Sub
End Class
'
' Exemplo para testar operadores e expressoes
'
Class Application
public Sub Initialize()
Dim aa As New CA
Dim x As Integer
Dim count As Integer
aa.XX();
aa.m_x = 1 + 3 * 2;
Console.WriteLn(count);
Console.WriteLn(aa.m_x);
End Sub
End Class
(o public ali eu lembro que era enfeito pq nao considerava : )
o pseudo código gerado era o seguinte para este exemplo.
[0] 0 (int)
[1] CAsm::New
[2] Application.Initialize (9)
[3] CAsm::Call
[4] CAsm::Exit
' --- CA.XX -----------------------
[5] teste0033ACE8 (string)
[6] CAsm::WriteLn
'CA.XX.End
[7] 1 (int)
[8] CAsm::Return
' --- Application.Initialize -----------------------
[9] 1 (int)
[10] CAsm::New
[11] x0 (int)
[12] count1 (int)
[13] CA.aa (0)
[14] CA.XX (5)
[15] CAsm::Call
[16] CA.aa (0)
[17] CA.m_x0 (int)
[18] CAsm::PushMember
[19] 1 (int)
[20] 3 (int)
[21] 2 (int)
[22] CAsm::Multiply
[23] CAsm::Addition
[24] CAsm::Set
[25] count (2)
[26] CAsm::WriteLn
[27] CA.aa (0)
[28] CA.m_x0 (int)
[29] CAsm::PushMember
[30] CAsm::WriteLn
'Application.Initialize.End
[31] 4 (int)
[32] CAsm::Return
Thiago Adams
http://ccppbrasil.googlegroups.com/web/tscript.PNG
DQ
estou iniciando uma série de posts no meu blog (http://
dqsoft.blogspot.com/) sobre a construção de compiladores.
Vanessa Leite
Consegui fazer meu "compilador-calculadora", mas... eu o fiz em java..
heheh
acabou que como era um trabalho em equipe (somos tres, assim como em maratonas :P), os outros membros preferiam usar java, e fica dificil sendo dois contra um, e como eu naum sabia como usar delimitadores em C/C++, nao podia nem apelar.. tsc tsc...
mas valeu assim mesmo galera..
>>ssinhaleite( http://ssinhaleite.multiply.com )
Ok, achei a apostila... Não sei se adianta ainda para a Vanessa, mas
estou iniciando uma série de posts no meu blog (http://
dqsoft.blogspot.com/) sobre a construção de compiladores.
--
>>Vanessa Leite
---
"Não se preocupe em entender. A vida ultrapassa todo entendimento." (Clarisse Lispector)
---
thoth39
wrote:
> .. e como eu naum sabia como usar delimitadores em C/C++, nao
> podia nem apelar.. tsc tsc...
O que são "delimitadores"?
--
Pedro Lamarão
Vanessa Leite
devo ler uma string (que no meu caso seria uma continha) algo como:
2+3*4=
eu tenho que retornar o resultado disso. Em java há o chamado stringTokenizer, que retorna os tokens, que por default sao separados por espaços. Mas eu posso criar meus proprios "delimitadores", ou seja, é onde eu digo que termina um token e começa outro, que no meu caso ( da continha) eu incluí o +, o * e o =.
Entendeu??
Espero ter sido clara..
>>ssinhaleite
Thiago Adams
uma solucao pronta no C++.
Para o caso mais geral tem que fazer um parser.
------------------x-------------------------
Falando em parser..
Alguém aqui tem interesse em fazer uma classe de parser para uso
geral?? Como eu tinha dito em outro email, eu sempre preciso disso e
pego de um projeto antigo.. so que atualmente eu faria diferente. :)
Requisitos:
- ler arquivos em UTF8
- usar wchar_t como caractere de saida
- poder definir o que 'e um comentario.. por exemplo comentario de
linha estilo // ou estilo ' etc.. e comentarios do estilo /* */
mas isso tudo tem q ser configuravel.
- definir como 'e uma string
- definida para ler arquivos somente. (?)
Esta classe tem que poder ser usada para fazer um parser XML, um
parser de um fonte etc.. somente adaptando e customizando futuramente.
Ele tem a intencao de ser a classe basica.
enum Tokens
{
TokenEof,
TokenInteger,
TokenDouble,
TokenString,
TokenSymbol,
};
class Parser
{
Parser(const char * fileName)
Reset();//?
wchar_t NextToken();
wchar_t GetToken() const;
bool CheckToken(wchar_t token) const;
bool CheckTokenSymbol(const wchar_t & tokenSymbol) const;
bool GetTokenInt(int &) const;
bool GetTokenDouble(double &) const;
bool GetTokenString(wchar_t *pszOut, size_t & size) const;
bool GetTokenAsString(wchar_t *pszOut, size_t & size) const;
int GetCurrentLine() const;
int GetCurrentCharPos() const;
int GetCurrentCharColumn() const;
};
As regras podem ser definidas em uma classe separada ... podem ser do
estilo template tb (polices)
Com uma classe destas...se faz quase tudo :)
(Adaptando mais tarde.., por exemplo numa segunda camada eu colocaria
excecoes etc...)
Cesar Gimenes
> Falando em parser..
> Alguém aqui tem interesse em fazer uma classe de parser para uso
> geral?? Como eu tinha dito em outro email, eu sempre preciso disso e
> pego de um projeto antigo.. so que atualmente eu faria diferente. :)
Eu estou fazendo a minha, faz parte do meu estudo sobre
compiladores/Interpretadores e linguagens de programação/otimização de
código/parser para RPC. quanta coisa em um mesmo programa! :D
> - ler arquivos em UTF8
Já esta ok, eu uso UTF8 no dia a dia.
> - usar wchar_t como caractere de saida
Me recuso! :D
> - poder definir o que 'e um comentario.. por exemplo comentario de
> linha estilo // ou estilo ' etc.. e comentarios do estilo /* */
Bom o que eu fiz foi uma classe "toke" você define uma lista de tokes e passa
essa lista para a classe "tokenizer" que por sua vez interpreta cada toke,
dessa forma da para ter qualquer quantidade de tokes e eles podem ser
qualquer coisa.
> mas isso tudo tem q ser configuravel.
Já esta ok, mas em tempo de compilação por enquanto.
> - definir como 'e uma string
Essa eu não entendi... eu estou usando o conceito do C/C++ para strings, acho
simples e bom.
> - definida para ler arquivos somente. (?)
Eu estou escrevendo para ler uma stream, dessa forma fica mais flexível, eu
costumo testar lendo direto da stdin:
cat tokenizer.cpp | tokenizer
Notou que eu uso o próprio fonte do tokenizer para testar o código? :D é
divertido fazer isso.
> Esta classe tem que poder ser usada para fazer um parser XML, um
> parser de um fonte etc.. somente adaptando e customizando futuramente.
A idéia é essa, se bem que meu foco é fontes C++, o XML é fácil de interpretar
comparado com um fonte em C++ :D
> Com uma classe destas...se faz quase tudo :)
:D
Tenho que polir meu código acertar mais algumas coisas, dai vou colocar no meu
site sob LGPL.
--
Cesar Gimenes http://www.crg.eti.br
Linux user #76132
Thiago Adams
On 1 Mar, 10:35, Cesar Gimenes <cesar.gime...@gmail.com> wrote:
> Em Quinta 01 Março 2007 07:06, Thiago Adams escreveu:
>
> > Falando em parser..
> > Alguém aqui tem interesse em fazer uma classe de parser para uso
> > geral?? Como eu tinha dito em outro email, eu sempre preciso disso e
> > pego de um projeto antigo.. so que atualmente eu faria diferente. :)
>
> Eu estou fazendo a minha, faz parte do meu estudo sobre
> compiladores/Interpretadores e linguagens de programação/otimização de
> código/parser para RPC. quanta coisa em um mesmo programa! :D
Legal, você tem interesse de fazer uma versao 2 que atenda os gostos/
necessidades comuns?
> > - ler arquivos em UTF8
>
> Já esta ok, eu uso UTF8 no dia a dia.
O que você usou? não depende de SO né?
> > - usar wchar_t como caractere de saida
>
> Me recuso! :D
Porque? Não entendi. Não vai poder ter um token em unicode dai...
> > - poder definir o que 'e um comentario.. por exemplo comentario de
> > linha estilo // ou estilo ' etc.. e comentarios do estilo /* */
>
> Bom o que eu fiz foi uma classe "toke" você define uma lista de tokes e passa
> essa lista para a classe "tokenizer" que por sua vez interpreta cada toke,
> dessa forma da para ter qualquer quantidade de tokes e eles podem ser
> qualquer coisa.
>
> > mas isso tudo tem q ser configuravel.
>
> Já esta ok, mas em tempo de compilação por enquanto.
>
> > - definir como 'e uma string
>
> Essa eu não entendi... eu estou usando o conceito do C/C++ para strings, acho
> simples e bom.
No c++ é uma coisa.. "string\n" no VB é outra.. 'string' no XML é
outra.. etc.. eu preciso poder configurar o que significa uma string
para usar o parser em outras coisas futuramente.
> > - definida para ler arquivos somente. (?)
>
> Eu estou escrevendo para ler uma stream, dessa forma fica mais flexível, eu
> costumo testar lendo direto da stdin:
É uma otima ideia fazer com streams genericos..no entando se pensar em
arquivos é interessante ler uma parte e colocar na memoria, para fica
mais rapido. Se a stream que vc esta usando ja eh em memoria nao faria
sentido usar isso. Entao se quiser ter as duas opcoes tb teria q ser
algo configuravel.
> Tenho que polir meu código acertar mais algumas coisas, dai vou colocar no meu
> site sob LGPL.
Acho que primeiro passo é definir a interface desejada.
por isso coloquei aquela sugestao.
Rodrigo Strauss
Já viram os fontes do parser do OmniObjects?
http://omniobjects.svn.sourceforge.net/viewvc/omniobjects/trunk/src/OmniIdl/MidlParser.cpp?view=markup
http://omniobjects.svn.sourceforge.net/viewvc/omniobjects/trunk/src/OmniIdl/MidlParser.h?view=markup
Rodrigo Strauss
Thiago Adams
On 1 Mar, 12:04, "Rodrigo Strauss" <rodr...@1bit.com.br> wrote:
> Qual o problema com o boost:tokenizer?
>
> Já viram os fontes do parser do OmniObjects?http://omniobjects.svn.sourceforge.net/viewvc/omniobjects/trunk/src/O...http://omniobjects.svn.sourceforge.net/viewvc/omniobjects/trunk/src/O...
Eu vi o parser do OmniObjects, mas ele esta mais focado para o idl.
Teria que ser um que pudesse ser usado como classe base ( out interno
tanto faz) para o este parser de idl do OmniObjects.
Outra coisa do parser do OmniObjects é que nao le UTF8. Para usar como
classe base para um parser de XML tem
que ter suporte a utf8.
Nao sei se o do boost tem? vou olhar o boost:tokenizer depois.
Cesar Gimenes
> Legal, você tem interesse de fazer uma versao 2 que atenda os gostos/
> necessidades comuns?
Um dos motivos de eu estar fazendo meu tokenizer é fazer do meu gosto, então
talvez não seja do "gosto comum", já quanto as funcionalidades eu vou
implementando conforme elas são necessárias para mim, de qualquer forma o
código é aberto se alguma coisa não estiver lá é só pegar o código
implementar. Claro que eu estou aberto a criticas e sugestões.
> > Já esta ok, eu uso UTF8 no dia a dia.
> O que você usou? não depende de SO né?
Não depende de SO mas tem algumas restrições, você pode usar caracteres UTF8
dentro de strings (no momento cercadas aspas), você pode predefinir um toke
UTF8 na lista de tokes, mas você não pode criar variáveis, labels ou nomes de
funções com caracteres UTF8.
> > > - usar wchar_t como caractere de saida
> > Me recuso! :D
> Porque? Não entendi. Não vai poder ter um token em unicode dai...
É complicado explicar o motivo de eu não usar wchar_t, acho que podemos dizer
que eu simplesmente não gosto disso. Quanto mais velho vou ficando mais chato
com mais manias essa é uma delas. No próximo encontro do grupo de C/C++
podemos bater papo sobre isso. :D
Como eu falei pode ter tokes UTF8 se ele for predefinido ou se estiver em uma
string para as minhas aplicações esta muito bom.
> > > - definir como 'e uma string
> > Essa eu não entendi... eu estou usando o conceito do C/C++ para strings,
> > acho simples e bom.
> No c++ é uma coisa.. "string\n" no VB é outra.. 'string' no XML é
> outra.. etc.. eu preciso poder configurar o que significa uma string
> para usar o parser em outras coisas futuramente.
Saquei! Por enquanto funciona apenas no estilo C/C++, estou trabalhando a
idéia para poder ser qualquer caractere.
> É uma otima ideia fazer com streams genericos..no entando se pensar em
> arquivos é interessante ler uma parte e colocar na memoria, para fica
> mais rapido. Se a stream que vc esta usando ja eh em memoria nao faria
> sentido usar isso. Entao se quiser ter as duas opcoes tb teria q ser
> algo configuravel.
Bom, eu preferi separar as coisas, não vou inserir na minha classe recursos
para leitura de arquivos isso é responsabilidade de quem chama o tokenizer,
mas da para fazer como você quer, um dos membros da classe tokenizer é o
addLine que recebe linhas, transforma em tokes e insere esses toques na
pilha:
bool tokenizer::addLine(std::string line);
> Acho que primeiro passo é definir a interface desejada.
> por isso coloquei aquela sugestao.
Como é um código escrito para estudo eu preferi não me preocupar com a
interface agora então minha definisão não podia ser mais simples, uma classe
com um membro que recebe uma stream e outro membro que retorna um vetor com
os tokes.
Ainda tem muita coisa para fazer, mas já esta tomando forma.
Se quiser dar uma olhada enquanto eu não disponibilizo oficialmente o código é
só pedir e eu mando em PVT. (lembre que ainda é um rascunho)
Cesar Gimenes
> Qual o problema com o boost:tokenizer?
Problema nenhum! Se o objetivo fosse *usar* um tokenizer e não *fazer* um
tokenizer. :D Se você precisa de um tokenizer bom e bem testado para usar em
um projeto ou qualquer séria deve usar o boost:tokenizer.
> Já viram os fontes do parser do OmniObjects?
Ainda não Rodrigo mas vou dar uma olhada agora que você mencionou, eu só havia
dado uma "passada de olhos" na OmniObjects quando estava procurando um
sistema de RPC mas como não tem port para Linux eu acabei resolvendo o
problema usando a velha dobradinha sockets e sscanf (o parser
universal! :-D )
Abraços!
Thiago Adams
O boost::tokenizer não e' uma parte, mas nao substitui uma classe de
parser.
Nao tem o conceito de comentario, de strings, de pegar um numero de
ponto fluturante ou um numero inteiro.
e nao tenho certeza, mas acho que foi projetado para trabalhar com
strings e nao com arquivos.
A classe de parser tem q ter a seguinte responsabilidade na minha
opniao:
- saber extrair simbolos, numeros inteiros, numeros de ponto flutuante
- saber extrair strings (basicamente nao pular espacos e ter uma regra
de comeco e fim de string. entender /n etc...
- saber pular comentarios do estilo linha e outro estilo de inicio
fim. (isso tem q ser opcional, configurado)
- trabalhar com arquivos de forma eficiente, e ler utf8
- retornar a posicao do cursor. (linha coluna)
- saber comparar simbolos e tokens
porque estes conceitos deveriam estar dentro da classe de parser??
- porque 'e muito mais eficiente fazer a conversao de uma string para
numero por exemplo dentro da classe de parser,
do que retornar uma string e depois converter.
A mesma questao de eficiencia vale para a comparacao de tokens e
simbolos.
Wanderley Caloni Jr
propósito? Quer dizer, você define as regras de sintaxe e cria as
funções para cada elemento capturado.
[]s
Em 01/03/07, Thiago Adams<thiago...@gmail.com> escreveu:
Cesar Gimenes
> Desculpem-me a "ingnor�ncia", mas o lex n�o serviria para esse
> prop�sito? Quer dizer, voc� define as regras de sintaxe e cria as
> fun��es para cada elemento capturado.
É para isso sim, mas ai você perde a oportunidade de aprender fazendo o seu
próprio tokenizer. Claro, se você não esta estudando e sim fazendo algo que
tem prazo para ser entregue o lex seria a melhor opção.
thoth39
wrote:
> Desculpem-me a "ingnor?ncia", mas o lex n?o serviria para esse
> prop?sito? Quer dizer, voc? define as regras de sintaxe e cria as
> fun??es para cada elemento capturado.
Realmente.
Há também mais uma alternativa em C++ que ainda não foi mencionada, a
Spirit, parte da Boost.
Eu achei um parto aprender a usar Spirit mas me divirto muito com ela
atualmente.
Um pré-processador C++ chamado Wave foi escrito com Spirit e hoje é
parte da Boost também.
--
Pedro Lamarão
Rodrigo Strauss
OmniObjects faz. O código é BSD, talvez seja um ponto para começar...
On 3/1/07, Thiago Adams <thiago...@gmail.com> wrote:
>
>
Cesar Gimenes
> Sim, mas muito do que você falou (strings, comentário), o parser do
> OmniObjects faz. O código é BSD, talvez seja um ponto para começar...
Talvez esse artigo seja um exemplo mais simples para quem quer experimentar o
boost::tokenizer embora o foco seja outro:
http://www.linhadecodigo.com.br/artigos.asp?id_ac=1147
Strauss, que tal você dar alguns exemplos legais de uso de Boost para nós?
Thiago Adams
On 2 Mar, 14:16, "Rodrigo Strauss" <rodr...@1bit.com.br> wrote:
> Sim, mas muito do que você falou (strings, comentário), o parser do
> OmniObjects faz. O código é BSD, talvez seja um ponto para começar...
Como eu disse uma vez, eu tenho uma classe de parser que eu sempre uso
em todos os meus projetos :)
So que eu dei uma olhada nela. e gostaria que ela fosse mais generica.
Na pratica eu sempre mudo o que eu preciso e fica varias versoes do
parser perdido no meu computador.
Entao desta vez eu queria fazer ela generica e testar bastante e
deixar "na gaveta" para quando eu precisar de novo eu ter um codigo
testado e com a versao 2007.
Para isso seria bom se mais pessoas tivessem interesse porque ajuda a
testar e usar em outros scenarios.
Alberto Fabiano
Dando o meu cents de contribuição (ou não) ter um ponto de partida é sempre mais produtivo e não vejo problema algum deste ser o OmniObjects, muito pelo contrário, visto que ele é bem funcional e tem uma licença apropriada, sem contar que o código é de qualidade.
Att.
[]s++
GPG KEY: F61D8A32
/*-::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::-"
"Quem pouco ou nada sabe, pensa mal e costuma agir pior ainda"
Leon Trotsky
-::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::--::-::-*/