Esta série de tutoriais promete ser talvez uma das mais extensas mini-séries da história, rivalizada apenas pelo atraso do Volume IV d'A Arte da Programação de Computadores de Donald Knuth. Começando em 1988, a série teve uma pausa de 4 anos em 1990 quando as "preocupações deste mundo", me fizeram mudar as prioridades e interesses, e a necessidade de sobreviver fez com que parássemos no capÃtulo 14. Aqueles de vocês com muita paciência foram finalmente recompensados, no começo do ano passado, com o muito esperado capÃtulo 15. Nele eu comecei a colocar a série novamente no caminho, para que fosse mais fácil continuar até o objetivo final, que não só é prover-lhes entendimento suficiente das dificuldades no ramo da teoria dos compiladores, mas também as ferramentes, na forma de sub-rotinas e conceitos para que você fosse capaz de continuar por conta própria e se tornar proficiente o suficiente para construir seus próprios analisadores sintáticos e tradutores. Por causa desta longa pausa, eu decidi que era apropriado voltar e rever os conceitos que cobrimos até agora, e refazer parte do software, também. No passado, nós nunca nos preocupamos muito com o desenvolvimento de ferramentas com qualidade de produção... afinal de contas, eu estava tentando lhes ensinar (e aprender) conceitos, e não prática de produção. Para fazer isto, eu tentei lhe dar, não compiladores ou analisadores completos, mas apenas os fragmentos de código que ilustravam o ponto particular que estava sendo considerado no momento.
Eu ainda acho que esta é uma boa forma de aprender qualquer assunto; ninguém gosta de ter que fazer mudanças em programas de 100.000 linhas apenas para tentar uma idéia nova. Mas a idéia de tratar apenas de fragmentos de código, ao invés de programas completos, também tem seus pontos negativos pois parece que estamos reescrevendo o mesmo código toda vez. Apesar da repetição ser comprovadamente uma boa forma de aprender novas idéias, também é provado que o excesso de uma coisa boa é ruim. No momento em que eu completei o capÃtulo 14 eu achei que havia atingido o limite das minhas habilidades para tratar de múltiplos arquivos e múltiplas versões das mesmas funções do software. Quem sabe foi esta uma das razões de eu ter perdido o fôlego neste ponto.
Felizmente, podemos manter módulos separados para manter nosso programa principal pequeno e simples enquanto testamos coisas novas. Mas, uma vez que o código tenha sido escrito ele sempre estará lá, e adicioná-los aos nossos programas é indolor e transparente.
{{{96...128}}
A questão, realmente, é que: usando o mecanismo de módulos separados, podemos ter a vantagem e a conveniência de escrever programas pequenos para teste, aparentemente independentes, sem ter que constantemente reescrever as funções de suporte necessárias.
Usando este princÃpio, eu comecei no capÃtulo 15 a minimizar nossa tendência a reinventar a roda organizando o código em unidades separadas, cada uma contendo partes diferentes do compilador. Acabamos com as seguintes unidades:
- input: módulo de tratamento da entrada
- output: módulo de geração da saÃda
- errors: tratamento de erros
- scanner: rotinas do analisador léxico
- parser: a implementação da sintaxe da linguagem propriamente dita
- codegen: rotinas de geração de código assembly
Cada uma destas unidades possui uma função diferente, e mantém encapsuladas áreas especÃficas de funcionalidade. Por exemplo, as unidades de entrada e saÃda, como seus nomes já dizem, provêem o tratamento de e/s e o importante caracter "lookahead" sobre o qual se baseia nosso analisador preditivo.
As duas unidades com que mais vamos trabalhar, e as que representam a maior parte da personalidade do compilador, são a do analisador sintático e a de geração de código. Teoricamente, o analisador sintático deveria encapsular todos os aspectos do compilador que dependem da sintaxe da linguagem compilada (contudo, como vimos da ultima vez, parte desta sintaxe acaba indo no próprio analisador léxico). De forma similar, a únidade de geração de código contém todo o código dependente da máquina-alvo. Neste capÃtulo, vamos continuar com o desenvolvimento das funções nestas duas unidades tão importantes.
Voltando ao Clássico?
---------------------
Antes de continuarmos, contudo, eu acho que eu deveria esclarecer a relação entre, a funcionalidade destas unidades. Aqueles de vocês que estão familiarizados com a teoria de compiladores conforme ensinado nas universidades, é claro, reconhecem os nomes, analisador léxico (scanner), analisador sintático (parser), e gerador de código (code generator), os quais são componentes da implementação clássica dos compiladores. Vocês devem estar pensando que eu abandonei o meu compromisso de manter a filosofia KISS, e preferi usar uma abordagem mais convencional. Uma observação mais atenta, porém, deve convecê-los de que, embora os nomes sejam similares, as funcionalidades são bem diferentes.
Juntas, as implementações clássicas dos analisadores léxico e sintático caracterizam o "front-end" ou "vanguarda" e o gerador de código, o "back-end" ou "retaguarda" de um compilador. As rotinas de vanguarda processam a parte dependente da linguagem, relacionadas à sintaxe, enquanto o gerador de código, ou retaguarda, trata da parte dependente da máquina-alvo do problema. Em compiladores clássicos, as duas partes se comunicam através de um arquivo de instruções escritos em uma linguagem intermediária.
Tipicamente, um analisador léxico clássico é um simples procedimento, operando como um coprocedimento com o analisador sintático. Ele "tokeniza" o arquivo fonte, lendo-o caracter por caracter, reconhecendo os elementos da linguagem, e traduzindo-os em tokens, e depois passando-os para o analisador sintático. Você pode pensar no analisador sintático como uma máquina abstrata, executando os códigos de operação, que são os tokens. De forma similar, o analisador gera códigos de operação de uma segunda máquina abstrata, que é alimentada pela linguagem intermediária. Tipicamente, o arquivo intermediário é gerado pelo analisador sintático, e lido pelo gerador de código.
Nossa organização é bem diferente. Nós não temos analisador léxico, no sentido clássico; nossa unidade "scanner", apesar de ter um nome similar, não é um simples procedimento ou coprocedimento, mas um conjunto de sub-rotinas separadas que são chamadas pelo analisador sintático conforme necessárias.
De forma similar, o gerador de código clássico, a retaguarda, é um tradutor por si só, lendo o arquivo-"fonte" na linguagem intermediátia, e emitindo um arquivo-objeto. Nosso gerador de código não funciona desta forma. Em nosso compilador, não há linguagem intermediária; cada construção na sintaxe da linguagem fonte é convertida em linguagem assembly conforme é reconhecida pelo analisador sintático. Assim como o módulo "scanner", o módulo "codegen" consiste de procedimentos individuais cada um chamado pelo analisador sintático conforme necessário.
Esta filosofia "codifique conforme necessário" pode não produzir o código mais eficiente do mundo -- por exemplo, ainda não construÃamos (ainda!) um lugar conveniente para que o otimizador faça sua mágica -- mas certamente simplifica o compilador, não simplifica?
E a observação me faz refletir, mais uma vez, em como fomos capazes de reduzir as funções do compilador em termos tão simples. Eu já fui bastante eloquente quanto a este assunto em capÃtulos anteriores, portanto não vou perder muito tempo com este ponto agora. No entanto, como um bom tempo passou desde as últimas seções, eu espero que você me garanta ao menos uma breve reflexão de como chegamos até aqui. Nós conseguimos isto aplicando diversos princÃpios que diversos criadores de compiladores comerciais raramente tiveram o prazer de usar. Estes são:
- A filosofia KISS: nunca fazer as coisas da forma mais difÃcil sem uma razão
- Codificação preguiçosa: "Nunca deixar para amanhã o que pode ser adiado para sempre" (com os créditos para P.J.Plauger)
- Ceticismo - Recusar teimosamente fazer algo apenas por ser a forma como sempre foi feito.
- Aceitação de código ineficiente
- Rejeição de limitações arbitrárias
Quando eu fiz uma revisão da história da construção de compiladores, eu aprendi que virtualmente todo compilador de produção na história sofreu de condições pré-impostas que influenciaram muito no projeto. O compilador original FORTRAN de John Backus e outros, precisavam competir com a linguagem assembly, e portanto deveriam produzir um código extremamente eficiente. Os compiladores IBM para os minicomputadores da década de 70 precisavam rodar com quantidades muito reduzidas de memória RAM -- reduzidas como 4k. O primeiro compilador Ada deveria compilar a si mesmo. Brinch Hansen declarou que seu compilador Pascal desenvolvido para o IBM PC deveria executar em uma máquina de 64k. Compiladores desenvolvidos em cursos de Ciência da Computação deveriam compilar a maior variedade possÃvel de linguagens, e portanto precisavam de analisadores LALR.
Em cada um destes casos, os requisitos pré-concebidos literalmente dominaram o projeto destes compiladores.
Um bom exemplo é o compilador de Brinch Hansen, descrito em seu excelente livro, "Brinch Hansen on Pascal Compilers". Apesar de seu compilador ser uma das mais limpas e não-obscuros implementações que eu já vi, aquela decisão, de compilar arquivos grandes em uma RAM limitade, dirigiu totalmente o projeto, e ele terminou com não somente um, mas vários arquivos intermediários, junto com as interfaces para ler e escrevê-los.
Em tempo, as estruturas resultantes destas decisões encontraram seus caminhos na ciência da computação como artigos de fé. Na opinião deste homem, já é hora de re-examinar o processo de um ponto de vista crÃtico. As condições, ambientes, e requerimentos que levaram à s arquiteturas clássicas não são os mesmos de hoje em dia. Não há razão para crer que a solução deveria ser a mesma.
Neste tutorial, nós seguimos a liderança dos pioneiros no mundo de compiladores pequenos para PCs como Leor Zolman, Ron Cain e James Hendrix, que não sabiam teoria de compiladores o suficiente para saber que eles "não conseguiriam fazer daquela forma". Nós temos resolvidamente evitado aceitar limitações arbitrárias, e feito o que quer que fosse mais fácil. Como resultado, acabamos construindo uma arquitetura que, embora bem diferente da clássica, faz bem seu trabalho de uma forma muito simples e descomplicada.
Eu vou terminar esta observação filosófica com uma observação da noção de uma linguagem intermediária. Embora eu tenha dito anteriormente que não temos uma em nosso compilador, isto não é exatamente verdadeiro; nós TEMOS uma, ou pelo menos estamos evoluindo uma, no sentido de que estamos definindo funçÕes de geração de código para que o analisador sintático as use. Em essência, cada chamada a uma rotina de geração de código pode ser encarada como uma instrução em uma linguagem intermediária. Se em algum momento nós acharmos necessário formalizar uma linguagem intermediária, esta é a forma de fazê-lo: emitir códigos no analisador sintático, cada um representando uma chamada a um dos procedimentos do gerador de código, e então processar cada código chamando estes procedimentos em um passo separado, implementado na retaguarda. Francamente, eu não acho que nós vamos encontrar uma necessidade real para esta abordagem, mas aà está a conexão, caso você deseja seguÃ-la, entre as abordagens clássica e a que estamos usando.
Expandindo o Analisador Sintático
---------------------------------
Apesar de ter prometido que, em algum lugar do capÃtulo 14, que nós nunca mais irÃamos ter que refazer cada função novamente, eu acabei começando a fazer isto outra vez no capÃtulo 15. A razão: a longa pausa entre os dois capÃtulos fez com que a revisão fosse justificada... para você e para mim. Mais importante do que isso, a decisão de coletar os procedimento em módulos (unidades), nos forçou a revisar tudo novamente, querendo ou não. E, finalmente e francamente, eu tive algumas idéias novas nos últimos quatro anos que garantiram uma nova olhada em alguns dos velhos amigos. Quando eu comecei esta série, eu francamente fiquei espantado, e ao mesmo tempo satisfeito, em saber quão simples as rotinas de análise podem ser. Mas desta vez, eu me surpreendi novamente, sendo capaz de fazê-las ainda mais simples.
Apesar de toda esta reescrita do módulo de análise, eu só consegui incluir uma parte no último capÃtulo. Por causa disto, nosso herósi, o analisador sintático, quando visto pela última vez, era apenas uma sombra de sua versão anterior, consistindo apenas de código suficiente para analisar e processar fatores consistindo de uma variável ou constante. O principal objetivo deste capÃtulo será ajudar o analisador a alcançar sua glória inicial. No processo, eu espero que você me acompanhe enquanto cobrimos um território que já foi tratado há muito tempo.
Em primeiro lugar, vamos tratar de um problema que já vimos anteriormente: nossa versão atual do procedimento "factor", conforme a deixamos no capÃtulo 15, não pode tratar de argumentos negativos. Para arrumar isto, vamos introduzir o procedimento "signedFactor":
/* analisa e traduz um fator com um sinal opcional */
void signedFactor()
{
char sign = look;
if (isAddOp(look))
nextChar();
factor();
if (sign == '-')
asmNegate();
}
Repare que este procedimento chama uma nova rotina de geração de código, "asmNegate":
/* inverte sinal de reg. prim. */
void asmNegate()
{
emit("NEG AX");
}
(Aqui, e em todo lugar nesta série, eu só vou lhe mostrar as novas rotinas. Eu espero que você as coloque no módulo apropriado, e eu tenho certeza de que você normalmente não terá problema em identificar. Não esqueça de adicionar o protótipo da função ao cabeçalho de cada módulo.)
No programa principal, simplesmente altere o procedimento chamado para "signedFactor" e faça um teste.
Sim, eu sei que o código não é muito eficiente. Se colocarmos um número, como -3, o código gerado será:
MOV AX, 3
NEG AX
o que é realmente estúpido. Podemos fazer melhor, é claro, simplesmente adicionando um sinal de menos à string passada para "loadConstant", mas isto adiciona algumas linhas de código a "signedFactor", e eu estou aplicando a filosofia KISS muito agressivamente aqui. Além disso, pra falar a verdade, eu acho que eu estou de forma subconsciente gostando de gerar código "realmente estúpido", para que eu tenha o prazer de vê-lo ficar dramaticamente melhor quando chegarmos aos métodos de otimização.
Creio que a maioria de vocês nunca ouviu falar de John Spray, então permitam-me apresentá-lo. John é da Nova Zelândia, e costumava ensinar ciência da computação em uma das universidades de lá. John escreveu um compilador para o processador Motorola 6809, baseado em uma fantástica linguagem que ele mesmo criou, parecida com Pascal, chamada "Whimsical". Mais tarde ele portou o compilador para o 68000, e por um tempo este foi o único compilador que eu possuia em meu sistema doméstico.
Por curiosidade, um dos meus testes padrão para qualquer novo compilador é ver como o programa trata de um programa nulo como:
program main;
begin
end.
Meu teste consiste em medir o tempo necessário para compilar e "linkar", e o tamanho do arquivo-objeto gerado. O _PERDEDOR_ indisputável no meu teste foi o compilador DEC C para o VAX, que levou 60 segundos para compilar, em um VAX 11/780, e gerou um código-objeto de 50K. O compilador de John é indisputável, único, futuro, e para sempre o rei no departamento de tamanho de código. Dado um programa nulo, Whimsical gerou precisamente dois bytes de código (é um processador 68000, lembre-se), implementando a única instrução,
RET
Fazendo o compilador gerar código para um arquivo de inclusão (uma expécie de módulo) ao invés de um programa independente, John conseguiu cortar o tamanho, de dois bytes para zero! É meio difÃcil ganhar de um arquivo-objeto vazio, você não acha?
Não é necessário dizer que, eu considero John uma espécie de especialista em otimização de código, e gosto do que ele tem para dizer: "A melhor forma de otimizar é não ter que otimizar nada. Ao invés disso produzir código de boa qualidade já da primeira vez." Palavras com as quais devemos conviver. Quando começarmos com otimização, vamos seguir o conselho de John, e nosso primeiro passo não será adicionar um otimizador "peephole" ou outro dispositivo do tipo depois-do-fato, mas sim melhorar a qualidade do código emitido antes da otimização. Portanto, tome nota a respeito de "signedFactor" como sendo um bom candidato para nossa primeira tentativa, e por enquanto vamos deixá-lo como está.
Termos e Expressões
-------------------
Eu estou certo de que você sabe o que vem em seguida: nós temos que, outra vez, criar o resto dos procedimentos que implementam a análise descendente-recursiva de uma expressão. Nós todos já conhecemos a hierarquia de procedimentos para expressões aritméticas:
expression
|
+---> term
|
+---> factor
Mas no momento vamos continuar fazendo as coisas uma de cada vez, e considerar expressões que só tem termos aditivas. O código para implementar expressões, incluindo um possÃvel termo sinalizado, é mostrado a seguir:
/* analisa e traduz uma expressão */
void expression()
{
signedFactor();
while (isAddOp(look)) {
switch (look) {
case '+':
add();
break;
case '-':
subtract();
break;
}
}
}
Este procedimento chama outros procedimento para processar as operações:
/* analisa e traduz uma operação de soma */
void add()
{
match('+');
asmPush();
factor();
asmPopAdd();
}
/* analisa e traduz uma operação de subtração */
void subtract()
{
match('-');
asmPush();
factor();
asmPopSub();
}
Os três procedimentos "asmPush", "asmPopAdd" e "asmPopSub" são novas rotinas de geração de código. Como o próprio nome implica, o procedimento "asmPush" gera código para colocar o registrador primário (AX, em nossa implementação) na pilha. "asmPopAdd" e "asmPopSub" removem o valor do topo da pilha, e adicionam, ou subtraem dele o registrador primário. O código é mostrado a seguir:
/* coloca registrador primário na pilha */
void asmPush()
{
emit("PUSH AX");
}
/* adiciona topo da pilha a reg. primário */
void asmPopAdd()
{
emit("POP BX");
emit("ADD AX, BX");
}
/* subtrari do topo da pilha o reg. primário */
void asmPopSub()
{
emit("POP BX");
emit("SUB AX, BX");
asmNegate();
}
Adicione estas rotinas aos módulos "parser" e "codegen", e mude o programa principal para chamar "expression". Voila!
O próximo passo, é claro, é adicionar capacidade para tratar de termos multiplicativos. Para isto, vamos adicionar um procedimento "term", e os procedimentos de geração de código "asmPopMul" e "asmPopDiv".
/* adiciona topo da pilha a reg. primário */
void asmPopMul()
{
emit("POP BX");
emit("IMUL BX");
}
/* subtrari do topo da pilha o reg. primário */
void asmPopDiv()
{
emit("POP BX");
emit("XCHG AX, BX");
emit("CWD");
emit("IDIV BX");
}
Eu admito que a rotina de divisão está um pouco "cheia", mas não há muita saÃda. Infelizmente os registradores acabam com os valores na ordem inversa, por isso é preciso invertê-los. Além disso precisamos fazer a extensão de sinal de AX (pois se o divisor é de 16-bits, BX, o dividendo deve ter 32-bits, DX:AX). Repare que estou usando a multiplicação e divisão com sinal. Estamos assumindo que nossas variáveis serão inteiros de 16-bits. Esta decisão vai voltar a nos assombrar mais tarde, quando começarmos a tratar de múltiplos tipos de dados, conversão de tipos, etc.
Nosso procedimentos "term" é virtualmente um clone de "expression" e se parece com isto:
/* analisa e traduz um termo */
void term()
{
factor();
while (isMulOp(look)) {
switch (look) {
case '*':
multiply();
break;
case '/':
divide();
break;
}
}
}
Nosso próximo passo é alterar alguns nomes. "signedFactor" agora torna-se "signedTerm", e as atuais chamadas a "factor", serão alteradas para "term":
/* analisa e traduz um termo com um sinal opcional */
void signedTerm()
{
char sign = look;
if (isAddOp(look))
nextChar();
term();
if (sign == '-')
asmNegate();
}
/* analisa e traduz uma expressão */
void expression()
{
signedTerm();
while (isAddOp(look)) {
switch (look) {
case '+':
add();
break;
case '-':
subtract();
break;
}
}
}
Se não me falha a memória, antes nós tinhamos tanto "signedFactor" quanto "signedTerm". Eu tinha razões para manter as duas daquela vez... tinha a ver com o tratamento da álgebra booleana e, em particular, a função booleana "NOT". Mas certamente, para operações aritméticas, a duplicação não é necessária. Em uma expressão como:
-x*y
é aparente que o sinal se aplica ao termo inteiro, x*y, e não apenas ao fator "x", e é desta forma que a expressão é codificada.
Teste este novo código. Agora você deve ser capaz de tratar das quatro operações aritméticas.
Nossa última tarefa, com relação à s expressões, é modificar o procedimento "factor" para permitir expressões entre parênteses. Usando uma chamada recursiva a "expression", é possÃvel reduzir o código necessário a virtualmente nada. Algumas linhas de código adicionadas a "factor" fazem o trabalho:
/* analisa e traduz um fator matemático */
void factor()
{
char name[MAXNAME+1], num[MAXNUM+1];
if (look == '(') {
match('(');
expression();
match(')');
} else if (isdigit(look)) {
getNum(num);
asmLoadConstant(num);
} else if (isalpha(look)) {
getName(name);
asmLoadVariable(name);
} else
error("Unrecognized character: '%c'", look);
}
Neste ponto, seu "compilador" deve estar apto a produzir qualquer expressão válida que você tentar. Melhor ainda, ele deve rejeitar as inválidas!
Atribuição
----------
Já que chegamos até aqui, podemos criar também o código para comandos de atribuição. Este código só precisa lembrar do nome da variável onde deve ser armazenado o resultado de uma expressão, chamar "expression", e então armazenar o valor. O procedimento é o seguinte:
/* analisa e traduz um comando de atribuição */
void assignment()
{
char name[MAXNAME+1];
getName(name);
match('=');
expression();
asmStoreVariable(name);
}
A atribuição precisa de mais uma rotina de geração de código:
/* armazena valor do registrador primário em variável */
void asmStoreVariable(char *name)
{
emit("MOV [%s], AX", name);
}
Agora, altere a chamada no programa principal para "assignment", e você deverá ver um comando completo de atribuição sendo processado corretamente. Legal, não? E indolor, também.
No passado, eu tentei mostrar as relações BNF para definir a sintaxe que estávamos desenvolvendo. Eu não fiz isto ainda, e já está na hora de fazê-lo. Aà está:
<factor> ::= <variable> | <constant> | '(' <expression> ')'
<signed_term> ::= [<addop>] <term>
<term> ::= <factor> (<mulop> <factor>)*
<expression> ::= <signed_term> (<addop> <term>)*
<assignment> ::= <variable> '=' <expression>
Expressões Booleanas
--------------------
O próximo passo, como já vimos diversas vezes antes, é adicionar álgebra booleana. No passado, este passo praticamente dobrou a quantidade de código que tivemos que escrever. Conforme eu repassava isto várias vezes mentalmente, eu me encontrei divergindo mais e mais do que fizemos nos capÃtulos anteriores. Para refrescar a memória, eu notei que Pascal trata os operadores booleanos de forma quase idêntica ao tratamento dos aritméticos. Um "AND" booleano tem o mesmo nÃvel de precedência da multiplicação e o "OR" o mesmo da adição. C, por outro lado, os coloca em nÃveis diferentes de precedência, e como já foi dito, são 17 nÃveis! Em nossos trabalhos anteriores, eu preferi algo intermediário, com sete nÃveis. Como resultado, acabamos com as chamadas expressões booleanas, paralelas à s expressões aritméticas na maioria dos detalhes, mas em um nÃvel de precedência diferente. Tudo isto, veio à tona, por que eu não gosto de colocar parênteses em expressões booleanas em comandos como:
IF (c >= 'A') AND (c <= 'Z') THEN ...
Em retrospecto, isto não parece uma razão muito boa para adicionar diversas camadas de complexidade ao compilador. Além disso, eu não estava sequer certo se poderia ou não evitar os parênteses.
Vamos começar tudo outra vez, usando uma abordagem mais próxima do Pascal, tratando os operadores booleaos com o mesmo nÃvel de precedência dos aritméticos. Vamos ver até onde chegamos. Se parecer algo muito estranho podemos voltar à abordagem anterior.
Vamos começar modificando "isAddOp" para incluir os dois operadores extra: "|" para OU e "~" para OU-exclusivo:
/* reconhece um operador aditivo */
int isAddOp(char c)
{
return (c == '+' || c == '-' || c == '|' || c == '~');
}
Em seguida, temos que incluir a análise destas operações em "expression":
/* analisa e traduz uma expressão */
void expression()
{
signedTerm();
while (isAddOp(look)) {
switch (look) {
case '+':
add();
break;
case '-':
subtract();
break;
case '|':
boolOr();
break;
case '~':
boolXor();
break;
}
}
}
Em seguida, as rotinas "boolOr" e "boolXor":
/* analisa e traduz uma operação OU booleana */
void boolOr()
{
match('|');
asmPush();
term();
asmPopOr();
}
/* analisa e traduz uma operação OU-exclusivo booleana */
void boolXor()
{
match('~');
asmPush();
term();
asmPopXor();
}
E, finalmente, as novas rotinas de geração de código:
/* aplica OU com topo da pilha a reg. primário */
void asmPopOr()
{
emit("POP BX");
emit("OR AX, BX");
}
/* aplica OU-exclusivo com topo da pilha a reg. primário */
void asmPopXor()
{
emit("POP BX");
emit("XOR AX, BX");
}
Agora, vamos testar o tradutor (talvez você queira trocar a chamada no programa principal para "expression", apenas para evitar ter que digitar "x=" para uma atribuição o tempo todo).
Até aqui tudo bem. O analisador trata corretamente de expressões da forma:
x|y~z
Infelizmente, ele também não faz nada para nos proteger de misturar algebra aritmética e booleana. Ele simplesmente gera o código para:
(a+b)*(c~d)
Nós falamos um pouco sobre isto, no passado. Em geral, as regras para operações que são válidas ou não não podem ser reforçadas pelo analisador sintático em si, por que isto não faz parte da sintaxe da linguagem, mas da semântica. Um compilador que não permite expressões misturadas deste tipo deve reconhecer que "c" e "d" são variáveis booleanas, ao invés de numéricas, e deve avisar sobre a multiplicação delas no próximo passo. Mas este "policiamente" não pode ser feito pelo analisador; deve ser tratado em algum outro lugar entre o analisador e o gerador de código. Nós não estamos em condição de forçar tais regras ainda, pois ainda nem sequer temos uma forma de declarar tipos, ou uma tabela de sÃmbolos para armazenar os tipos declarados. Então, pelo que temos feito até o momento, o analisador está fazendo precisamente o que deveria.
De qualquer forma, estamos certos de que NÃO queremos operações entre tipos misturados? Tomamos a decisão algum tempo atrás (ou, pelo menos, eu tomei), de adotar o valor 0000 para o "falso" booleano, e -1, ou FFFFh, como "verdadeiro". O bom desta decisão é que as operações bit-a-bit funcionam exatamente da mesma forma que as lógicas. Em outras palavras, quando fazemos uma operação em uma variável lógica, fazemos nela inteira. Isto significa que não é preciso diferenciar operações lógicas e bit-a-bit, como é feito em C com os operadores & e &&, e | e ||. Reduzir o número de operadores pela metade certamente não é tão ruim assim.
Do ponto de vista do armazenamento de dados, é claro que o computador e o compilador não dão a menor importância se o número FFFFh representa VERDADEIRO, ou o valor numérico -1. DeverÃamos nós? Eu acho que não. Eu posso pensar em muitos exemplos (embora alguns não sejam considerados bons exemplos de código claro) onde a habilidade de misturar tipos se torna útil. Por exemplo, a função delta de Dirac, pode ser codificada em uma única linha:
-(x=0)
Ou a função de valor absoluto (DEFINITAMENTE estranha!):
x*(1+2*(x<0))
Por favor, entenda. Eu não estou tentando dizer que este tipo de programação é um estilo de vida. Eu certamente escreveria estas funções em formas mais legÃveis, usando IFs, apenas para manter evitar confundir programadores que venham a manter os programas. Porém, uma questão moral surge: nós temos o direito de IMPOR nossas idéias de boa prática de programação ao programador, escrevendo a linguagem de forma que ele não tenha saÃda? Foi isto que Niklaus Wirth fez, em muitos partes de Pascal, e Pascal foi muito criticado por isto -- por não ser tão "permissÃvel" quanto C.
Um paralelo interessante no exemplo do projeto do processador Motorola 68000. Por exemplo, é possÃvel ler uma variável a partir de seu endereço:
MOVE X, D0 (onde X é o nome da variável e D0 é o registrador primário)
(repare que a ordem dos operandos é Origem->Destino e não Destino<-Origem)
Porém, não é possÃvel fazer o inverso, isto é, é preciso carregar em um registrador o endereço de X.
LEA X(PC), A0
MOVE D0, (A0)
O mesmo vale para endereçamente relativo ao contador de programa:
MOVE X(PC), D0 (válido)
MOVE D0, X(PC) (inválido)
Quando você começa a se perguntar como um comportamento não-ortogonal surgiu, você descobre que alguém na Motorola tinha algumas teorias a respeito de como o software deveria ser escrito. Especificamente, neste caso, eles decidiram que código auto-modificável, que pode ser implementado usando escritas relativas ao contador de programa (PC) é Algo Ruim. Portanto, eles projetaram o processador para proibir isto. Infelizmente, no processo eles também proibiram TODAS as instruções de escrita no formato mostrado acima, não importa quão benignas. Repare que isto não foi algo feito por padrão. Trabalho extra foi adicionado ao projeto, e portas extras foram adicionadas, para destruir a ortogonalidade natural do conjunto de instruções.
Uma das lições que eu aprendi com a vida: se você tem duas escolhas, e não consegue decidir qual tomar, algumas vezes a melhor coisa a fazer é nada. Por que adicionar portas lógicas extras a um processador para forçar algumas idéias estranhas a respeito de boa prática de programação? Deixe as instruções lá, e deixe que os programadores discutam o que é boa prática de programação. De forma similar, por que deverÃamos adicionar código extra ao nosso compilador, para testar e prevenir condições que o usuário preferiria fazer de qualquer jeito? Eu prefiro manter o compilador simples, e deixar que os especialistas do software discutam se a prática deve ser usada ou não.
Tudo isto serve como uma explicação para a minha decisão a respeito de prevenir ou não aritmética de tipos misturados: eu não vou! Para uma linguagem cujo objetivo é programação de sistemas, quanto menos regras, melhor. Se você não concordar, e preferir testar tais condições, podemos fazê-lo uma vez que tenhamos uma tabela de sÃmbolos.
"AND" booleano
--------------
Com esta discussão filosófica fora do nosso caminho, podemos continuar com o operador AND, que entra no procedimento "term". A esta altura, você provavelmente já consegue fazer isto sem mim, mas aqui está o código de qualquer forma:
No analisador léxico:
/* reconhece um operador multiplicativo */
int isMulOp(char c)
{
return (c == '*' || c == '/' || c == '&');
}
No analisador sintático:
/* analisa e traduz um termo */
void term()
{
factor();
while (isMulOp(look)) {
switch (look) {
case '*':
multiply();
break;
case '/':
divide();
break;
case '&':
boolAnd();
break;
}
}
}
/* analisa e traduz uma operação AND */
void boolAnd()
{
match('&');
asmPush();
factor();
asmPopAnd();
}
E no gerador de código:
/* aplica AND com topo da pilha a reg. primário */
void asmPopAnd()
{
emit("POP BX");
emit("AND AX, BX");
}
Sem analisador deve a esta altura estar apto a processar quase todo tipo de expressões lógicas, e expressões misturadas também.
Por que não "todo tipo de expressões lógicas"? Por que, até aqui, não tratamos do operador lógico NOT, e é aà que as coisas começam a fica complicadas. O operador lógico NOT parece, numa primeira olhada, ser idêntico em comportamento ao menos unário. Portanto, minha primeira idéia foi permitir que o operador OU-exclusivo "~", fizesse o papel do NOT, quando operador unário. Isto não funcionou. Na minha primeira tentativa, o procedimento "signedTerm" simplesmente ignorou o "~", pois o caracter passou o teste de "isAddOp", mas "signedTerm" ignora qualquer coisa exceto "-". Seria fácil adicionar outro teste a "signedTerm", mas isto ainda não resolveria o problema, pois, note que "expression" só aceita um termo com sinal para o PRIMEIRO argumento.
Matematicamente, uma expressão como:
-a * -b
não faz sentido, e o analisador deve avisar sobre o erro. Mas a mesma expressão, usando um NOT faz total sentido:
NOT a AND NOT b
No caso destes operadores unários, escolher fazê-los agir da mesma forma, parece ser uma medida artificial, sacrificando o comportamento razoável no altar da facilidade de implementação. Embora eu seja devoto de manter a implementação tão simples quanto possÃvel, eu não acho que devemos fazer isto ao custo da perda do senso racional. Remendos como este nos deslocam do foco principal: o operador lógico NOT não é do mesmo tipo do menos unário. Considere o OU-exclusivo, que é escrito mais naturalmente como:
a~b ::= (a AND NOT b) OR (NOT a AND b)
Se permitirmos que NOT se aplique ao termo inteiro, o último termo entre parênteses seria interpretado como:
NOT(a AND b)
que não é a mesma coisa. Portanto está claro que o NOT lógico deve ser considerado conectado ao FATOR, não ao termo.
A idéia de sobrecarregar (overload) o operador "~" também não faz sentido do ponto de vista matemárico. A implicação do menos unário é equivalente a uma subtração de zero:
-x <=> 0-x
De fato, em uma das minhas versões mais simplistas de "expression", eu reagi a um operador aditivo simplesmente pré-carregando um zero, e então processado o operador como se ele fosse um operador binário. Mas um NOT não é equivalente a um OU-exclusivo com zero... isto só daria como resultado o próprio número. Ao invés disto, seria um OU-exclusivo com FFFFh, ou -1.
Em resumo, o paralelo entre o NOT e o menos unário é falso. NOT modifica o fator, não o termo, e não está relacionando nem ao menos nem ao OU-exclusivo. Portanto, ele merece um sÃmbolo próprio. Que sÃmbolo seria melhor que o mais óbvio de todos, o caracter "!" da linguagem C? Usando as regras da forma como achamos que o NOT deveria ser, poderÃamos codificar o OU-exclusivo (se é que um dia vamos precisar fazer isto), na forma natural:
a & !b | !a & b
Repare que não há necessidade de parênteses -- os nÃveis de precedência que escolhemos automaticamente tomam conta das coisas.
Se você tem acompanhado os nÃveis de precedência, esta definição coloca o "!" no topo da pilha. Os nÃveis se tornam:
1. !
2. - (unário)
3. * / &
4. + - | ~
Olhando para esta lista, certamente não é difÃcil ver porque terÃamos problemas usando "~" como o sÃmbolo para NOT!
Então, como implementar as regras? Da mesma forma que fizemos com "signedTerm", mas no nÃvel do fator. Vamos definir um procedimento "notFactor":
/* analisa e traduz um fator com NOT opcional */
void notFactor()
{
if (look == '!') {
match('!');
factor();
asmNot();
} else
factor();
}
Coloque uma chamada a esta rotina em todos os lugares onde estava "factor" era chamada. Note a nova rotina de geração de código:
/* aplica NOT a reg. primário */
void asmNot()
{
emit("NOT AX");
}
Teste isto agora, com alguns casos simples. Teste também o nosso exemplo do OU-exclusivo:
a&!b|!a&b
Você deve obter o código (sem os comentários, é claro):
MOV AX, [A] ;carrega A
PUSH AX ;coloca na pilha
MOV AX, [B] ;carrega B
NOT AX ;NOT b
POP BX ;pega A da pilha
AND AX, BX ;NOT b AND a
PUSH AX ;coloca resultado na pilha
MOV AX, [A] ;carrega A
NOT AX ;NOT a
PUSH AX ;coloca na pilha
MOV AX, [B] ;carrega B
POP BX ;pega NOT a da pilha
AND AX, BX ;resultado = b AND NOT a
POP BX ;pega resultado anterior (NOT b AND a)
OR AX, BX ;resultado OR resultado anterior
Isto é precisamente o que gostarÃamos de obter. Portanto, pelo menos para operadores lógicos e aritméticos, nossa nova sintaxe e nÃveis de precedência estão bons. Mesmo uma expressão peculiar, mas válida, como:
~x
faz sentido. "signedTerm" ignora o "~" inicial, como deveria, já que a expressão é equivalente a:
0~x
que é a mesma coisa que "x".
Se olharmos na BNF que criamos, vamos descobrir que nossa algebra booleana adiciona apenas uma linha extra:
<not_factor> ::= [!] <factor>
<factor> ::= <variable> | <constant> | '(' <expression> ')'
<signed_term> ::= [<addop>] <term>
<term> ::= <not_factor> (<mulop> <not_factor>)*
<expression> ::= <signed_term> (<addop> <term>)*
<assignment> ::= <variable> '=' <expression>
Esta é uma grande melhoria em relação à s tentativas passadas. Nossa sorte vai continuar quando tratarmos de operadores relacionais? Nós vamos descobrir em breve, mas isto terá que esperar pelo próximo capÃtulo. Chegamos num bom ponto de parada por enquanto, e estou ansioso para que este capÃtulo chegue à s suas mãos logo. Já se passou um ano desde o capÃtulo 15. Eu devo admitir que parte destes capÃtulos atuais estiveram prontos por muito tomepo, com a exceção dos operadores relacionais. Mas a informação não tem valor algum, enquanto permanecer no meu disco rÃgido, e segurá-la até que os operadores relacionais estivessem prontos iria atrasar demais as coisas. Está na hora de liberá-la para que você possa tirar algum valor dela. Além disso, há uma série de questões filosóficas associadas aos operadores relacionais, também, e eu gostaria de deixá-las para um capÃtulo posterior, onde eu possa fazer justiça a elas.
Divita-se com o novo analisador lógico e aritmético, e quem sabe em breve estaremos tratando dos operadores relacionais.
Comments (0)
You don't have permission to comment on this page.