Departamento de Ciência da Computação - IME - USP
Depois de fazer o EP3 e EP4 é esperado que todos passem a compreender melhor o significado (semântica) de expressões em C como:
Em particular, a semântica de expressões comoif ((x = stackPop()) != '#') ... a = b = c = 5; if (a < b < c) . . . while (!achou) ...
é diferente em Python e em C. Além disso, expressões comoa < b < c < d
que não são aceitas pelo Python, são muito utilizadas em C. Nessas, e em outras situações, a semântica adotada neste EP é a da linguagem C, apesar da sintaxe (e semântica) utilizada para cada operador ser a do Python.a = (b = 2 * (c = 2))
Este EP é uma adaptação feita pelo Professor José Coelho de Pina do EP4 de MAC0122 em 2012 de autoria do professor Carlos Hitoshi Morimoto
Neste EP você implementará um interpretador de expressões em notação infixa que, como em um programa, também pode conter variáveis. De maneira semelhante ao EP3, você escreverá um programa que lê de um arquivo ou de um prompt uma sequência de expressões e calcula e imprime o resultado de cada uma. A diferença agora é que as expressões são mais semelhantes àquelas encontradas em linguagens de programação como C. As expressões serão em notação infixa e poderão conter variáveis. Como em um programa, variáveis poderão ser inicializadas por meio de atribuições e reutilizadas em expressões futuras.
Cada expressão pode conter variáveis, números, abre e fecha parênteses e os seguintes símbolos correspondentes a um operador de atribuição, 6 operadores relacionais, 8 operadores aritméticos e 3 operadores lógicos:
| operação | símbolo |
|---|---|
| atribuição | = |
| igual | == |
| diferente | != |
| maior ou igual | >= |
| menor ou igual | <= |
| maior | > |
| menor | < |
| exponenciação | ** |
| resto de divisão | % |
| multiplicação | * |
| divisão | / |
| divisão inteira | // |
| adição | + |
| subtração | - |
| menos unário | _ |
| e lógico | and |
| ou lógico | or |
| negação | not |
Como no EP3 o programa pitao poderá ser executado no modo interativo (opção "-i") ou no modo script (opção "-s").
O novo pitao deve ler uma sequência de linhas (strings), independentemente do modo selecionado.
O programa pitao, quando invocado com a opção "-h" (help) mostra como deve ser utilizado. Nos exemplos a seguir de execução do programa, texto em vermelho indica algo digitado pelo usuário.
prompt> ./pitao -h ./pitao: Uso prompt> ./pitao [-h] [-i | -sNote que o EP4 tem duas opções novas em relação ao EP3, as opções "-e" e "-t" que são descritas mais adiante.] [-l] [-v] [-p] [-e] [-t] -h = mostra como usar o programa e abandona o programa -i = executa em modo (i)nterativo -s<nome-script> = calcula as expressões no arquivo <nome-script> -l = mostra fila de itens (l)exicos -v = mostra fila de (v)alores -p = mostra a (p)ilha de execucao apos cada operacao -e = mostra a (e)xpressao na notacao posfixa (EP4) -t = mostra a (t)abela de simbolos (EP4)
prompt> ./pitao -i MAC0121 2019 - EP4 Pitao (Oct 25 2019, 12:09:28) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X >>> 2 **8 # 2 elevado a 8 256 >>> 2 **_ 1 # 2 elevado a -1 0.5 >>> 2 + 3 *4 14 >>> 2 ** 2 ** 3 # o mesmo que 2 elevado a (2 elevado a 3) 256Como agora as expressões estão na notação infixa, para alterar a ordem em que as operações são executadas devemos utilizar um par de abre e fecha parênteses.
>>> (2 + 3) * 4 20 >>> (2 + 2) * 4 ** 0.5 # 4 elevado a 0.5 e 2 8 >>> ((2 + 2) * 4) ** 0.5 # raiz quadrada de 8 4 >>> (2 ** 2) ** 3 # o mesmo que 4 elevado a 3 64Além disso, as expressões podem envolver variáveis que podem armazenar valores que podem ser reutilizados. Como em Python, para criar uma variável utilizamos o operador "=" de atribuição.
>>> a = 5 5 >>> a # o valor da expressao com uma variavel e o seu conteudo 5 >>> b = a + 1 6 >>> c = a + b 11 >>> c 11 >>> prova1 = 6 6 >>> prova2 = 7 7 >>> media = (prova1 + 2*prova2)/3 6.66667 >>> media 6.66667As expressões podem ainda conter operadores relacionais, aritméticos, lógicos e atribuições múltiplas, como em C.
>>> ep1 = 5 5 >>> ep2 = 2.5 2.5 >>> ep3 = 6 6 >>> mep = (ep1 + 2*ep2 + 3*ep3)/6 4.66667 >>> p1 = 5 5 >>> p2 = 6 6 >>> mp = (p1 + 2* p2)/3 5.66667 >>> aprovado = mp >= 5 and mep >= 5 0 >>> i = j = k = 0 0 >>> i 0 >>> j 0 >>> k 0
O programa transforma cada expressão em notação infixa lida em uma expressão em notação posfixa equivalente. O programa pitao pode imprimir essa expressão em notação posfixa, para isto basta ser executado com a opção "-e".
prompt> ./pitao -e MAC0121 2019 - EP4 Pitao (Oct 25 2019, 12:09:28) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X >>> a = 1 Expressao posfixa: a 1 = 1 >>> b = 2 Expressao posfixa: b 2 = 2 >>> c = (a + 1) * b ** 0.5 Expressao posfixa: c a 1 + b 0.5 ** * = 2.82843 >>> a = (b = c - 0.828443) * 2 + a Expressao posfixa: a b c 0.828443 - = 2 * a + = 4.99997 >>> a = 1 Expressao posfixa: a 1 = 1 >>> b = 2 Expressao posfixa: b 2 = 2 >>> b = b + a Expressao posfixa: b b a + = 3 >>> bool = b < 3 Expressao posfixa: bool b 3 < = 0 >>> bool Expressao posfixa: bool 0
Uma tabela de símbolos (symbol table) é uma estrutura de dados utilizada por interpretadores e compiladores para manter informações sobre cada identificador tais como o seu tipo, a posição em que está armazenado e outras informações relevantes.
Em geral, uma tabela de símbolos é uma estrutura de dados que representa objetos ou itens, cada um dotado de uma chave (key). Essa estrutura deve ser capaz de realizar duas operações básicas: inserir (= insert = enter) um novo item e buscar (= search = lookup ) e retornar um item que tenha uma dada chave. Tabelas de símbolos também são chamadas de dicionários (dictionary) em analogia ao sistema bem conhecido de armazenar palavras (chaves) e seus significados (itens). Algumas linguagens de programação, como Python, possuem dicionários como um tipo nativo:
Python 3.7.4 (default, Jul 9 2019, 18:15:00)
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> estoque = { 'abacaxis': 430, 'peras': 238, 'bananas': 312, 'laranjas': 562} # chave:item
>>> type(estoque)
<type 'dict'>
>>> print(estoque['peras'])
238
>>> for fruta in estoque:
... print("Temos", estoque[fruta], fruta)
...
('Temos', 562, 'laranjas')
('Temos', 238, 'peras')
('Temos', 312, 'bananas')
('Temos', 430, 'abacaxis')
A propósito, algumas linguagens também possuem pilhas e filas como tipo nativos.
Por exemplo, vejam o que diz a página
Data Structure.O programa pitao deverá armazenar informações sobre as variáveis em uma tabela de símbolos. Se invocarmos pitao com a opção "-t", o valor de cada variável é mostrado após a interpretação de cada expressão.
prompt> ./pitao -t MAC0121 2019 - EP4 Pitao (Oct 25 2019, 12:09:28) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X >>> (2 + 6) * 8 **_ 1 1 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . tabela vazia. >>> soma = 0 0 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'soma': 0 >>> prova1 = 7 7 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'prova1': 7 'soma': 0 >>> prova2 = 6.5 6.5 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'prova2': 6.5 'prova1': 7 'soma': 0 >>> prova3 = 4.5 4.5 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'prova3': 4.5 'prova2': 6.5 'prova1': 7 'soma': 0 >>> soma = prova1 + prova2 + prova3 18 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'prova3': 4.5 'prova2': 6.5 'prova1': 7 'soma': 18 >>> mediaProva = soma/3 6 ========================== Tabela de simbolos 'nome': valor . . . . . . . . . . . . . . . 'mediaProva': 6 'prova3': 4.5 'prova2': 6.5 'prova1': 7 'soma': 18
Novos arquivos categorias.h, lexer.h, lexer.c... deverão ser copiados do esqueleto. Trechos de código que você escreveu para o EP3 deverão ser copiados para os arquivos do novo esqueleto. Alguns desses trechos de códigos deverão ser adaptados.
O programa pitao lê linhas com expressões de um arquivo dado ou interativamente a partir de um shell. Cada linha desse arquivo possui uma expressão infixa supostamente correta. A função main() do módulo main.c mostra um passo a passo no processo da interpretação de cada expressão. As linhas são percorridas e para cada linha pitao:
Aqui estão listados os protótipos das funções fornecidas ou parcialmente fornecidas e que você utilizará em algum dos trechos de código que deverá escrever. O comportamento das funções está descrito nos comentários que precedem as funções nos arquivos do esqueleto.
No módulo lexer.c temos a função
Copiado de lexer.h:que já foi adaptada para funcionar no EP4.CelObjeto * crieFilaItens (char linha[]);
No módulo util.c temos as funções
Copiado de util.h:que estão completamente escritas.void * mallocSafe (size_t nbytes); String getLine (FILE *infile);
No módulo main.c temos as funções
Copiado de main.c:que deverão ser adaptadas para este EP4.static void mostreUso (char *nomePrograma); int main(int argc, char *argv[]);
Aqui estão listados os protótipos das funções que você deverá
escrever. Algumas funções você já fez para o EP3 e deverão ser
simplesmente copiadas para o EP4.
Outras funções que você fez para o EP3 deverão ser adaptadas para o novo pitao.
Já outras funções são totalmente novas e deverão ser completamente escritas para o EP4. O
comportamento das funções está descrito nos comentários que precedem as
funções nos arquivos do esqueleto ou ainda no
meio da função, como no caso das funções main() e
mostreUso() do módulo main.c.
Você (sempre!) pode
escrever mais funções auxiliares.
Em um novo módulo, o posfixa.c temos a função
Copiado de posfixa.h:que recebe uma expressão em notação infixa representada através de uma fila iniInfixa e retorna a expressão correspondente em notação posfixa. A expressão retornada também deve ser representada através de uma fila. Ambas as filas deverão ser implementadas através listas encadeadas com cabeça.CelObjeto * infixaParaPosfixa (CelObjeto *iniInfixa);
Em um outro novo módulo, o st.c, deverão ser implementadas todas as funções que manipulam a tabela de símbolos. A interface para a tabela de símbolos é composta pelas funções
Copiado de st.h:Além dessas funções, o módulo st.c contém a função auxiliarvoid initST(); CelObjeto * getValorST(char *nomeVar); void setValorST(char *nomeVar, CelObjeto *pValor); void showST(); void freeST();
Copiado de st.c:que também deverá ser implementada. A tabela de símbolos deverá ser implementada através de uma lista encadeada com cabeça (vixe, mais uma. . .) em que cada célula é do tipo CelST. O tipo CelST é declarado em st.hstatic CelST *static CelST * endVarST(char *nomeVar);
No módulo objetos.c
Copiado de objetos.h:As funções mostreObjeto() e mostreListaObjetos() deverão ser adaptada para imprimir a expressão posfixa. A função freeObjeto() deverá ser adaptada para dar free em uma CelObjeto que representa uma variável (categoria ID). Já as funções mostreValor(), freeObjeto() e freeListaObjetos() são as mesmas que foram escritas para o EP3.void freeObjeto(CelObjeto *pObj); void freeListaObjetos(CelObjeto *iniLista); void mostreValor(CelObjeto *pValor); void mostreObjeto(CelObjeto *pObj, int tipoLista); void mostreListaObjetos(CelObjeto *iniLista, int tipoLista);
No módulo eval.c
Copiado de eval.h:a função itensParaValores() talvez tenha que ser adaptada para tratar o operador de atribuição =. Nada precisa ser feito a respeito de abre e fecha parênteses. No entanto, a função eval() deverá ser adaptada para tratar o operador de atribuição e variáveis. O tratamento das variáveis será feito através das funções que estão na interface para a tabela de símbolos.void itensParaValores (CelObjeto *iniFila); CelObjeto * eval(CelObjeto *iniPosfixa, Bool mostrePilhaExecucao);
Estão descritos aqui alguns aspectos sobre as implementação. Talvez esta descrição seja meio que redundante se levamos em consideração o que já foi descrito e as especificações nos arquivos do esqueleto.
O programa utilizará uma tabela de símbolos para armazenar informações sobre as variáveis. Essa tabela será representada através de uma lista ligada com cabeça em que toda célula é do tipo CelST
Copiado de st.h:O campo nomeVar é um ponteiro para o string com o nome da variável. O campo tipoVar indica o tipo da variável, que nesse EP é sempre FLOAT. Neste EP, como as variaveis são do tipo FLOAT, um double, que representa o valor da variável, é armazenado no campo valorVar./*----------------------------------------------------------*/ /* estrutura basica da tabela de simbolos */ typedef struct celST CelST; struct celST { /* ponteiro para o nome da variavel */ String nomeVar; /* tipo da variavel (neste EP e' sempre FLOAT) */ Categoria tipoVar; /* valor da variavel (neste EP e' sempre um double) */ Valor valorVar; /* proxima celula da tabela de simbolos */ CelST *proxVar; };
Cada linha do arquivo de entrada contém uma expressão infixa correta formada por números, variáveis e por operadores. Após a leitura de cada linha contendo uma expressão infixa, o programa pitao produz uma fila com os itens léxicos que formam a expressão na linha. Isto é feito pela função crieFilaItens() do módulo lexer.c. Em seguida, essa fila é tratada pela função itensParaValores() do módulo eval.c. Em seguida essa fila será convertida em uma fila que representa a expressão correspondente em notação posfixa. Essa conversão deve ser feita pela função
Copiado de posfixa.h:do módulo posfixa.c. Essa função recebe a fila contendo a expressão infixa e retorna a fila com a expressão correspondente na notação posfixa. Esta função é uma adaptação da função de mesmo nome dessa página.CelObjeto * infixaParaPosfixa (CelObjeto *iniInfixa);
Ao longo de todo processo as filas são implementadas através de uma lista encadeadas com cabeça em que toda célula é do tipo CelObjeto, como as filas do EP3. Na fila com a expressão posfixa, cada célula armazena uma variável, um número, ou um operador. Suponha que p é um ponteiro para uma célula dessa fila.
Macros podem tornar mais conveniente e claro o acesso através de ponteiros aos campos de uma estrutura como CelObjeto. Para isso foram declaradas as macros a seguir.
Copiado de objetos.h:/* nome de variaveis */ /* torna possivel escrevermos p->nomeID em vez de p->valor.pStr */ #define nomeID valor.pStr /* precedencia de operadores */ /* torna possivel escrevermos p->prec em vez de p->valor.pInt */ #define prec valor.pInt /* valores */ /* torna possivel escrevermos p->val em vez de p->valor.vFloat */ #define val valor.pFloat
Para interpretar a expressão posfixa a partir da fila, o seu programa deve utilizar uma pilha. A pilha deve ser implementada por meio de uma lista encadeada com cabeça em que cada elemento é do tipo CelObjeto. Como no EP3, essa tarefa será feita pela função
Copiado de eval.h:que deverá ser adaptada para o EP4.CelObjeto * eval(CelObjeto *iniPosfixa, Bool mostrePilhaExecucao);
Na descrição a seguir, por valor de uma célula pCel entenda-se:
O seu programa deve examinar cada célula da fila com a expressão posfixa e:
Para saber mais detalhes de como o programa realiza o cálculo da expressão em notação posfixa, consulte as notas de aula.
A tabela abaixo é baseada na tabela de precedência disponível aqui. Nessa tabela, os operadores estão em ordem decrescente de prioridade: na primeira linha os operadores executados em primeiro lugar e na última os operadores executados por último. Assim, o operador '=' possui a menor precedência dentre os operadores da tabela. A coluna direta indica a convenção de associação para os operadores da linha.
| ( ) | esquerda-para-esquerda | |
| _ not ^ | direita-para-esquerda | |
| * / % // | esquerda-para-direita | |
| + - | esquerda-para-direita | |
| < <= >= > | esquerda-para-direita | |
| == != | esquerda-para-direita | |
| and | esquerda-para-direita | |
| or | esquerda-para-direita | |
| = | direita-para-esquerda |
A tabela abaixo exemplifica a precedência dos operadores. Note, por exemplo, a associatividade da esquerda para direita entre operadores como '+' e '-' ou '*' e '/' e a associatividade da direita para esquerda dos operadores '_', 'not', '**' e '='.
| expressão | interpretação |
| 2 + 3 + 4 | (2 + 3) + 4 |
| 2 ** 3 ** 4 | 2 ** (3 ** 4) |
| A * B / C | (A * B) / C |
| A = B + C / 3.2 / C | A = (B + ((C / 3.2) / C)) |
| A = B = C = 3.2 | A = (B = (C = 3.2)) |
| A * _ B ** C - 2 | ((A * (_ (B ** C)) - 2) |
Aqui temos uma visão geral dos arquivos que compõem o EP.
Você deverá entregar apenas um arquivo
zip ou tar.gz
contendo todos os arquivos no diretório do seu EP4.
Este exercício programa é formado por 16 arquivos 8-[.
O diretório com esqueleto do EP contém, além desses 16 arquivos,
um Makefile para gerar o executável do pitao do EP.
Os arquivos no diretório com o esqueleto são
prompt/esqueleto> ls -l total 272 -rw-r--r--@ 1 cris 26744 Oct 25 11:27 00-esqueleto.zip -rw-r--r--@ 1 cris 945 Oct 24 12:15 Makefile -rw-r--r--@ 1 cris 3132 Oct 25 11:18 categorias.h -rw-r--r--@ 1 cris 7971 Oct 24 12:15 eval.c -rw-r--r--@ 1 cris 661 Oct 25 11:18 eval.h -rw-r--r--@ 1 cris 16497 Oct 25 11:19 lexer.c -rw-r--r--@ 1 cris 661 Oct 25 11:19 lexer.h -rw-r--r--@ 1 cris 8591 Oct 25 11:19 main.c -rw-r--r--@ 1 cris 10806 Oct 24 12:15 objetos.c -rw-r--r--@ 1 cris 3697 Oct 25 11:19 objetos.h -rw-r--r--@ 1 cris 2469 Oct 24 12:15 posfixa.c -rw-r--r--@ 1 cris 384 Oct 24 12:15 posfixa.h -rw-r--r--@ 1 cris 5846 Oct 24 12:15 st.c -rw-r--r--@ 1 cris 1107 Oct 24 12:15 st.h -rw-r--r--@ 1 cris 1594 Oct 24 12:15 stack.c -rw-r--r--@ 1 cris 1494 Oct 25 11:20 stack.h -rw-r--r--@ 1 cris 2833 Oct 25 11:20 util.c -rw-r--r--@ 1 cris 1257 Oct 25 11:20 util.h
O arquivo 00-esqueleto.zip contém todos os arquivos .h, .c que formam o EP4 junto com o Makefile.
Os arquivos que deverão ser manipulados são main.c, objetos.c, eval.c, posfixa.c e st.c. Os demais arquivos não devem ser alterados.
Os arquivos no esqueleto contêm comentários nos protótipos das funções que deverão ser feitas, parcialmente feitas ou estão completas. Os comentários fornecem as especificação do comportamento de cada função.
Para compilar o programa e gerar o executável basta, na linha de comando, digitar make. Faça isto assim que baixar o esqueleto e você verá as seguintes mensagens e um executável de nome pitao será gerado.
prompt/esqueleto> make
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c util.c
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c objetos.c
objetos.c:57:14: warning: unused variable 'nomeCategoria' [-Wunused-variable]
static char *nomeCategoria[MAX_CATEGORIAS] =
^
1 warning generated.
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c lexer.c
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c stack.c
stack.c:51:1: warning: ISO C requires a translation unit to contain at least one declaration [-Wempty-translation-unit]
^
1 warning generated.
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c posfixa.c
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c st.c
st.c:49:15: warning: unused variable 'ini' [-Wunused-variable]
static CelST *ini;
^
st.c:194:1: warning: unused function 'endVarST' [-Wunused-function]
endVarST(char *nomeVar)
^
2 warnings generated.
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c eval.c
eval.c:62:18: warning: unused variable 'precedencia' [-Wunused-const-variable]
static const int precedencia[MAX_OPERADORES] =
^
1 warning generated.
gcc -Wall -ansi -g -pedantic -Wno-unused-result -c main.c
gcc util.o objetos.o lexer.o stack.o posfixa.o st.o eval.o main.o -o pitao -lm
Note que, apesar de no esqueleto o corpo das funções que deverão ser feitas estar vazio,
o EP compila sem erros de sintaxe e com 5 avisos.
Se você executar o programa imediatamente verá que ele não faz grandes coisas:
prompt/esqueleto> pitao MAC0121 2019 - EP4 Pitao (Oct 25 2019, 12:09:28) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X >>> 1 + 2 AVISO: eval.c: Vixe! Ainda nao fiz a funcao itensParaValores. AVISO: eval.c: Vixe! Ainda nao fiz a funcao eval. AVISO: objetos.c: Vixe! Ainda nao fiz a funcao freeListaObjetos. >>> a = 2 AVISO: eval.c: Vixe! Ainda nao fiz a funcao itensParaValores. AVISO: eval.c: Vixe! Ainda nao fiz a funcao eval. AVISO: objetos.c: Vixe! Ainda nao fiz a funcao freeListaObjetos. >>> a AVISO: eval.c: Vixe! Ainda nao fiz a funcao itensParaValores. AVISO: eval.c: Vixe! Ainda nao fiz a funcao eval. AVISO: objetos.c: Vixe! Ainda nao fiz a funcao freeListaObjetos. >>>
Agora passamos à descrição dos arquivos.
Copiado de categorias.h:/* * numero de operadores * aritmeticos + relacionais + logicos + indexacao + atribuicao * 8 + 6 + 3 + 1 + 1 */ #define MAX_OPERADORES 19 /*-------------------------------------------------------------*/ /* temos 32 categorias de itens lexicos */ #define MAX_CATEGORIAS 32 enum listaCategorias { [. . . trecho removido . . .] }; typedef enum listaCategorias Categoria;
prompt> make gcc -Wall -ansi -g -pedantic -Wno-unused-result -c util.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c objetos.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c lexer.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c stack.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c posfixa.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c st.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c eval.c gcc -Wall -ansi -g -pedantic -Wno-unused-result -c main.c gcc util.o objetos.o lexer.o stack.o posfixa.o st.o eval.o main.o -o pitao -lm