pico

Projeto de Compiladores (etapa 7): PicoNicolas Maillard Claudio Schepke Stfano Mr

2 Este documento detalha a especicao da stima etapa do pequeno compilador Pico.

Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

Chapter 1

Organizao do projetoA primeira etapa consiste na programao de duas estruturas de dados bsicas. As etapas 2, 3 e 4 consistem na implementao dos analisadores lexicais e sintticos. As etapas 5, 6 e 7 trataro da fase de gerao de cdigo. 1. Estruturas de dados bsicas (pilha e tabela de Hash). 1 ponto. 2. Analisador lexical (com auxlio do ex). 1 ponto. 3. Analisador sinttico (LL(1). 1 ponto. 4. Anlise sinttica LR (Yacc). 1,5 ponto. 5. Anlise semntica: declarao de variveis, expresses. 1,5 ponto. 6. Anlise semntica: controle de uxo. 2 pontos. 7. Gerao de cdigo Assembly. 2 pontos. O trabalho de programao da etapa 7 deve ser entregue at o dia 01 de Dezembro, 23h00 (segunda-feira). Ser apresentado ao tutor no encontro do dia 02 de Dezembro, 10h30 ou no dia 04 de Dezembro. Ele receber uma nota valendo 2 pontos do total da nota do projeto. A nota nal do projeto valer 50% da nota nal da disciplina. A programao deve ser feita no Linux, em C ANSI. Ser usados, a partir da segunda etapa, as ferramentas Lex (ex) e Yacc (Bison). O ltimo captulo deste documento d as primeiras instrues para usar o comando Make, no Linux, para compilar um programa. Tambm explica como se usa o Doxygen para documentar cdigo. absolutamente fundamental que a especicao seja respeitada totalmente: os nomes dos procedimentos devem ser iguais ao especicado; os parmetros devem ser conformes ao que se espera; etc. Os cdigos devem ser comentados, de acordo com o padro Doxygen. Encontra-se, nos programas entregues junto a essa especicao, exemplos de uso de Doxygen. O projeto todo deve ser desenvolvido por grupos de 3 alunos. Faz parte do trabalho se distribuir a carga de trabalho de forma a fornecer uma implementao de boa qualidade: por exemplo, pode se programar a quatro mos (dois alunos programam juntos), com o terceiro colega se encarregando de testes e da documentao. Pode-se tambm optar por uma distribuio dos procedimentos a ser programados. Aconselha-se que programao e teste no sejam feitos pela mesma pessoa. interditado que um aluno nunca programe nada. totalmente possvel que os integrantes de um grupo tenham notas diferenciadas em funo de seu envolvimento no trabalho.

4

Organizao do projeto


Chapter 2

Especicao da Etapa 1O cdigo a ser implementado se encontra especicado em Pico/src/Etapa1. Pede-se implementar uma estrutura de pilha (ver o arquivo stack.h) e uma estrutura de tabela de smbolos (ver symbol_table.h). O diretrio doc/html/ contm essas especicaes, legveis on-line. A pilha dever suportar operaes de push e de pop de elementos genricos void *, ou seja referncias sobre qualquer tipo se encontraro na pilha. Outras operaes clssicas so exigidas. Uma tabela de smbolos uma estrutura de dados interna a um compilador, que ir ser usada intensivamente nas outras etapas. Por ora, basta saber que se implementa atravs de uma tabela de Hash. Uma entrada na tabela de smbolos ser caracterizada por vrios campos (cujo detalhe est fora do escopo desta primeira etapa, ver o tipo abstrato entry_t em symbol_table.h), incluindo um campo nome de tipo char* (ou string, em C). A partir deste nome, deve-se calcular um hash para associ-lo a um nmero inteiro, que ir servir para acessar um vetor. Se houver colises na funo de Hash, cuidados devem ser tomados para desempatar. As funes exigidas so de insero de uma entrada, de consulta, alm de funcionalidades de vericao e de impresso do contedo de uma tabela de smbolos. Salienta-se que se espera implementaes corretas: sem perda de memria (lembrar que C no usa coletor de lixo: caso se use um malloc, deve-se usar um free em algum outro lugar), sem acesso fora da rea de memria alocada, sem efeito colateral no controlado, etc. . . A seguir, detalha-se o perl de cada um dos procedimentos exigidos.

2.1

Referncia do Arquivo stack.h

Funes void init_stack (stack s)Inicializar a pilha. Uso tipico: init_stack(&minha_pilha);.

void free_stack (stack s)Liberar a memoria usada pela pilha. Uso tipico: free_stack(&minha_pilha);.

int empty (stack s)Testar se a pilha esta vazia.

int push (stack s, void item)Empilhar um elemento na pilha. (O tipo do elemento void .).

6

Especicao da Etapa 1

void pop (stack s)Desempilhar o elemento no topo da pilha.

void top (stack s)Consultar o elemento no topo da pilha.

Variveis typedef stackAqui, voce deve completar a parte entre o typedef e o stack para inserir sua implementacao da estrutura de dados abstrata de pilha.

2.1.1Verso: 1.1

Descrio Detalhada

2.1.22.1.2.1

Funesint empty (stack s)

Testar se a pilha esta vazia. Testa se a pilha esta vazia. Parmetros: s uma pilha Retorna: 0 se a pilha nao esta vazia, um valor diferente de zero se a pilha esta vazia. 2.1.2.2 void free_stack (stack s)

Liberar a memoria usada pela pilha. Uso tipico: free_stack(&minha_pilha);. free_stack eh o destrutor da estrutura de dados de pilha. Deve liberar qualquer espaco na memoria que tenha sido alocado para a implementacao interna da pilha passada em argumento. Um acesso a uma pilha, depois da chamada a free_stack levara a um erro na execucao. Parmetros: s um ponteiro sobre uma pilha (stack). Retorna: nada (void).Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

2.1 Referncia do Arquivo stack.h 2.1.2.3 void init_stack (stack s)

7

Inicializar a pilha. Uso tipico: init_stack(&minha_pilha);. Inicializa a pilha, allocando qualquer espao na memoria que seja necessario. Nao se deve efetuar nenhuma hipotese restritiva quanto ao numero total de entradas que podera conter a pilha num dado instante. init_stack devera ser chamado pelo usuario deste estrutura de dados, antes de poder usa-la. Qualquer referencia anterior que ele possa fazer a uma pilha tera comportamento nao-especicado. Parmetros: s um ponteiro sobre uma pilha (stack). Retorna: nada (void). 2.1.2.4 void pop (stack s)

Desempilhar o elemento no topo da pilha. Desempilha o elemento no topo da pilha, e retorna-o. Remove este elemento da pilha. Parmetros: s,um ponteiro sobre a pilha de onde se deve tirar um elemento. Retorna: o elemento que foi desempilhado, ou NULL se nao tinha como desempilhar alguma coisa. 2.1.2.5 int push (stack s, void item)

Empilhar um elemento na pilha. (O tipo do elemento void .). Empilha um elemento na pilha. Parmetros: s,uma referencia sobre a pilha onde se deve inserir o elemento. item,uma referencia sobre o elemento a ser inserido. Retorna: 0 se a insercao deu certo. 2.1.2.6 void top (stack s)

Consultar o elemento no topo da pilha. Retorna um ponteiro sobre o elemento no topo da pilha. Nao remove este elemento da pilha. Parmetros: s,a pilha de que se deve consultar o topo. Retorna: o elemento, ou NULL se nao tinha nada no topo.


8


2.2

Referncia do Arquivo symbol_table.h

Estruturas de Dados struct entry_t

Funes int init_table (symbol_t table)Inicializar a tabela de Hash.

void free_table (symbol_t table)Destruir a tabela de Hash.

entry_t lookup (symbol_t table, char name)Retornar um ponteiro sobre a entrada associada a name.

int insert (symbol_t table, entry_t entry)Inserir uma entrada em uma tabela.

int print_table (symbol_t table)Imprimir o conteudo de uma tabela.

int print_le_table (FILE out, symbol_t table)Imprimir o conteudo de uma tabela em um arquivo.

Variveis typedef symbol_tEncapsulacao de um tipo abstrato que se chamara symbol_t.

2.2.1Verso: 1.1

Descrio Detalhada

2.2.22.2.2.1

Funesvoid free_table (symbol_t table)

Destruir a tabela de Hash. free_table eh o destrutor da estrutura de dados. Deve ser chamado pelo usuario no m de seu uso de uma tabela de simbolos. Parmetros: table,uma referencia sobre uma tabela de simbolos.Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

2.2 Referncia do Arquivo symbol_table.h 2.2.2.2 int init_table (symbol_t table)

9

Inicializar a tabela de Hash. Parmetros: table,uma referencia sobre uma tabela de simbolos. Retorna: o valor 0 se deu certo. 2.2.2.3 int insert (symbol_t table, entry_t entry)

Inserir uma entrada em uma tabela. Parmetros: table,uma tabela de simbolos. entry,uma entrada. Retorna: um numero negativo se nao se conseguiu efetuar a insercao, zero se deu certo. 2.2.2.4 entry_t lookup (symbol_t table, char name)

Retornar um ponteiro sobre a entrada associada a name. Essa funcao deve consultar a tabela de simbolos para vericar se se encontra nela uma entrada associada a um char (string) fornecido em entrada. Para a implementacao, sera necessario usar uma funcao que mapeia um char a um numero inteiro. Aconselha-se, por exemplo, consultar o livro do dragao (Aho/Sethi/Ulman), Fig. 7.35 e a funcao HPJW. Parmetros: table,uma tabela de simbolos. name,um char (string). Retorna: um ponteiro sobre a entrada associada a name, ou NULL se name nao se encontrou na tabela. 2.2.2.5 int print_le_table (FILE out, symbol_t table)

Imprimir o conteudo de uma tabela em um arquivo. A formatacao exata e deixada a carga do programador. Deve-se listar todas as entradas contidas na tabela atraves de seu nome (char). Deve retornar o numero de entradas na tabela. A saida deve ser dirigida para um arquivo, cujo descritor e passado em parametro. Parmetros: out,um descrito de arquivo (FILE). table,uma tabela de simbolos. Retorna: o numero de entradas na tabela.Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

10 2.2.2.6 int print_table (symbol_t table)


Imprimir o conteudo de uma tabela. A formatacao exata e deixada a carga do programador. Deve-se listar todas as entradas contidas na tabela atraves de seu nome (char). Deve retornar o numero de entradas na tabela. Parmetros: table,uma tabela de simbolos. Retorna: o numero de entradas na tabela.

2.2.32.2.3.1

Variveistypedef symbol_t

Encapsulacao de um tipo abstrato que se chamara symbol_t. Voce deve inserir, entre o typedef e o symbol_t, a estrutura de dados abstrata que voce ira implementar.


Chapter 3

Especicao da Etapa 2Essa segunda etapa do projeto consiste na implementao do analizador lexical (scanner), que dever retornar os tokens reconhecidos num arquivo de entrada.

3.1

Explicaes

A etapa consiste na denio, com o Flex, dos tokens que sero reconhecidos pelo compilador Pico. Cada token ser implementado, em C, por um nmero constante inteiro atravs de diretivas #define. Por exemplo, #define IDF 100 pode servir para denir o token IDF, que ser encodicado no analizador lexical (e no futuro analizador sinttico) atravs da constante 101. A lista inteira dos tokens que devero ser denidos, junto com a especicao (em portugus) dos lexemas que devero ser reconhecidos como representando esses tokens, se encontra a seguir na prxima seo. Para cada token, voc dever: 1. Deni-lo atravs de um #define. Essa lista de define dever ser programada em um arquivo separado, limitado a este contedo, chamado de tokens.h. O seu analizador lexical dever incluir tokens.h atravs de um: #include tokens.h Os arquivos entregues em Pico/src/Etapa2 incluem um esqueleto para tokens.h e a incluso do mesmo no arquivo de entrada usado com o Flex (chamado scanner.l). 2. Denir uma expresso regular, de acordo com a sintaxe do Flex, que especique os lexemas representando esses tokens. Essas expresses regulares devero se encontrar no arquivo scanner.l, usado como entrada do Flex. Para determinar essas expresses regulares, pode-se consultar o documento encontrado no Moodle, encontro 4, pgina 7. O arquivo scanner.l inicial, encontrado em Pico/src/Etapa2, contm um esqueleto pronto a compilar. 3. Associar a essa expresso regular uma ao em C, que ser acionada quando o analizador lexical ir reconhecer este token. A ao, em geral, ser trivial e consistir apenas no retorno (return) do token identicado. Eventualmente, ser necessrio executar uma ao mais complexa, de acordo com a especicao. Caber, ento, programar (em C) o cdigo necessrio ou usar estruturas de dados j prontas. Exemplo: seja a especicao (irrealista) seguinte: o token INT deve ser retornado ao reconhecer os lexemas integer ou int. Deve-se programar, por exemplo:

12 #define INT 3333 %% (integer|int) { return( INT ); }


A linha do #define ir no arquivo tokens.h. A linha com a expresso regular, simples neste caso, e a ao em C (return()), dever ser inserida no arquivo scanner.l. Seu analizador lexical, chamado pico, dever ler sua entrada a partir de um arquivo especicado em argumento na linha de comando. Ele deve usar uma tabela de smbolos para armazenar os identicadores (IDF) reconhecidos. O arquivo scanner.l e o Makele fornecidos em Pico/src/Etapa2/ so pontos de partida para escrever o analizador lexical e compil-lo. Basicamente, basta complementar scanner.l e tokens.h. make ou make pico deve invocar o ex, gerar o arquivo C que implementa o analizador, e compil-lo para obter o executvel pico. Observa-se que o scanner.l j vem com um main pronto, o qual se encarrega de ler o arquivo em entrada e de chamar o scanner nele.

3.2

Especicao dos tokens

Os tokens so denidos em duas partes: os chamados tokens simples representam apenas um lexema (string) nico, o que signica que a expresso regular os denindo trivial (mas precisa ser implementada). Os outros tokens necessitam de expresses regulares menos imediatas, porm todas discutidas nas aulas.

3.2.1

Tokens simples

Cada um dos lexemas a seguir se confunde com o token a ser retornado, ou seja o token representa apenas um nica lexema. A nica ao a ser efetuada consiste no retorno do token. Tm casos especiais ainda mais simples, onde o lexema se limita a um caractere nico (exemplos: *, ou ;). Neste caso, o Flex possibilita retornar como constante inteira o prprio caractere (sem necessitar um #define, pois ser usado um cast do char de C para um int). Por exemplo, se o lexema * deve ser reconhecido e associado a um token, ao invs de cham-lo, por exemplo, de ASTERISCO e de programar seu retorno assim:

#define ASTERISCO 3333 %% * { return( ASTERISCO ); }

basta escrever:

%% *

{ return( * ); }


3.2 Especicao dos tokens

13

A tabela a seguir explicita todos os tokens a serem retornados. Para ganhar espao, alguns casos juntam mais de um token numa linha s, separados por vrgulas. Espera-se bom senso para entender que, por exemplo,

Lexema (, )

Token a ser retornado (, ) (respectivamente)

signica que o lexema ( deve ser associado ao token ( (exemplo do caso onde o lexema se limita a um nico caractere) e que o lexema ) deve ser associado ao token ), e NO que o lexema (, ) (string composto por abre-parntese vrgula fecha-parntese) deve ser associado aos dois tokens ) e ) (o que no faria sentido).

