Tutoriais - Linguagens Formais e Autômatos
Tutoriais
Linguagens Formais e Autômatos

1. Ybadoo
2. Tutoriais
3. Linguagens Formais e Autômatos
4. Gramáticas Livre do Contexto (GLC)
5. Exercício 07.120

Exercício 07.120

Apresente a) uma derivação à extrema esquerda (DEE), b) uma derivação à extrema direita (DED) e c) uma árvore de derivação (parse tree) da sentença x = a + b * (c - d) / a - b sobre a gramática a seguir.

G = ({S, E, T, F, V}, {a, b, c, d, x, =, +, -, *, /, (, )}, P, S)
P = {S → V = E
     E → E + T | E - T | T
     T → T * F | T / F | F
     F → ( E ) | V
     V → a | b | c | d | x}

Solução do Exercício

Derivação à extrema esquerda (DEE)

S
V = E
x = E
x = E - T
x = E + T - T
x = T + T - T
x = F + T - T
x = V + T - T
x = a + T - T
x = a + T / F - T
x = a + T * F / F - T
x = a + F * F / F - T
x = a + V * F / F - T
x = a + b * F / F - T
x = a + b * ( E ) / F - T
x = a + b * ( E - T ) / F - T
x = a + b * ( T - T ) / F - T
x = a + b * ( F - T ) / F - T
x = a + b * ( V - T ) / F - T
x = a + b * ( c - T ) / F - T
x = a + b * ( c - F ) / F - T
x = a + b * ( c - V ) / F - T
x = a + b * ( c - d ) / F - T
x = a + b * ( c - d ) / V - T
x = a + b * ( c - d ) / a - T
x = a + b * ( c - d ) / a - F
x = a + b * ( c - d ) / a - V
x = a + b * ( c - d ) / a - b

Derivação à extrema direita (DED)

S
V = E
V = E - T
V = E - F
V = E - V
V = E - b
V = E + T - b
V = E + T / F - b
V = E + T / V - b
V = E + T / a - b
V = E + T * F / a - b
V = E + T * ( E ) / a - b
V = E + T * ( E - T ) / a - b
V = E + T * ( E - F ) / a - b
V = E + T * ( E - V ) / a - b
V = E + T * ( E - d ) / a - b
V = E + T * ( T - d ) / a - b
V = E + T * ( F - d ) / a - b
V = E + T * ( V - d ) / a - b
V = E + T * ( c - d ) / a - b
V = E + F * ( c - d ) / a - b
V = E + V * ( c - d ) / a - b
V = E + b * ( c - d ) / a - b
V = T + b * ( c - d ) / a - b
V = F + b * ( c - d ) / a - b
V = V + b * ( c - d ) / a - b
V = a + b * ( c - d ) / a - b
x = a + b * ( c - d ) / a - b

Árvore de derivação (parse tree)