Este é o primeiro de uma série de exercícios-programas que têm como objetivo a construção de um interpretador de expressões simples em notação infixa que, como em um programa, também poderão conter variáveis. Exemplos de expressões que o interpretador executará são:
mp = (p1 + 2*p2 + 2*p3)/5
nota_final = 0.75*mp + 0.25*me
nr = (prec + nf)/2
Como pode ser notado, as expressões serão semelhantes àquelas encontradas em linguagens de programação. Assim como em Python, variáveis poderão ser criadas por meio de atribuições e reutilizadas em expressões futuras.
Python 3.4.3 (default, Mar 26 2015, 22:07:01)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 + 2
3
>>> 3.14 * 6
18.84
>>> p1 = 4
>>> p2 = 5
>>> p3 = 6
>>> mp = (p1 + 2*p2 + 2*p3)/5
>>> mp
5.2
>>> me = 6
>>> nota_final = 0.75*mp + 0.25*me
>>> nota_final
5.4
>>>
>>> nota_final = 4
>>> nota_final
4
>>> prec = 5.5
>>> nr = (prec + nota_final)/2
>>> nr
4.75
>>>
Durante o processo da construção desse interpretador aprenderemos e revisaremos vários conceitos de programação, algoritmos e estruturas de dados: orientação a objetos, pilhas, tabelas de símbolos, dicionários, etc.
Começaremos com uma tarefa simples. Neste exercício programa você deverá fazer uma função de nome tokeniza() que, como veremos será gradativamente alterada e complementada nos próximos exercícios programas.
- Continuar o desenvolvimento da habilidade de resolver problemas computacionais a partir de tipos básicos como listas, strings e dicionários.
- Utilizar novas estruturas (pilhas e filas).
- Motivar o uso de classes de objetos na resolução de problemas.
Uma das primeiras tarefas realizadas por um compilador ou interpretador após da leitura de um programa é a sua análise léxica. Neste EP você desenvolverá um analisador léxico que receberá uma linha (= string) com uma expressão aritmética simples e produzirá como saída uma lista de pares da forma
[item, categoria]
Um item léxico (= lexeme) é uma cadeia de caracteres (= string) que representa um elemento básico de uma linguagem. Os itens léxicos são classificados em unidades léxicas que são indicadas pelo componente categoria do par. O par representando o item léxico e a sua categoria é também chamado de um token. O processo de formar tokens a partir de uma dado string é chamado de análise léxica (= tokenization). Considere a expressão
media_prova = (p1 + p2)/2
A análise léxica dessa expressão pode produzir:
'media_prova' : nome de variável
'=' : operador para atribuição
'(' : abre parenteses
'p1' : nome de variável
'+' : operador aritmético para adição
'p2' : nome de variável
')' : fecha parenteses
'/' : operador aritmético para divisão
2.000000 : constante float
Assim, o objetivo da análise léxica é produzir uma lista (= fila) de pares da forma [item, categoria]. Neste exercício programa as categorias a serem consideradas são determinadas pelas constantes:
# categorias
OPERADOR = 1 # para operadores aritméticos e atribuição
NUMERO = 2 # para números: todos são considerados float
VARIAVEL = 3 # para variáveis
PARENTESES = 4 # para '(' e ')
Por exemplo, para a expressão
media_prova = (p1 + p2)/2
a análise léxica deverá produzir a lista
[['media_prova', 3], ['=', 1], ['(', 4], ['p1', 3], ['+', 1], ['p2', 3], [')', 4], ['/', 1], [2.0, 2]]
Primeiro, você deve baixar os arquivos main.py, operadores.py e esqueleto_tokeniza.py.
O módulo main.py contém a função main() que é a função principal do projeto (= função que coordena o programa). A função main() está completamente escrita e nada no módulo main.py deve ser alterado.
O módulo operadores.py contém um dicionário com uma descrição dos operadores aritméticos e parênteses. Esse módulo é utilizado apenas pela função main() e também não deve ser alterado.
Já o módulo tokeniza.py contém o esqueleto da única função que você deve fazer e entregar:
def tokeniza(exp):
"""(str) -> list
Recebe uma string exp representando uma expressão e cria
e retorna uma lista com os itens léxicos que formam a
expressão.
Cada item léxico (= token) é da forma
[item, tipo]
O componente item de um token é
- um float: no caso do item ser um número; ou
- um string no caso do item ser um operador ou
uma variável ou um abre/fecha parenteses.
O componente tipo de um token indica a sua categoria
(ver definição de constantes acima).
- OPERADOR;
- NUMERO;
- VARIAVEL; ou
- PARENTESES
A função ignora tudo que esta na exp apos o caractere
COMENTARIO (= "#").
"""
Na parte A, você deve escrever a função tokeniza() do módulo tokeniza.py e depositar na página da disciplina apenas esse módulo.
A seguir estão alguns exemplos de execução da função tokeniza().
Python 3.4.3 (default, Mar 26 2015, 22:07:01)
[GCC 4.9.2] on linux
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> tokeniza("+")
[['+', 1]]
>>> tokeniza("=^! - +/* %")
[['=', 1], ['^', 1], ['!', 1], ['-', 1], ['+', 1], ['/', 1], ['*', 1], ['%', 1]]
>>> tokeniza("")
[]
>>> tokeniza("123")
[[123.0, 2]]
>>> tokeniza(".5")
[[0.5, 2]]
>>> tokeniza("12.5")
[[12.5, 2]]
>>> tokeniza("v")
[['v', 3]]
>>> tokeniza("v_1")
[['v_1', 3]]
>>> tokeniza("v_1 var nome_var")
[['v_1', 3], ['var', 3], ['nome_var', 3]]
>>> tokeniza(" ") # string com espaços
[]
>>> tokeniza("(()(") # string apenas com parenteses
[['(', 4], ['(', 4], [')', 4], ['(', 4]]
>>> tokeniza("mp = (p1 + 2*p2 + 2*p3)/ 5")
[['mp', 3], ['=', 1], ['(', 4], ['p1', 3], ['+', 1], [2.0, 2], ['*', 1], ['p2', 3], ['+', 1], [2.0, 2], ['*', 1], ['p3', 3], [')', 4], ['/', 1], [5.0, 2]]
>>>
>>> tokeniza(" # esta string tem apenas comentários")
[]
>>> tokeniza(" nf = 4 # nota final < 5 indica rec")
[['nf', 3], ['=', 1], [4.0, 2]]
>>>
A seguir esta um exemplo de execução do programa completo (= função main()).
Python 3.4.3 (default, Mar 26 2015, 22:07:01)
[GCC 4.9.2] on linux
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
Entre como uma expressão ou tecle apenas ENTER para encerrar.
expressão >>> +
'+' : operador aritmético para adição
expressão >>> =^! - +/* %
'=' : operador para atribuição
'^' : operador aritmético para exponenciacao
'!' : operador aritmético 'menos unário'
'-' : operador aritmético para subtração
'+' : operador aritmético para adição
'/' : operador aritmético para divisão
'*' : operador aritmético para multiplicação
'%' : operador aritmético para resto de divisão
expressão >>> 123
123.000000 : constante float
expressão >>> .5
0.500000 : constante float
expressão >>> 12.5
12.500000 : constante float
expressão >>> v_1
'v_1' : nome de variável
expressão >>> v_1 var nome_var
'v_1' : nome de variável
'var' : nome de variável
'nome_var' : nome de variável
expressão >>> # linha vazia
expressão >>> # string apenas com espaços
expressão >>> (()(
'(' : abre parenteses
'(' : abre parenteses
')' : fecha parenteses
'(' : abre parenteses
expressão >>> mp = (p1 + 2*p2 + 2*p3)/ 5
'mp' : nome de variável
'=' : operador para atribuição
'(' : abre parenteses
'p1' : nome de variável
'+' : operador aritmético para adição
2.000000 : constante float
'*' : operador aritmético para multiplicação
'p2' : nome de variável
'+' : operador aritmético para adição
2.000000 : constante float
'*' : operador aritmético para multiplicação
'p3' : nome de variável
')' : fecha parenteses
'/' : operador aritmético para divisão
5.000000 : constante float
expressão >>> # esta string tem apenas comentários
expressão >>> nf = 4 # nota final < 5 indica rec
'nf' : nome de variável
'=' : operador para atribuição
4.000000 : constante float
expressão >>>
>>>