Lexemas int double float char *,+,-,/ , ; " (, ) [, ], {, } , = = == != &&, ||, ! if then else while

Tokens a ser retornados INT DOUBLE FLOAT CHAR *, +, -, / (respectivamente) , ; QUOTE DQUOTE (, ) (respectivamente) [, ], {, } (respectivamente) e = respectivamente LE GE EQ NE AND, OR, NOT (respectivamente) IF THEN ELSE WHILE

3.2.1.1

Outros tokens

Em toda essa seo, um dgito um dos caracteres 0, 1, 2, . . . , 9.Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

14 Descrio Qualquer combinao de qualquer nmero de brancos: espao branco, tabulao, m de linha. Pelo menos uma letra (mauscula ou minscula), seguida por qualquer nmero de letras (maisculas ou minsculas), dgitos ou _. Qualquer conjunto de dgitos token a ser retornado no ser retornado token

Especicao da Etapa 2 Ao imprimir na sada (tela): BRANCO.

IDF

o lexema deve ser inserido numa tabela de smbolos. o lexema, convertido em int, deve ser copiado numa varivel C global chamada VAL_INT, de tipo int. o lexema, convertido em double, deve ser copiado numa varivel C global chamada VAL_DOUBLE, de tipo double.

INT_LIT

Um nmero com vrgula utuante (ver abaixo).

