Arboles de reconocimiento

 
1.4.1.3: Arboles de Reconocimiento.
 
José Manuel Vargas Navarro.
4
Á
rbol de derivación por la izquierda
A
AA3'-'A3'-'A3

 
1.4.1.3: Arboles de Reconocimiento.
 
José Manuel Vargas Navarro.
4
Á
rbol de derivación por la izquierda
A
AA3'-'A3'-'A3

 
1.4.1.3: Arboles de Reconocimiento.
 
José Manuel Vargas Navarro.
4
Á
rbol de derivación por la izquierda
AAA3'-'A3'-'A3

3'-'A3'-'A3

3'-'A3'-'A3

3'-'A3'-'A3

3'-'A3'-'A3

 
1.4.1.3: Arboles de Reconocimiento.
 
José Manuel Vargas Navarro.
6
 A
nálisis Sintáctico
Existen dos tipos de análisis sintáctico:
Descendente.
 Análisis descendente: se parte de la raíz del árbol (símbolo inicial de lagramática) y se van aplicando reglas por la izquierda obteniendo unaderivación por la izda. del símboloinicial. Las hojas del árbol tendrán los tokensque nos devuelve el analizador léxico.

 
1.4.1.3: Arboles de Reconocimiento.
 
José Manuel Vargas Navarro.
6
 A
nálisis Sintáctico
Existen dos tipos de análisis sintáctico:
Descendente.
 Análisis descendente: se parte de la raíz del árbol (símbolo inicial de lagramática) y se van aplicando reglas por la izquierda obteniendounaderivación por la izda. del símbolo inicial. Las hojas del árbol tendrán los tokensque nos devuelve el analizador léxico.

Un árbol de derivació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.

Un árbol de parse puede ser visto como una representación gráfica de una derivación,
donde el orden en que sonaplicadas las producciones es mostrado, debido a la naturaleza
jerárquica del árbol.

Un árbol de parse tiene las siguientes características :

• La raíz del árbol es el símbolo de inicio de la gramática.
• Las hojas (nodos sin hijos) son símbolos terminales, es decir, tokens.
• Los nodos intermedios son etiquetados siempre por un símbolo no terminal.
• Un nodo y sus hijos constituyen unaproducción.

El árbol de parse que representa la derivación R ∗⇒ read (x,y) es mostrado enseguida. La
gramática es la del siguiente ejemplo.

R
-> read(P)

P ->pi,d

P-> id

R
read

( p )

P . id

id

En el árbol se aprecian 6 nodos sin hijos, es decir, hojas. Todos ellos etiquetados por un
token. La raíz es el símbolo de inicio R de la gramática. Losnodos intermedios son 2 y
ambos son etiquetados por la variable sintáctica P.

La forma más simple es listar las cadenas de sí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 y consta de estrategias de como reemplazar el terminal de más a la izquierdaprimero, pero contrariamente si aplicamos reglas de forma que derivemos primero el no terminal de la derecha le llamaremos derivación por la derecha,

 
 

Existen dos tipos de análisis sintáctico:

Descendente.
Análisis descendente:se parte dela raíz del árbol (símbolo inicial de la gramática) y se van aplicando reglas por la izquierda obteniendo una derivación por la izquierda. Delsímbolo inicial. Las hojas del árbol tendrán los tokens que nos devuelve el analizador léxico.

ascendente
Análisis ascendente: se empieza por las hojas (tokens) y se van creando los nodos intermedios hasta llegar a la raíz (símbolo inicial).

Ambigüedad.
Se dice que una gramática es ambigua, si ésta produce más de un árbol de
reconocimiento (parse) para una misma sentencia. O de otra manera,cuando la gramática produce más de una derivación -ya sea izquierda ó derecha- para una misma
sentencia.
Supongamos la gramática :

E
->E+E | E-E | E*E | E/E | id | num
y

G = ( { +, -, *, /, id, num }, { E }, E, Φ )

Obtengamos la derivación para la sentencia : 5 + id * 9
(1) E=> E+E => num+E => num+E*E=> num+id*E => num+id*num

Pero, existe otra derivación...