compiladores

Compiladores

2 Formas de Validação
Top-down ou Descendente
Analisadores
Sintáticos
Botton-up ou Ascendente

Exemplo:

Dada a expressão: (v+v)*v e considerando as gramáticas:
1 E → E + E
2 E → E * E
3 E → (E)
4 E → V

Para verificar se a expressão pode ser produzida utilizando a validação descendente, fazemos assim:
E → E * E (2)
E → (E) * E (3)
E → (E + E) * E (1)
E → (V + E) *E (4)
E → (V + V) *E (4)
E → (V + V) * V (4)

Então a sequencia de utilização das produções é: 2,3,1,4,4,4
Mas são possíveis outras sequencias como:

a) 2, 3, 4, 1, 4, 4 E → E * E (2)
E → (E) * E (3)
E → (E) * V (4)
E → (E + E) * V (1)
E → (V + E) *V (4)
E → (V + V) * V (4)

b) 2, 4, 3, 1, 4, 4, E → E * E (2)
E → E * V (4)
E → (E) * V (3)
E → (E + E) * V (1)
E → (V + E) *V (4)
E → (V + V) * V (4)

Botton-up:

(V + V) * V ← (E + V) * V (4) ← (V + E) *V (4) ← (E + E) * V (1) ← (E) * V (3) ← E * V (4) ← E * E (2)

Também é possível montarmos as arvores sintáticas para isto, iniciamos montando sub arvores das produções, por exemplo:

E → E + E E → E * E E → (E) E → (V)

E E E E

E + E E * E ( E ) V

Então a árvore sintática da expressão (V + V) * V e:

E

E * E

( E ) V E + E

V + V

Derivação Canônica

Está relacionada à estratégia de como se pode percorrer sequencialmente os elementos da arvore.