Diseño del compilador: análisis semántico

Hemos aprendido cómo un analizador construye árboles de análisis sintáctico en la fase de análisis de sintaxis. El árbol de análisis simple construido en esa fase generalmente no es útil para un compilador, ya que no contiene ninguna información sobre cómo evaluar el árbol. Las producciones de gramática libre de contexto, que hace las reglas del lenguaje, no se adaptan a cómo interpretarlas.

Por ejemplo

E → E + T

La producción de CFG anterior no tiene una regla semántica asociada y no puede ayudar a darle sentido a la producción.

Semántica

La semántica de un lenguaje proporciona significado a sus construcciones, como tokens y estructura de sintaxis. La semántica ayuda a interpretar los símbolos, sus tipos y sus relaciones entre sí. El análisis semántico juzga si la estructura sintáctica construida en el programa fuente deriva algún significado o no.

CFG + semantic rules = Syntax Directed Definitions

Por ejemplo:

int a = “value”;

no debe generar un error en la fase de análisis léxico y sintáctico, ya que es léxica y estructuralmente correcto, pero debe generar un error semántico ya que el tipo de asignación es diferente. Estas reglas son establecidas por la gramática del idioma y evaluadas en análisis semántico. Las siguientes tareas deben realizarse en análisis semántico:

• Resolución de alcance
• Comprobación de tipo
• Comprobación enlazada a matriz

Errores semánticos

Hemos mencionado algunos de los errores semánticos que se espera que reconozca el analizador semántico:

• Falta de coincidencia de tipos
• Variable no declarada
• Mal uso del identificador reservado.
• Declaración múltiple de variable en un ámbito.
• Accediendo a una variable fuera de alcance.
• Desajuste de parámetros real y formal.

Gramática de atributos

La gramática de atributos es una forma especial de gramática libre de contexto en la que se agrega información adicional (atributos) a uno o más de sus no terminales para proporcionar información sensible al contexto. Cada atributo tiene un dominio de valores bien definido, como entero, flotante, carácter, cadena y expresiones.

La gramática de atributos es un medio para proporcionar semántica a la gramática libre de contexto y puede ayudar a especificar la sintaxis y la semántica de un lenguaje de programación. La gramática de atributos (cuando se ve como un árbol de análisis) puede pasar valores o información entre los nodos de un árbol.

Example:

E → E + T { E.value = E.value + T.value }

La parte derecha del CFG contiene las reglas semánticas que especifican cómo se debe interpretar la gramática. Aquí, los valores de los no terminales E y T se suman y el resultado se copia en el no terminal E.

Los atributos semánticos pueden asignarse a sus valores de su dominio en el momento del análisis sintáctico y evaluarse en el momento de la asignación o las condiciones. Según la forma en que los atributos obtienen sus valores, se pueden dividir en dos categorías: atributos sintetizados y atributos heredados.

Atributos sintetizados

Estos atributos obtienen valores de los valores de atributo de sus nodos secundarios. Para ilustrar, suponga la siguiente producción:

S → ABC

Si S está tomando valores de sus nodos secundarios (A, B, C), entonces se dice que es un atributo sintetizado, ya que los valores de ABC se sintetizan en S.

Como en nuestro ejemplo anterior (E → E + T), el nodo padre E obtiene su valor de su nodo hijo. Los atributos sintetizados nunca toman valores de sus nodos principales ni de ningún nodo hermano.

Atributos heredados

A diferencia de los atributos sintetizados, los atributos heredados pueden tomar valores de los padres y / o hermanos. Como en la siguiente producción,

S → ABC

A puede obtener valores de S, B y C. B puede tomar valores de S, A y C. Asimismo, C puede tomar valores de S, A y B.

Expansion : Cuando un no terminal se expande a terminales según una regla gramatical

Reduction: Cuando un terminal se reduce a su correspondiente no terminal según las reglas gramaticales. Los árboles de sintaxis se analizan de arriba hacia abajo y de izquierda a derecha. Siempre que se produce una reducción, aplicamos sus correspondientes reglas semánticas (acciones).

El análisis semántico utiliza traducciones dirigidas por sintaxis para realizar las tareas anteriores.

El analizador semántico recibe AST (Abstract Syntax Tree) de su etapa anterior (análisis de sintaxis).

El analizador semántico adjunta información de atributos con AST, que se denominan AST atribuidos.

Los atributos son dos valores de tupla, <nombre de atributo, valor de atributo>

Por ejemplo:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Para cada producción, adjuntamos una regla semántica.

SDT atribuido a S

Si un SDT usa solo atributos sintetizados, se llama SDT con atributos S. Estos atributos se evalúan utilizando SDT con atributos S que tienen sus acciones semánticas escritas después de la producción (lado derecho).

Como se describió anteriormente, los atributos en los SDT con atributos S se evalúan en el análisis de abajo hacia arriba, ya que los valores de los nodos principales dependen de los valores de los nodos secundarios.

SDT atribuido a L

Esta forma de SDT utiliza atributos sintetizados y heredados con la restricción de no tomar valores de los hermanos derechos.

En los SDT con atributos L, un no terminal puede obtener valores de sus nodos padre, hijo y hermano. Como en la siguiente producción

S → ABC

S puede tomar valores de A, B y C (sintetizados). A solo puede tomar valores de S. B puede tomar valores de S y A. C puede obtener valores de S, A y B. Ningún no terminal puede obtener valores del hermano a su derecha.

Los atributos en los SDT con atributos L se evalúan mediante el análisis de profundidad primero y de izquierda a derecha.

Podemos concluir que si una definición tiene atribución S, también se atribuye a L, ya que la definición con atribución L incluye definiciones con atribución S.