F_LIT

No caso do F_LIT, a descrio a seguinte: qualquer conjunto de dgitos (eventualmente vazio), seguido de um ponto (.), seguido de pelo menos um dgito. Isso tudo pode ser, opcionalmente, seguido de: 1. e ou E, obrigatoriamente seguido de 2. um sinal + ou - (obrigatrio), obrigatoriamente seguido de 3. pelo menos um dgito. Exemplos de lexemas reconhecidos: 3.14, 3.14e+0, .0, .0E+0. Exemplos de lexemas no reconhecidos: 0., 1e10, e+10, 10.1E, .0E0.

3.3

Tratamento de erros lexicais

Em alguns poucos casos, a entrada pode conter caracteres (ou seqncias de caracteres) no reconhecidos por nenhuma expresso regular. Observa-se que algumas seqncias que parecem, objetivamente, erradas ao programador no podem ser capturadas pelo analizador lexical. Considere por exemplo a entrada: 10E. Apesar de este lexema no condizer com nada do que se espera, o scanner ir retornar um INT_LIT (lexema 10) e logo depois um IDF (lexema E). Na verdade, essa entrada lexicamente correta, e o erro que o ser humano detecta sinttico: caber apenas gramtica do analizador sinttico no autorizar uma sucesso de dois tokens INT_LIT e IDF. Isso dito, existem casos de erros lexicais. Por exemplo, se um caractere ? aparecer na entrada, nenhuma das expresses regulares acima denidas dever aceit-lo. Isso acontece tambm com outros casos. Para pegar tais casos, a soluo no Lex incluir uma ltima regra (em ltimo lugar para que seja aplicada unicamente em ltima instncia, ou seja se nada fechou antes), do tipo: . { printf(Erro lexical - caractere nao reconhecido: %c.\n, yytext[0]); exit(-1); } A expresso regular . no incio da linha signica qualquer caractere (nico). Ao reconhecer qualquer caractere, ento, o analizador lexical gerado pelo Flex ir imprimir na tela uma mensagem relatando o caractere encontrado e no reconhecido, e depois interromper a execuo do programa (exit) com oGerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

