Orden de evaluación para SDD

El orden de evaluación para SDD incluye cómo se evalúa SDD (definición dirigida por sintaxis) con la ayuda de atributos, gráficos de dependencia, reglas semánticas y definiciones con atributos S y L. SDD ayuda en el análisis semántico en el compilador, por lo que es importante saber cómo se evalúan los SDD y su orden de evaluación. Este artículo proporciona información detallada sobre la evaluación SDD. Requiere algunos conocimientos básicos de gramática, producción, árbol de análisis, árbol de análisis anotado, atributos sintetizados y heredados.   

Terminologías:

• Árbol de análisis: un árbol de análisis es un árbol que representa la sintaxis de la producción de forma jerárquica.
• Árbol de análisis anotado: el árbol de análisis anotado contiene los valores y atributos en cada Node.
• Atributos Sintetizados: Cuando la evaluación del atributo de cualquier Node se basa en hijos.
• Atributos Heredados: Cuando la evaluación del atributo de cualquier Node se basa en hijos o padres. 

Gráficos de dependencia:

Un gráfico de dependencia proporciona información sobre el orden de evaluación de los atributos con la ayuda de los bordes. Se utiliza para determinar el orden de evaluación de los atributos según las reglas semánticas de la producción. Un borde desde el atributo del primer Node al atributo del segundo Node proporciona la información de que se requiere la evaluación del atributo del primer Node para la evaluación del atributo del segundo Node. Los bordes representan las reglas semánticas de la producción correspondiente. 

Reglas del gráfico de dependencia: un Node en el gráfico de dependencia corresponde al Node del árbol de análisis para cada atributo. Los bordes (primer Node desde el segundo Node) del gráfico de dependencia representan que el atributo del primer Node se evalúa antes que el atributo del segundo Node.

Ordenando la Evaluación de Atributos:

El gráfico de dependencia proporciona el orden de evaluación de los atributos de los Nodes del árbol de análisis. Un borde (es decir, del primer Node al segundo Node) en el gráfico de dependencia representa que el atributo del segundo Node depende del atributo del primer Node para una evaluación posterior. Este orden de evaluación da un orden lineal llamado orden topológico .

No hay forma de evaluar SDD en un árbol de análisis cuando hay un ciclo presente en el gráfico y, debido al ciclo, no existe un orden topológico.  

Mesa de producción
S. No.	Producciones	Reglas semánticas
1.	S ⇢ A y B	S.val = A.syn + B.syn
2.	A ⇢ A 1 # B	A.syn = A1.syn * B.syn  A1.inh = A.syn
3.	A1 ⇢ B	A1.syn = B.syn
4.	B ⇢ dígito	B.syn = digit.lexval

Explicación del gráfico de dependencia:

El número de Node en el gráfico representa el orden de evaluación del atributo asociado. Los bordes del gráfico representan que el segundo valor depende del primer valor. 

La Tabla-1 representa los atributos correspondientes a cada Node. 
La Tabla-2 representa las reglas semánticas correspondientes a cada arista.  

Tabla 1
Node	Atributo
1	dígito.lexval
2	dígito.lexval
3	dígito.lexval
4	B.syn
5	B.syn
6	B.syn
7	A1.syn
8	A.syn
9	A1.inh
10	S.val

Tabla 2
Borde		Regla semántica correspondiente  (De la mesa de producción)
De	A
1	4	B.syn = digit.lexval
2	5	B.syn = digit.lexval
3	6	B.syn = digit.lexval
4	7	A1.syn = B.syn
5	8	A.syn = A1.syn * B.syn
6	10	S.val = A.syn + B.syn
7	8	A.syn = A1.syn * B.syn
8	10	S.val = A.syn + B.syn
8	9	A1.inh = A.syn

Definiciones con atributos S:

SDD con atributos S solo puede tener atributos sintetizados. En este tipo de definiciones las reglas semánticas se sitúan únicamente al final de la producción. Su evaluación se basa en un análisis de abajo hacia arriba. 

Ejemplo: S ⇢ AB { Sx = f(Ax | Bx) }

Definiciones con atributos L:

El SDD con atributos L se puede sintetizar y heredar (los atributos heredados restringidos solo se pueden tomar del padre o de los hermanos restantes). En este tipo de definición, las reglas semánticas se pueden colocar en cualquier parte del RHS de la producción. Su evaluación se basa en orden (clasificación topológica). 

Ejemplo : S ⇢ AB {Ax = Sx + 2} o S ⇢ AB { Bx = f(Ax | Bx) } o S ⇢ AB { Sx = f(Ax | Bx) }

Nota:

• Cada gramática con atributos S también tiene atributos L.
• Para la evaluación con atributos L se utiliza el orden del árbol de análisis anotado.
• Para S-atribuido se utiliza el reverso de la derivación más a la derecha.

Reglas semánticas con efectos secundarios controlados:

Los efectos secundarios son el fragmento de programa contenido dentro de las reglas semánticas. Estos efectos secundarios en SDD se pueden controlar de dos maneras: permitir los efectos secundarios incidentales y restringir las órdenes de evaluación admisibles para que tengan la misma traducción que cualquier orden admisible.