Exercício 07.29

Apresente uma derivação à extrema direita (DED) da sentença x + (y * (z * x) + z) sobre a gramática a seguir.

G = ({S, A, B, C}, {x, y, z, +, *, (, )}, P, S)
P = {< S >  ->  < S > + < S >  |  < A >
     < A >  ->  < A > * < A >  |  < B >
     < B >  ->  ( < S > )  |  < C >
     < C >  ->  x  |  y  |  z }

Resposta

< S >
< S > + < S >
< S > + < A >
< S > + < B >
< S > + ( < S > ) 
< S > + ( < S > + < S > ) 
< S > + ( < S > + < A > ) 
< S > + ( < S > + < B > ) 
< S > + ( < S > + < C > ) 
< S > + ( < S > + z ) 
< S > + ( < A > + z ) 
< S > + ( < A > * < A > + z ) 
< S > + ( < A > * < B > + z ) 
< S > + ( < A > * ( < S > ) + z ) 
< S > + ( < A > * ( < A > ) + z ) 
< S > + ( < A > * ( < A > * < A > ) + z ) 
< S > + ( < A > * ( < A > * < B > ) + z ) 
< S > + ( < A > * ( < A > * < C > ) + z ) 
< S > + ( < A > * ( < A > * x ) + z ) 
< S > + ( < A > * ( < B > * x ) + z ) 
< S > + ( < A > * ( < C > * x ) + z ) 
< S > + ( < A > * ( z * x ) + z ) 
< S > + ( < B > * ( z * x ) + z ) 
< S > + ( < C > * ( z * x ) + z ) 
< S > + ( y * ( z * x ) + z ) 
< A > + ( y * ( z * x ) + z ) 
< B > + ( y * ( z * x ) + z ) 
< C > + ( y * ( z * x ) + z ) 
x + ( y * ( z * x ) + z )