3.4 Observaes nais

15

cdigo de retorno negativo, associado a um erro. Observa-se que se usa, no printf, a varivel interna ao Lex chamada yytext. Essa varivel, que iremos usar mais adiante, um string (char* em C) que contm sistematicamente o lexema que est sendo comparado com a E. R. Como, nessa rgra, se usa a E. R. . que autoriza apenas um caractere, yytext aqui um string de tamanho 1, e portanto yytext[0] o nico caractere compondo o lexema, que no caso o caractere que no foi reconhecido. (Para amadores de ponteiros em C, podia se escrever tambm *yytext em lugar de yytext[0].) O uso de . nessa regra deixa claro que se deve aplic-la apenas como ltimo recurso: uma regra pega tudo.

3.4

Observaes nais

Vai ser necessrio usar a tabela de smbolos da Etapa1. Existe vrias opes para incluir o cdigo C (.c e/ou .h) no cdigo do analizador lexical, uma delas sendo usar a mesma tcnica usada para incluir tokens.h. Deve-se obrigatoriamente incluir um .h que se encontra ou no diretrio corrente (no caso: Pico/src/Etapa2); ou (melhor) em Pico/include, onde o make install da etapa 1 ter copiado seus .h anteriores. Da mesma forma, deve-se linkar o cdigo objeto ou com arquivos .o do diretrio corrente, ou com os .o de Pico/objects (essa segunda opo sendo melhor). Cabe a vocs organizar seu cdigo e seus Makeles para isso. Os exemplos providos j servem para ilustrar como faz-lo. Essa etapa 2 simples - basicamente, consiste em preencher arquivos existentes com as Expresses Regulares vistas em aula, na sintaxe do Flex. Com os arquivos providos, tudo deve se compilar automaticamente. Posto isso, muito importante dedicar tempo para testar seu analizador lexical e vericar o maior nmero possvel de entradas para vericar que ele retorne os tokens que se espera. Os testes dessa etapa iro principalmente testar essas expresses regulares.


16



Chapter 4

