\documentclass[10pt]{letter}

\usepackage{portuges}
\usepackage{isolatin1}

\pagestyle{empty}

\date{}

\textheight 9in
\topmargin -0.7in

\newcommand{\section}[1]{\vspace{3mm}{\emph{#1}}\vspace{2mm}}

\begin{document}
\pagestyle{empty}

\begin{center}
  \LARGE
  MAC-221 --- Construção de Montadores \\
  MAC-222 --- Sistemas de Programação \\[1cm]
  \large
  1998 ---   Especificação da terceira fase do Montador p/ MIPS
\end{center}

\vspace{2mm}


\section{Idéias gerais}

Na terceira fase do montador para o processador RISC MIPS R2000 deve-se
completar o montador.  A novidade em relação à segunda fase é a montagem dos
``opcodes'' proprimante ditos.

Nesta fase deverá ser utilizado o analisador léxico gerado na primeira fase e
o analisador sintático gerado na segunda fase.  A maior parte das alterações
no código será feita nas ações associadas às regras gramaticais presentes no
fonte do bison\footnote{Quanto à depuração do analisador sintático, além da opção
\texttt{-v} dada ao bison, que gera o arquivo \texttt{.output}, pode-se
inserir a linha \texttt{\#define YYDEBUG 1} à seção de cabeçalhos do arquivo
fonte do bison e uma atribuição não nula à variável \texttt{yydebug} faz um
``tracing'' no empilhamento dos tokens e das reduções realizadas.
}.


\section{O analisador léxico}

Nesta fase deverá ser utilizado o analisador léxico gerado na primeira
fase.  Poucas alterações serão necessárias.
A principal diferença é que os valores semânticos deverão ser tratados agora,
inclusive o valor semântico do token \texttt{STR}. 

Os módulos já definidos, incluindo-se aquele gerado pelo flex e que implementa
a função \texttt{yylex()} e o módulo necessário à manipulação da tabela de
hashing serão usados como antes.  O módulo \texttt{testlex} será omitido mas
pode ser utilizado nalgum outro executável de forma a se obter uma listagem
dos ítens léxicos que estão sendo sucessivamente remetidos ao analisador
sintático.


\section{O analisador sintático}

Todas as \emph{instruções}, \emph{pseudoinstruções} e \emph{diretivas} deverão
ser reconhecidas corretamente.

No caso das instruções, o reconhecimento sintático deve ser \emph{estrito}, ou
seja, todas as possíveis combinações de operandos devem ser reconhecíveis e
nenhuma a mais.  Todas as diretivas \texttt{.align}, \texttt{.text}, \texttt{.data},
\texttt{.sdata}, \texttt{.rdata}, \texttt{.comm}, \texttt{.lcomm},
\texttt{.word}, \texttt{.byte}, \texttt{.half}, \texttt{.double},
\texttt{.ascii} e \texttt{.asciiz} também devem ter reconhecimento sintático
\emph{estrito}, bem como as pseudoinstruções \texttt{la} (load address),
\texttt{li} (load immediate), \texttt{move} e \texttt{nop} (no operation).

Todas as demais pseudoinstruções e diretivas podem ter um reconhecimento
sintático \emph{relaxado}, ou seja, todas as combinações corretas de operandos
devem ser reconhecíveis mas pode-se reconhecer como sintaticamente corretos
operandos incorretos.  Isto não trará problemas
para estas pseudoinstruções e diretivas pois não serão implementadas a
princípio.

Várias instruções dos tipos \texttt{R3} e \texttt{J} podem ter uma segunda
sintaxe, e devem ser implementadas, como já comentado na segunda fase.  Mais
detalhes também podem ser encontrados no ítem $3$ do arquivo
\texttt{Observacoes.txt}.



\section{Recuperação e relatório de erros}

O programa deve ser capaz de se recuperar de um erro sintático, prosseguindo a
análise sintática nas linhas subsequentes.  Quanto à
função \texttt{yyerror()} deve dar informações sobre onde ocorreu o erro
sintático.  Ao menos o número da linha em que foi detectado o erro (basta que
\texttt{yylex()} conte os caracteres de mudança de linha) e o valor de
\texttt{yytext} do último token lido deve ser impresso.

De fato, o arquivo fornecido
\texttt{testsint.c} já possui uma implementação de uma tal função
\texttt{yyerror()} e também tem uma função 
\texttt{main()} que inicializa a tabela de símbolos, lê os parâmetros da linha
de comando e chama \texttt{yyparse()}.  Este arquivo, como todos os demais que
foram fornecidos, pode ser alterado.  Em particular, a função \texttt{main()}
nele presente não cuida de chamar a função \texttt{savecoff()} ou tratar
adequadamente o caso de um montador de um ou de dois passos.  Esta função
\texttt{main()} certamente \emph{deverá} ser alterada.

Será recusado um projeto que simplemente dê uma mensagem do tipo \texttt{`parse
  error'} sem dar as informações necessárias à localização da linha e do token
em que ocorreu o erro.


\section{Arquivos fornecidos}

O diretórios (que são idênticos)
\begin{quote}
  \texttt{<http://www.ime.usp.br/\~{ }alair/mac221-98/TerceiraFase/>}\\
  \texttt{<http://www.ime.usp.br/\~{ }alair/mac222-98/TerceiraFase/>}
\end{quote}
contêm a especificação da terceira fase e arquivos auxiliares à confecção do
montador.  Um arquivo com todo o conteúdo do diretório pode ser
encontrado em  
\begin{quote}
  \texttt{<http://www.ime.usp.br/\~{ }alair/mac221-98/TerceiraFase.tar.gz>}\\
  \texttt{<http://www.ime.usp.br/\~{ }alair/mac222-98/TerceiraFase.tar.gz>}\\
\end{quote}
Para ser extraído, basta usar o comando
\begin{quote}
  \texttt{tar xvzf TerceiraFase.tar.gz}
\end{quote}
no linux\footnote{Quem usa o \texttt{DJGPP} pode fazer o mesmo já que o
  \texttt{DJGPP} possui o \texttt{tar} e o \texttt{gzip}.}.

Nesses diretórios são fornecidos os arquivos:
\begin{itemize}
\item \texttt{Tokens-2.6} com a especificação dos tokens;
\item \texttt{Observacoes.txt} com várias observações sobre o projeto.
\end{itemize}
Estes dois arquivos \emph{fazem parte da especificação do projeto} e poderão
ser alterados de forma a dar mais esclarecimentos porventura necessários.

São fornecidos ainda vários arquivos que \emph{podem} ser usados na implementação
do projeto:
\begin{itemize}
\item \texttt{symrec.h} com a especificação de uma tabela de símbolos;
\item \texttt{symrechash.c} com uma implementação da tabela de símbolos
  através de uma tabela de hashing (com uma função de hashing simples);
\item \texttt{initsymrec.c} com uma função que inicializa a tabela de hashing;
\item \texttt{token2hash} um script AWK que processa o arquivo
  \texttt{Tokens-2.6} e gera um vetor de inicialização com as palavras
  reservadas a serem inseridas inicialmente na tabela de Hashing;
\item \texttt{testsint.c} com a função \texttt{yyerror()} e a função
  \texttt{main()};
\item \texttt{token2bison} um script AWK que processa o arquivo
  \texttt{Tokens-2.6} e gera definições como \texttt{\%token} e
  \texttt{\%union} para o bison;
\item \texttt{Makefile} um arquivo descritor das dependências entre os
  diferentes arquivos do projeto;
\item \texttt{coff.h} um arquivo com o a descrição dos cabeçalhos e seções
  presentes no executável a ser gerado;
\item \texttt{savecoff.h} um arquivo com o protótipo da função
  \texttt{savecoff()}, ne\-ces\-sária à geração do arquivo executável a ser
  simulado pelo \texttt{SPIM};
\item \texttt{savecoff.c} um arquivo que implementa a função \texttt{savecoff()};
\item outros arquivos/scripts AWK relacionados às fases anteriores do projeto;
\item \texttt{exemplos} um diretório que será comentado mais tarde; 
\item \texttt{<ftp://ftp.linux.ime.usp.br/pub/alair/>}, um diretório com programas
  auxiliares, que também será comentado mais tarde.
\end{itemize}


\section{Usando os arquivos fornecidos}

Com os arquivos fornecidos, basta escrever os arquivos \texttt{analex.l},
\texttt{anasintdef.y} e \texttt{anasintregras.y} compatíveis e alterar
propriamente o arquivo \texttt{testasint.c}.  Rodando
\texttt{make}, o \texttt{Makefile} fornecido é analisado e é gerado o
arquivo executável \texttt{./monta}.  Se só estes arquivos forem implementados,
basta entregar um arquivo-pacote \texttt{.tar}\footnote{\flushleft O comando \texttt{tar
    cvzf meutar.tgz analex.l anasintdef.y anasintregras.y testasint.c} monta o pacote.}
(ou um \texttt{.zip}) dos quatro arquivos.  Se os arquivos fornecidos forem
alterados ou outros arquivos forem acrescentados, todos estes arquivos devem
ser entregues neste pacote.  Com o pacote entregue e extraído sobre um
diretório contendo previamente os mesmos arquivos entregues na especificação
da TerceiraFase, deve-se ser capaz de gerar o executável, de nome
\texttt{monta} simplesmente rodando \texttt{make}.


\section{Documentação fornecida}

Está à disposição no Xerox o apêndice A da primeira edição do excelente livro
``Computer Organization \& Design: The Hardware / Software Interface'' de
autoria de Patterson \& Hennessy.  Este apêndice contém os `opcodes' das
instruções do MIPS 2000 bem como sua sintaxe e \emph{DEVE} ser consultado.  Há
alguns erros no apêndice e o arquivo \texttt{Observacoes.txt} e
\texttt{Tokens-2.6} têm informações mais confiáveis quando houver
discrepância.  Uma terceira fonte de informação é o manual do SPIM que também
está no xerox.  Já no apêndice A há alguma informação referente ao SPIM.


\section{Diretório \texttt{exemplos}}

Este diretório possui vários arquivos assembly (\texttt{.s}) para o MIPS.  Possui também
alguns arquivos C (\texttt{.c}) que podem ser cross-compilados de forma que se gerem
os correspondentes arquivos \texttt{.s}.  O arquivo \texttt{Makefile} presente
neste diretório oferece regras de como fazer esta cross-compilação.

O ``cross-compiler'', disponível apenas em linux, pode ser encontrado em
\begin{quote}
  \texttt{<ftp://ftp.linux.ime.usp.br/pub/alair/>}
\end{quote}
juntamente com o simulador \texttt{spim}. (Já estão instalados na rede linux
do IME.)  Há também uma versão do simulador \texttt{spim} que roda em DOS.

O diretório \texttt{<ftp://ftp.linux.ime.usp.br/pub/alair/cross-compiler/>} contém
um cross-compiler e cross-assembler que gera código para uma máquina MIPS
little endian: uma decstation rodando o sistema operacional ultrix.  O arquivo
\texttt{<ftp://ftp.linux.ime.usp.br/pub/alair/spim.tar.gz>} é uma versão do
\texttt{SPIM} (simulador MIPS) que simula a execução de um binário gerado para
esta decstation, com algumas restrições que serão vistas abaixo.  Eventuais
versões do \texttt{SPIM} encontradas na internet não são suficientes.

\section{Cross-compilação e simulação do MIPS}

Juntamente com os executáveis para linux do SPIM (e XSPIM), que permitem a
simulação da execução de um programa gerado para a plataforma
decstation/ultrix, foram fornecidos vários exemplos e arquivos necessários à
confecção destes exemplos.  Estes exemplos podem ser executados dentro do SPIM
como veremos abaixo e encontram-se no subdiretório 
\texttt{exemplos}.

O SPIM não emula as chamadas de sistema necessárias à implementação de toda
uma biblioteca de funções como a \texttt{libc}.  Isto em particular implica
que os arquivos \texttt{.c} cross-compilados não podem fazer referência a
funções como \texttt{printf}, \texttt{scanf} ou \texttt{fopen}.  O SPIM
fornece dez chamadas de sistema enumeradas em \texttt{spim-syscall.h}.  Uma
interface para reconhecimento destas chamadas a partir de programas
\texttt{.c} está descrita no arquivo \texttt{spimio.h} e a implementação desta
interface está presente no arquivo \texttt{start.asm}, um arquivo assembly que
deve ser preprocessado primeiramente, gerando o arquivo \texttt{start.s}.  O
arquivo \texttt{start.o} deve ser linkado com cada arquivo objeto
cross-compilado que se deseje simular no SPIM.  Além da implementação da
interface antes descrita, o arquivo faz as inicializações e finalizações
necessárias para executar a função \texttt{main}.  Existe um \texttt{Makefile}
que descreve como devem ser gerados os executáveis para serem simulados no
SPIM.

Tomemos como exemplo o arquivo \texttt{hello.c}.  O arquivo \texttt{hello.c},
é compilado para um arquivo assembly \texttt{hello.s} (a opção \texttt{-S} é
usada para a geração do assembly).  O arquivo \texttt{hello.s}, é então
montado para um arquivo objeto \texttt{hello.o}.  Uma listagem dos bits
montados pode ser obtida com a opção \texttt{-a -EB} fornecida ao montador e
pode-se fazer uma separação primária dos campos de bits fornecendo esta saída
como entrada para o script AWK \texttt{separabits}.  O
arquivo \texttt{hello.o} é então linkado com \texttt{start.o}.  É fornecida ao
ligador \texttt{ld} a opção \texttt{-T script-spim} que diz em que endereços devem ser
alocados quais segmentos de forma que o SPIM possa simular o programa.  O SPIM
supõem que hajam somente dois segmentos: \texttt{.text} que começa em
$0x04000000$, e \texttt{.data} que começa em $0x10000000$.  Para a execução do
arquivo executável, já linkado, executamos o spim como da forma:
\begin{quote}
  \texttt{./spim -execute hello}
\end{quote}
ou ainda trocando \texttt{./spim} por \texttt{./xspim -fn fixed}.







\section{Geração de código}

O montador deverá gerar código suficiente para que os
arquivos \texttt{test0.s}, \texttt{test1.s} e \texttt{test2.s} sejam montados
e executados pelo SPIM.  Estes arquivos \texttt{test*.s} têm versões editadas
dos arquivos assembly gerados pela cross-compilação dos exemplos acima
mencionados.  Esta edição é necessária para incluir o conteúdo do
arquivo \texttt{start.asm}, já que o arquivo gerado pelo montador não será
linkado.  (Isto requeria a geração de um arquivo objeto com as informações
necessárias a uma realocação e solução de referências cruzadas.)

Como já especificamos na segunda fase, cada diretiva, pseudoinstrução e
instrução deverá ser reconhecida sintaticamente.  Quando nada além da análise
sintática for feito, diremos que a linha está sendo \emph{ignorada}.  Caso
contrário diremos que está sendo \emph{implementada}.  A implementação de uma
instrução ou pseudoinstrução implica a geração de código e a montagem de
alguns bytes.  A implementação de uma diretiva tipicamente altera a
configuração corrente do montador e pode também implicar a cópia de alguns
bytes nalgum segmento.  De fato, cada diretiva é um caso.  Todas as diretivas
implementadas deverão ter um reconhecimento sintático estrito.

Serão implementadas todas as instruções.  Instruções que
possuirem uma segunda sintaxe também devem ter esta segunda sintaxe
implementada.  As
pseudoinstruções \texttt{la} (load address), \texttt{li} (load immediate),
\texttt{move} e \texttt{nop} deverão ser implementadas.

Uma pseudoinstrução \texttt{la \$v0,x} pode ser implementada
pelos opcodes correspondentes às instruções:
\begin{quote}
\begin{verbatim}
    lui     $v0,xh
    addiu   $v0,$v0,xl
\end{verbatim} %$
\end{quote}
onde \texttt{xh} corresponde aos $16$ bits mais significativos do endereço
associado ao rótulo \texttt{x} e \texttt{xl} corresponde aos $16$ bits menos
significativos.  Caso o endereço \texttt{x} possa ser alcançado por
\texttt{\$gp} mais um deslocamento de $16$ bits (o que significa que o
endereço está entre $0x10000000$ e $0x1000FFFF$) a pseudoinstrução também pode
ser implementada pelo opcode correspondente à instrução
\begin{quote}
\begin{verbatim}
    addiu   $v0,$gp,x-0x10008000
\end{verbatim}
\end{quote}
já que o valor de \texttt{\$gp} é $0x10008000$.  Esta hipótese pode ser
pressuposta pelo montador e isto leva a um montador que restringe ao máximo de
$64Kbytes$ no segmento de dados.
Uma pseudoinstrução \texttt{li \$v1,num} pode ser implementada de
duas formas: pelo opcode correspondente à instrução
\begin{quote}
\begin{verbatim}
    addiu   $v1,$zero,num
\end{verbatim}
\end{quote}
caso \texttt{num} seja um inteiro de $16$ bits; ou ainda
pelos opcodes correspondente às instruções
\begin{quote}
\begin{verbatim}
    lui     $v1,numh
    ori     $v1,$v1,numl
\end{verbatim}
\end{quote} %$
onde \texttt{numh} corresponde aos $16$ bits mais significativos e
\texttt{numl} corresponde aos $16$ bits menos significativos de \texttt{num}.
Quanto à pseudoinstrução \texttt{move \$t1,\$t2}, ela pode ser implementada
pelo mesmo opcode da instrução \texttt{addu \$t1,\$t2,\$zero}.  A
pseudointrução \texttt{nop} corresponde ao opcode $0$ (zero).  Pode-se fazer
testes com o cross-assembler caso se queira verificar o código que está sendo
gerado pelo \texttt{GNU as} para estas pseudoinstruções.  O arquivo
\texttt{pseudos.s} no diretório \texttt{exemplos} já possui estas
pseudoinstruções.

As seguintes diretivas deverão ser \emph{implementadas}: \texttt{.align}, \texttt{.text},
\texttt{.data}, \texttt{.ascii}, \texttt{.asciiz}.  As diretivas
\texttt{.sdata} e \texttt{.rdata} serão
``implementadas'' como sinônimos de \texttt{.data}.  Os possiveis parâmetros
numéricos que seguem às diretivas \texttt{.text}, \texttt{.data},
\texttt{.sdata} e \texttt{.rdata} são
ignorados.  As diretivas
\texttt{.word}, \texttt{.byte}, \texttt{.half}, \texttt{.double},
\texttt{.ascii} e \texttt{.asciiz} também devem ter reconhecimento sintático
\emph{estrito}, bem como as pseudoinstruções \texttt{la} (load address),
\texttt{li} (load immediate), \texttt{move} e \texttt{nop}.


As diretivas \texttt{.comm} e \texttt{.lcomm} serão implementadas
da seguinte forma: \texttt{.comm primo,2044} terá o efeito de definir o rótulo
\texttt{primo} no corrente endereço do segmento \texttt{.data} e reservar-lhe
um total de $2044$ bytes que serão inicializados com zeros.  Estas diretivas
deveriam ser tratadas pelo linker, usualmente.  As diretivas
\texttt{.word}, \texttt{.byte}, \texttt{.half} e \texttt{.double} também devem
ser implementadas.

Outras diretivas e/ou pseudoinstruções também poderão ser implementadas.

Para cada um dos segmentos \texttt{.text} e \texttt{.data} deveremos ter: um
vetor, que armazena os bytes que são montados nos respectivos segmentos; e um
contador de endereços, que conta os endereços correntemente associados à
próxima instrução/palavra a ser montada no segmento.  Uma vez terminada a
montagem do programa, deve-se gerar um arquivo executável no formato COFF
littleMIPS que possa ser carregado no SPIM.  Para tanto, faça uso da função
\texttt{savecoff()}, cujo protótipo está fornecido no arquivo
\texttt{savecoff.h}.  O contador de endereços do segmento \texttt{.text} deve
ser inicializado com $0x400000$ e o do segmento \texttt{.data} deve ser
inicializado com $0x10000000$.  Isto significa que se um rótulo é associado ao
primeiro byte do segmento \texttt{.text} ele estará associado ao endereço
$0x400000$.


\section{Entrega}

A entrega deste pacote deve ser feita de forma eletrônica em 
  \begin{quote}
    \texttt{<http://panda.ime.usp.br>}
  \end{quote}
até o dia 7 de dezembro.  Este prazo não pode ser prorrogado devido à
data limite de entrega de notas.

Quanto à divisão de grupos, será divulgado o processo de formação dos grupos
nas páginas do curso.

\pagestyle{empty}
\end{document}
