Exercícios

Em Construção

Exercício 01

Para cada um dos pares palavra/gramática seguintes, obtenha a estrutura simplificada da palavra na forma de uma árvore apenas com terminais nos nós.

  1. Emparelhe E → E + T | E - T | T ; T → T × F | T ÷ F | F ; F → N | ( E ), em que N representa qualquer número inteiro, com:
    1. 2, (2), 2 + 3, 2 × 3, (2 + 3).
    2. 2 + (3 × 4), 2 + 3 × 4 e (2 + 3) × 4.
    3. 2 + (3 + 4), 2 + 3 + 4 e (2 + 3) + 4.
    4. (2 + 3) × (3 + 4), 2 + (3 × 3) + 4, 2 + 3 × 3 + 4.
    5. (2 × 3) + (3 × 4), 2 × (3 + 3) × 4, 2 × 3 + 3 × 4.
  2. sequências; lisp;

Exercício 02

Os nós de árvores podem ser representadas por listas heterogéneas (suportadas diretamente, por exemplo, em Python) em que o primeiro elemento é o conteúdo do nó e os seguintes elementos são os descendentes. Por convenção, as folhas representam-se apenas pelo conteúdo (isto é, pelo valor 42 em vez da lista [42]). Implemente:

  • degree(a) o número de descendentes de a.
  • size(a) o número de nós em a.
  • tree_degree(a) o maior grau dos nós em a.
  • is_leaf(a) se a não tem descendentes.
  • is_inner(a) se a tem descendente.
  • is_parent(a, b) se a é ascendente direto de b.
  • is_neighbor(a, b) se a é ascendente direto de b ou vice-versa.
  • is_antecessor(a, b) se a é ascendente (direto, ou não) de b.
  • is_descendant(a, b) se a é descendente (direto, ou não) de a.
  • level(a, b): se b descende de a, o número de arestas do caminho que liga a a b; caso contrário, None.
  • width(a, n) o número de descendentes de a no nível n.
  • breadth(a) o número de folhas de a.
  • pesquisas; inserir; remover; podar; menor ascendente comum de dois nós;

Exercício 03

  • Revisitar exercícios de Python?
  • Funções anónimas (???)
    • Aplicações: map, filter, reduce

Exercício 04

  • Lisp (sbcl)

Exercício 05

E → T E₁
E₁ → + T E₁ | - T E₁ | λ
T → F T₁
T₁ → * F T₁ | / F T₁ | λ
F → ( E ) | N
N → D N₁
N₁ → λ | D N₁
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  • Verifique que a gramática acima é LL(1) e implemente uma calculadora na linha de comandos para efetuar contas simples como 2 + (3 * 4).

Exercício 06

  • Melhorar ALisP:
    • Incluir um gerador de números aleatórios nas funções base.
    • Corrigir atom_value de forma a prever o tipo do valor, em vez de levantar exceções.
    • Tratar adequadamente as string, delimitadas por ".
    • Suportar quote, de forma a suspender a valoração de uma expressão.
    • Mudar ALisP.value de forma a que True e False sejam sempre booleanos (não é o caso agora!)
  • Extensões ALisP
    • (range start end) (fechado-aberto).
    • (for var list instr)
    • (native "Python expr") como?
    • (pair key val), (update key val map), (get key map), (keys map)
    • (fn-map fn list), (filter pred list),