Especicao da Etapa 34.1 Trabalho pedido

Nessa etapa, voc deve programar um analisador sinttico (acoplado com seu analisador lexical da Etapa 2) para uma gramtica simples, a m de reconhecer expresses aritmticas. A gramtica a reconhecer a seguinte: E E + E E E - E E E * E E E / E E ( E ) E IDF E INT_LIT E F_LIT O smbolo Start E. Os terminais so (parte de) os tokens denidos na Etapa 2. Sentenas como: IDF + ( IDF * ( F_LIT - IDF ) ) so reconhecidas por essa gramtica. Posto que o analisador lexical da Etapa 2 esteja funcionado, o programa que voc ir entregar nessa etapa dever poder analisar uma entrada do tipo: tmp + (x*( 3.14 - y_0z )), reconhecer que essa entrada se decompe em uma seqncia de tokens tal como a sentena acima, e em torno que essa sentena sintaticamente correta (ou seja de acordo com a gramtica). Para implementar o analisador sinttico, voc dever obrigatoriamente usar o algoritmo LL(1) apresentado na 7a aula (26 de Agosto). Este algoritmo usa, internamente: Uma pilha. Voc pode usar a pilha implementada na Etapa 1. A pilha dever armazenar smbolos terminais (tokens) e no-terminais (a denir em funo da gramtica). Como os terminais retornados por seu analisador lexical so representados atravs de int, sugere-se usar tambm uma encodicao em int de seus smbolos no-terminais. Un analisador lexical para ler um por um os tokens da entrada. Isso j vem provido pelo procedimento yylex() implementado, graas ao Flex, na Etapa 2 (ver o main provido na Etapa 2). Uma tabela de deciso, a tabela LL(1). Voc dever montar essa tabela e implement-la em C para que possa orientar o comportamento do seu parser. Seu parser chamado pico deve aceitar como argumento na linha de comando o nome do arquivo contendo o input (j era o comportamento do seu scanner).

18 A sada do seu parser, na tela, deve ser a seguinte: OKAY no caso que a entrada esteja de acordo com a gramtica; ERROR no caso contrrio.


Tanto o algoritmo de montagem da tabela LL(1), como seu uso pelo parser, se encontram nas lminas do encontro 7. Salienta-se que a gramtica acima indicada no LL(1), por motivos que deveriam aparecer diretamente a quem lembra da aula. A primeira parte dessa etapa consiste em transformar essa gramtica numa gramtica equivalente, e que seja LL(1). Para montar a tabela LL(1), ser necessrio calcular os conjuntos First e Follow de sua gramtica transformada. importante entender que no ser preciso programar o clculo desses conjuntos para qualquer gramtica: basta faz-lo, manualmente, para sua gramtica; deduzir a tabela LL(1) que a reconhecer; e implementar o parser para essa gramtica.

4.2

Entrega do trabalho

O diretrio src/Etapa3 de Pico dever incluir, pelo menos: um arquivo txt gramatica.txt contendo sua gramtica transformada, seguindo o formato seguinte (a ttulo de exemplo, usa-se aqui a gramtica acima apresentada): E -> E + E E -> E * E etc... um arquivo txt tabelaLL1.txt contendo a tabela LL(1), no formato seguinte: Simbolo ( E (E) etc... ) + - * / F_LIT INT_LIT F_LIT IDF $

