Para ajudar-vos nesta tarefa, fornecemos a sua estrutura de base (na forma de um conjunto de ficheiros OCaml e um Makefile) que podem recuperar aqui : mini-python.zip. Uma vez descompactado, este arquivo produz uma pasta mini-python/ com os ficheiros seguintes :
| ast.mli | a sintaxe abstracta de mini-Python (completo) |
| lexer.mll | o analizador léxico (completo) |
| parser.mly | o analizador sintáctico (completo) |
| interp.ml | o interpretador (por completar) |
| main.ml | o programa principal (completo) |
| Makefile | para automatizar a compilação (completo) |
Como para o TD anterior, o código fornecido compila mas está incompleto. Podemos compilar com ajuda do utilitário (e comando) make (o executável resultante chama-se mini-python no directório corrente), ou então recorrer ao utilitário dune com o comando dune build @all (o executável neste caso fica no directório _build e pode-se criar um link simbólico com ln -s _build/default/main.exe mini-python ). O executável aplica-se sobre um ficheiro mini-Python com a extensão .py, assim :
./mini-python fich.pyUm ficheiro mini-Python tem a estrutura seguinte :
# zero, uma ou várias definições de funções no início do ficheiro
def fibaux(a, b, k):
if k == 0:
return a
else:
return fibaux(b, a+b, k-1)
def fib(n):
return fibaux(0, 1, n)
# uma ou várias instruções no fim do ficheiro
print "alguns valores da sequência de Fibonacci :"
for n in [0, 1, 11, 42]:
print(fib(n))
Mais geralmente, um ficheiro mini-Python é composto
de uma lista opcional de declarações de funções, seguido de uma
lista de instruções. As instruções são : a atribuição, a
condicional, o ciclo (for), a visualização de uma
expressão com print, a devolução de um valor
com return ou a avaliação de uma expressão. As expressões
inteiras são : uma constante (booleana, inteira ou uma string), o
acesso a uma variável, a construção de uma lista (com a
notação [e1, e2, ..., en]), o acesso a um elemento de
lista (com a notação
e[i]), a chamada de uma função, ou uma das operações
+, -, * e //,
=, <>, <, <=, >,
>=, and, or e not.
Consideramos igualmente as três funções primitivas: list(range(n)) constrói a lista [0, 1, 2, ..., n-1] e len(l) devolve o comprimento da lista l. (Apenas usaremos list e range em conjunto desta forma.)
print 1 + 2*3 print (3*3 + 4*4) // 5 print 10-3-4o resultado deve ser
7 5 3As operações de divisão e de módulo devem assinalar um erro no caso de divisão por zero. Utilizarmos para esse efeito a função error fornecida no ficheiro interp.ml.
Para testar facilmente, podemos editar o ficheiro test.py e invocar o comando make. Este comando compila o interpretador mini-python e executa este último sobre o ficheiro test.py.
Complete em seguida a função expr para interpretar as constantes booleanas, as operações de comparação e as operações and, or e not. Em Python, a comparação é estrutural ; poderemos utilizar directamente a comparação estrutural de OCaml, isto é utilizar operações como < sobre valores de tipo value. (Tal procedimento não é 100% compatível com Python, mas remediaremos esta situação mais adiante.)
Completar finalmente a função stmt para poder interpretar a condicional (construção Sif).
Testar com o programa seguinte :
print not True and 1//0==0
print 1<2
if False or True:
print "ok"
else:
print "oops"
cujo resultado deve ser
False True ok
(string, value) Hashtbl.t
Completar a função expr para que se possa aceder às variáveis. É o caso do padrão (pattern matching) Eident id. Tentar aceder a uma variável que não se encontra ainda na tabela deve provocar um erro. Nesta mesma linha, completar a função stmt para que se possa atribuir uma variável. É o caso do padrão Sassign (id, e1). Desta vez a variável pode estar ou não na tabela. No caso de la estar, o seu valor é modificado.
Finalmente, completar a função expr para que se possa concatenar duas strings com a operação +.
Testar com o programa seguinte :
x = 41 x = x+1 print(x) b = True and False print(b) s = "hello" + " world!" print(s)o resultado deve ser
42 False hello world!
let functions = (Hashtbl.create 17 : (string, ident list * stmt) Hashtbl.t)A cada nome de função está associada um par constituído da lista dos parâmetro e da instrução que define o corpo da função. Completar a função file para que esta preencha esta tabela com as funções contidas na lista fl.
Completar na sequência as funções expr e stmt para interpretar uma chamada de função. Para uma chamada da forma f(e1,...,en) a uma função f da forma def f(x1,...,xn): body deve-se construir um novo ambiente que associe a cada argumento formal xi o valor de ei. Podemos então interpretar a instrução body (o corpo da função) neste novo ambiente. A instrução return sera interpretada utilizando a excepção OCaml Return (já definida).
Testar com o programa seguinte :
def fact(n):
if n <= 1: return 1
return n * fact(n-1)
print fact(10)
cujo resultado deve ser
3628800
Completar em sequência a função stmt para poder interpretar a atribuição de um elemento de lista (caso do padrão Sset (e1, e2, e3)).
Finalmente, completar a função stmt para poder interpretar a construção for. A construção Sfor(x,e,s) atribuí a variável x sucessivamente aos diferentes elementos da lista e e executa de cada vez a instrução s. A expressão e deve ser avaliada uma só vez.
Testar sobre o programa dado no início do enunciado. o resultado deve ser:
0 1 89 267914296
Escrever uma função compare_value: value -> value -> int para comparar dois valores Python. Esta função devolve um inteiro estritamente negativo (resp. nulo, resp. estritamente positivo) quando o primeiro valor é menor (resp. igual, resp. maior) que o segundo. Poder-se-á recorrer ao interpretador de Python como referência em caso de dúvidas. Utilizar esta função para rectificar o que foi feito na questão 2.
Fazer testes suplementares para constatar a correção da solução proposta.