Árboles de reconocimiento

Universidad
 de
 Guadalajara
 
Centro
 Universitario
 de
 Ciencias
 Exactas
 e
 
Ingenierías
 
Lenguajes
 de
 Programación
 Comparados.
 
Árboles
 de Reconocimiento.
 

 

Martínez
 Castillo
 Erick
 Jesús
 
Sección
 D02
 


 
 
 
 
 


 


 

Arboles de Reconocimiento:
Un árbol dederivación o árbol sintáctico es una forma de describir gráficamente cómo en
una cierta gramática una cadena puede ser derivada desde el símbolo inicial.
La forma más simple es listar las cadenas desímbolos consecutivas, comenzando por el
símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas.
Hay dos tipos de derivación, el primero se llama derivación por la izquierda yconsta de
estrategias de como reemplazar el terminal de más a la izquierda primero, pero
contrariamente si aplicamos reglas de forma que derivemos primero el no terminal de la
derecha le llamaremosderivación por la derecha, por ejemplo:
A à A - A
A à 3
Y si queremos derivar la cadena “3 - 3 - 3”, el orden que usaríamos con derivación por la
izquierda seria: [(1), (1), (2), (2), (2)],mientras que si usamos derivación por la derecha
seria: [(1), (2), (1), (2), (2)]

Derivación por la izquierda
•
•
•
•
•


 

A → A - A (1)
A → A - A - A (1)
A → 3 - A - A (2)
A → 3 - 3 -A (2)
A → 3 - 3 - 3 (2)

Derivación por la derecha
•
•
•
•
•

A → A - A (1)
A → 3 - A (2)
A → 3 - A - A (1)
A → 3 - 3 - A (2)
A → 3 - 3 - 3 (2)

1
 


 
 
 
 
  


 

Árbol de derivación por la izquierda

A
 

'-­‐'
 

A
 

A
 

3
 

'-­‐'
 

A
 

A
 


 

3
 

3
 

2
 


 
  
 
 


 


 

Árbol de derivación por la derecha

A
 

3
 

'-­‐'
 

A
 

A
 

'-­‐'
 

A
 

A
 


 

3
 

3
 

3
 ...