(cada coluna para um smbolo no-terminal em uma linha mostra a derivao a ser aplicada ao nterminal, quando o prximo token lido o rtulo da coluna. Por exemplo, aqui, tendo-se E no topo da pilha, e lendo-se o token (, deve-se derivar o E em ( E ).) A implementao em C de seu parser LL(1), que dever incluir (e chamar) o analisador lexical da Etapa 2; Um arquivo Makele que o compila (ver o Makele de src/Etapa2 para se ajudar). Casos de teste.


Chapter 5

Especicao da Etapa 4Essa etapa consiste na denio da gramtica usada no compilador Pico e na implementao de um parser que a reconhea, graas ferramenta Yacc (Bison). Sugere-se (mas no obrigatrio) distribuir partes da gramtica entre os trs integrantes, cada qual se responsabilizando pela implementao de um pedao. Para a programao, pode-se usar o cdigo fonte original liberado no Moodle (pico-etapa4.1.tar.gz). Vem a estrutura de diretrios usual, com Makeles prontos para serem usados. A nica parte dos Makeles que pode ser alterada so as regras que dizem respeito ao diretoio Pico/Tests/ e s etapas 2 e 3. No se pode r alterar Pico/Makele, nem Pico/src/Etapa4/Makele. Voc deve: baixar e unzipar pico-etapa4.1.tar.gz; copiar em src/Etapa1, src/Etapa2 e src/Etapa3/ os arquivos de suas implementaes prvias das 3 primeiras etapas. Para as etapas 2 e 3, podem recuperar tambm os Makeles que vocs usaram; desenvolver a etapa 4 em src/Etapa4; compil-la a partir de Pico/, com o comando make etapa4. Os tutores daro suporte no uso dos Makeles apenas se sua estrutura for respeitada.

5.1

Ajustes no analisador lexical

Foram esquecidos quatro tokens simples a serem acrescentados no scanner da Etapa 2 (arquivo Pico/src/Etapa2/scanner.l): :, END, FALSE e TRUE. Basta completar este arquivo com as 4 linhas (na seo correta): ":" {return(:);} "end" {return(END);} "true" {return(TRUE);} "false" {return(FALSE);} Comentrio importante. O cdigo fonte entregue (pico 4.1) vem com Makeles prontos para ajud-lo a compilar seu parser da etapa 4. Os Makeles sistematicamente re-aproveitam Pico/src/Etapa2/scanner.l para obter o scanner usado pelo Yacc. Ou seja, qualquer modicao que voc queira ou precise fazer em seu scanner deve ser feita no diretrio da Etapa 2, se no ela no ser enxergada pela Etapa 4.

20


5.2

Gramtica

Um programa Pico composto por uma seo de declaraes, seguida de uma seo de aes (ver o start da gramtica no arquivo pico.y fornecido).

5.2.1

Declaraes

A seo de declaraes pode estar vazia, ou composta por uma ou mais declarao, separada(s) pelo terminal ; Uma declarao composta por uma lista de identicadores, seguida por :, seguido por um indicador de tipo. Uma lista de identicadores consiste em um nmero qualquer de (pelo menos um) identicador(es) separado(s) por ,. Um indicador de tipo pode derivar em: cada um dos 4 terminais que informa um tipo (ver o captulo sobre o scanner), ou cada um dos 4 terminais que informa um tipo, seguido de [, seguido de uma lista de duplas de inteiros, seguida de ]. Uma lista de duplas de inteiros composta por qualquer nmero (maior ou igual a 1) de ocorrncias da seqncia de trs smbolos seguintes: INT_LIT : INT_LIT, cada ocorrncia sendo separada da seguinte por ,. Exemplo 1 de declaraes: x, tmp_1 : double; Exemplo 2 de declaraes: x:float; z1t2 , i :float

Exemplo 3 de declaraes: x:float; tab : double[10:20, 30:10, 0:5]; y:float Neste ltimo caso, encontra-se uma lista de trs duplas de inteiros: 10:20, 30:10 e 0:5. Comentrio. Observa-se que nessa etapa de denio da sintaxe, no se associa semntica ainda a essas construes. No entanto, parece intuitivo que este tipo de declarao servir para denir um array de 3 dimenses e que cada dupla n:m dene os valores mnimos e mximos autorizados para o ndice em uma direo. Nessa lgica, a segunda dupla 30:10 parece dever levar a um erro, pois se est tentando declarar um array com um limite inferior de ndice maior do que o limite superior na segunda dimenso. Repara-se que isso seria um erro semntico, tipicamente detectado na prxima etapa, e no nessa.

5.2.2

Aes

A seo de aes composta por um ou mais comandos, separados pelo terminal ;. Um comando pode ser composto por: uma atribuio, do tipo: lvalue = expr, ou um enunciado simples.Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

5.2 Gramtica

21

Comentrio importante. Nota-se que o ; no faz parte, sintaticamente falando, do comando. Pelo contrrio, na linguagem denida aqui, ele um separador de comandos. Isso signica que seu parser dever aceitar, eventualmente, um nico comando sem ponto-vrgula no m (ver o exemplo abaixo com o while() {}). Isso tambm signica que no ser sintaticamente correta a presena de um ponto-vrgula nico (sem comandos a separar). lvalue pode ser ou um identicador simples, ou um identicador seguido por [, seguido por uma lista de expr, seguida por um terminal ] nal. Uma lista de expr composta por pelo menos uma expr; se tiver mais de uma, devem ser separadas por ,. Uma expr abrange: duas expr separadas por um dos terminais que representa um operador aritmtico; ou uma expr entre parnteses; ou um literal nico, inteiro ou com vrgula utuante; ou uma lvalue tal como denida acima; ou uma chamada a um procedimento. Uma chamada a procedimento consiste em um identicador, seguido de uma lista de expr (se tiver mais de uma expr na lista, elas devem ser separadas por ,) entre parnteses. Um enunciado simples se limita a uma expr ou a uma instruo de controle. Uma instruo de controle pode ser: IF, seguido de (, seguido de uma expresso booleana, seguida de ), seguido de THEN, seguido de um ou vrios comando(s) (no sentido denido acima), seguido de: Ou o terminal END; Ou o terminal ELSE, seguido por um ou vrios comandos (no sentido denido acima), seguido(s) pelo terminal END. WHILE, seguido de (, seguido de uma expresso booleana, seguida de ), seguido de {, seguido por um ou vrios comandos (no sentido denido acima), seguido(s) por }. Por m, uma expresso booleana denida recursivamente da forma seguinte: pode ser: Ou o terminal TRUE; Ou o terminal FALSE; Ou uma expresso booleana entre parnteses; Ou duas expresses booleanas separadas por um dos operadores lgicos reconhecidos pelo scanner (AND, OR); Ou uma expresso booleana precedida pelo token NOT; Ou duas expr separadas por um dos operadores relacionais (tokens: , LE, GE e EQ). Exemplos de aes: x = 1; f(2-3,x) + tmp1; if ( g(tmp[1,2]*2) 0) && y!=1 ) { x=0 } endGerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

22


(Nota-se, nas iteraes do while, que elas se limitam a apenas um comando x=0, portanto sem pontovrgula no m.) Exemplo de programa Pico inteiro: i,n : int; x:double x = 2.0; i=0 ; n=10; while (i = == != op2 como op1. label como o rtulo denido para a instruo GOTO (aceitando, inclusive, o nmero da linha, precedido por um underscore, conforme explicado anteriormente). e.g., 000: IF 4 1 instrues assembly, pois h necessidade de salvar registradores, us-los e restaurar seu contedo. e.g., 003: 012(Rx) := 008(Rx) ADD 016(SP)Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

8.2 Data de entrega convertida em _003: MOVL ADDL MOVL 8(%EDX) , %EAX 16(%ECX) , %EAX %EAX ,12(%EDX)

37

A instruo TAC print ser implementada atravs de uma chamada ao procedimento printf da linguagem C da seguinte maneira: 005: PRINT 004(SP)

convertida em _005: PUSHL 4(%ECX) PUSHL $intf CALL printf seu trabalho ser apenas traduzir 004(SP) em 4(%ECX), nesse caso. Para saber que registradores da arquitetura correspondem a SP e Rx, veja o arquivo template.model. A converso do nmero de linha TAC para o cdigo assembly como mostrado anteriormente. No ser cobrada indentao para o cdigo assembly. O cerne da avaliao ser o executvel gerado e sua correspondncia com a linguagem processada pelo pico. Isso no signica, entretanto, que o cdigo gerado no ser avaliado.

8.1.4

Limitaes & Facilidades

O emprego de nmeros em ponto utuante no ser cobrado nessa etapa, tratando apenas operaes com nmeros inteiros. A avaliao de expresses booleanas tambm no precisar ser curto-circuito.

8.2

Data de entrega

A etapa 7 dever ser entregue at o dia 01 de Dezembro, 23h00. O script pias e os demais executveis devero se encontrar no diretrio Pico/src/Etapa7.


38



Chapter 9

AvaliaoA avaliao se far em duas etapas. Primeiramente, seu programa ir ser testado de forma automatizada: programas C pre-escritos iro ser compilados junto com suas implementaes de tabela de smbolos e de pilha, e executar operaes usuais nelas para vericar sua conformidade especicao (exemplos de tais testes sero providos nessa semana). A conformidade ir levar a 50% da nota nal obtida nessa etapa 1. Salienta-se que, nessa fase, programas de vericao de cpia e programas de busca por cdigo on-line sero usados para detectar eventuais fraudes. A outra metade da nota ser atribuda em funo da apresentao informal que vocs faro em laboratrio, no dia 25 de Setembro, ao seu tutor: resultados dos testes, discusso da implementao, validao atravs de outros testes, documentao. Todos os trs alunos podem ser indagados sobre qualquer parte da implementao, at mesmo quem no programou uma funcionalidade: espera-se que todos os integrantes tenham entendido como tudo foi programado. Opcionalmente, o tutor poder aplicar um questionrio rpido, e escrito, para testar o conhecimento do programa entregue. Qualquer tentativa, mesmo parcial, de reaproveitamento de cdigo de colegas ou da Web, ir zerar a nota.

40

Avaliao


Chapter 10

Anexo tcnico: Doxygen e Make10.1 Introduo ao D OXYGEN

Todo o contedo deste tutorial foi retirado de http://www.stack.nl/~dimitri/doxygen/ manual.html. Recomenda-se consultar a fonte para mais detalhes. O que segue so as notaes recomendadas para o projeto da disciplina de Compiladores (INF01147/INF01033) 2008/2. Gerador de documentao para cdigo-fonte, o D OXYGEN um sistema de documentao para C++, C, Java, Objective-C, Python, etc. Dentre outras capacidades, o D OXYGEN pode gerar um sistema de documentao on-line (em HTML) e/ou A um manual de referncia off-line (em LTEX) de um conjunto de cdigos-fonte propriamente documentados. Tambm h suporte para gerar a sada em RTF (MS-Word), PostScript, PDF com hyperlinks, HTML compactado e pginas man do UNIX. A documentao extrada diretamente dos cdigos-fonte, tornando mais fcil a manuteno da documentao. Disponvel para Windows, Linux e MacOS-X.

10.1.1

Comandos Bsicos em C

Existem muitos mtodos diferentes para escrever um comentrio no estilo D OXYGEN . Listados, a seguir, os mais comuns. 10.1.1.1 Blocos de Comentrios Simples

Comentrios simples na sintaxe da linguagem podem ser colocados normalmente. Por padro, o D OXYGEN no gerar estes comentrios na sada, ignorando sua presena. So necessrios identicadores especiais para os comandos D OXYGEN . /* comentario simples */ 10.1.1.2 Blocos de Comentrios Breves

Um dos modos em que o D OXYGEN pode gerar comentrios, estes so produzidos na sada; devem possuir apenas uma linha, so usadas para consideraes pontuais importantes (como a descrio do que faz um lao for complexo) e sua sintaxe a seguinte: /** comentario breve */

42 Tambm pode ser obtido atravs da tag \brief: /* \brief comentario breve */ 10.1.1.3 Blocos de Comentrios Detalhados

Anexo tcnico: Doxygen e Make

Um dos modos em que o D OXYGEN pode gerar comentrios, estes so produzidos na sada; usados para descries detalhadas de blocos dos arquivos, em vrias linhas (como o header do cdigo fonte ou cabealho de funo). Sua sintaxe a seguinte: /** * comentario detalhado * */ 10.1.1.4 Tags Especiais

Algumas tags (marcaes especiais do cdigo que aparecem an documentao nal) so de especial uso neste projeto: \author : nome autor do autor do cdigo em questo (vrios autores de vrios author sero agrupados no mesmo pargrafo). \version : verso atual do cdigo (e.g., nmero da etapa do projeto). \date : data da primeira e ltima modicao no cdigo. \bug : descreve possveis bugs que a aquele trecho de cdigo apresenta. \warning : aviso no uso daquele trecho de cdigo. \param : identica o parmetro de uma funo. Deve ser usado com as palavras-chave in e out para indicar o tipo de atributo (entrada ou sada) e uma breve descrio. \return : valor de retorno de uma funo. \le : identica o arquivo (nome dele no sistema de arquivos) ao qual o comentrio se refere. Em geral o nome do arquivo de cdigo-fonte e aparece apenas no header. Por exemplo, /** * \file minhas_funcoes.c * \brief Arquivo com as minhas funcoes. */ /** * * * * * * * MinhaFuncao \brief Copia sequencias de bytes. \author Bill Gates \author Linus Torvalds \version 4.0 \date 1996-1998 \bug Trava muito e requer muita memoria. \bug A medida que eh usada introduz mais bugs.Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

10.2 Introduo ao Make * \warning Nao confie nesta funcao. * \warning Nem neste comentario. * * Nao faz nada e soh consome memoria. * \param[out] dest Area de destino. * \param[in] src Area de origem. Numero de bytes. * \param[in] n \return Nada. * */ void minha_funcao(void *dest, const void *src, size_t n); 10.1.1.5 Uso

43

O D OXYGEN consegue determinar a que bloco de cdigo um comentrio se refere. Isso signica que blocos que antecedem uma funo referem-se funo e blocos que antecedem todo o arquivo so o header do arquivo na documentao. Neste projeto, trs blocos so o suciente para que o arquivo seja considerado documentado: o header, o descritor da funo e comentrios de trechos importantes de cdigo. Em anexo, segue um exemplo.

10.210.2.1

Introduo ao MakeIntroduo

Make um programa GNU linux que automatiza o procedimento de criao e manuteno de grupos de programas, vericando dependncias e possibilitando a compilao de cdigos. O objetivo de make determinar automaticamente as partes de um programa relativamente grande que precisam ser recompiladas, provendo os comandos necessrios para tal nalidade. Com make podem ser descritas muitas tarefas onde arquivos precisam ser atualizados automaticamente a partir da modicao de outros. Em um programa, o arquivo executvel obtido a partir de arquivos objeto, os quais so oriundos da compilao de arquivos fontes. Com apenas uma nica chamada de make, todas as mudanas realizadas em arquivos fonte podem ser recompiladas, uma vez que make se baseia nos tempos das ltimas modicaes do arquivo. Caso no haja nenhuma alterao, no ser necessria a compilao, no havendo a necessidade de recompilao de todo cdigo

10.2.2

Composio de um arquivo makele

Para usar make, necessrio criar um arquivo chamado makele que descreve as relaes entre os arquivos do programa e os estados dos comandos para a atualizao de cada arquivo. Em um arquivo makele podem ser utilizados labels (rtulos) e targets (alvos), de maneira que na chamada de make possa haver o reaproveitamento de nomes, bem como a invocao de diferentes alvos. Tambm possvel vericar dependncias. Por exemplo, se o arquivo makele tiver a seguinte especicao: FILENAME=fonte FLAGS= -g -Wall compilar: ${CC} -o ${FILENAME} ${FILENAME}.c ${FLAGS} executar: ${FILENAME} ./${FILENAME}Gerado em Mon Aug 4 21:56:27 2008 para Pico por Doxygen

44

Anexo tcnico: Doxygen e Make

apagar: rm ${FILENAME}.o rm ${FILENAME} clear Tem-se um label, F ILEN AM E, o qual est referenciando a palavra "fonte", sendo usado em diferentes partes do script como uma "varivel" e a label FLAGS, o qual invocada apenas em uma das targets Ao mesmo tempo, tm-se trs targets que podem ser chamados atravs de: nome@maquina:/home/usuario: make compilar nome@maquina:/home/usuario: make executar nome@maquina:/home/usuario: make apagar No primeiro caso haver a compilao do cdigo utilizando o compilador gcc. Este invocado atravs de uma varivel externa. J as ags de documentao esto referenciadas em FLAGS. No segundo caso a target verica a existncia do cdigo executvel (repare que isto feito logo aps os dois pontos) e se isto for verdadeiro ele executa o cdigo. J no terceiro caso haver a execuo de trs comandos: a excluso do arquivo objeto, a excluso do arquivo executvel e a "limpeza" do terminal. Para o acesso ao contedo de um label basta utilizar $ antes do label, sendo esta colocada entre chaves. Outra observao importante de que os comandos precisam ser colocados a partir da linha seguinte de target, iniciando sempre com um tab. atravs da invocao dos targets que se pode executar uma srie de comandos prticos, simplicando o processo de compilao.

10.2.3

Maiores Referncias

Sugere-se a consulta de: man make http : //www.gnu.org/sof tware/make http : //www.gnu.org/sof tware/make/manual/make.html


Documents

pico