inicio

UNIVERSIDAD GERARDO BARRIOS


Facultad de ciencias y tecnologias



e-Portafolio de evidencias



Catedra: Compiladores e interpretes



Tutor: Ing. Marvin Osmaro Parada



Alumno: Herson Enrique Chorro Ventura



Lenguajes Intermedios y Generación de Código

Después de los análisis Lexicos, sintácticos y semánticos, algunos compiladores generan una representación intermedia explicita del programa fuente. Se puede considerar esta representación intermedia como un programa para una maquina abstracta. Esta representación intermedia debe tener dos propiedades importantes, debe ser fácil de producir y fácil de traducir al programa objeto.
*El código intermedió es particularmente utilizado cuando el objetivo de compilador es producir código muy eficiente, ya que para hacerlo así se requiere una cantidad importante del análisis de las propiedades del código objetivo, y esto se facilita mediante el uso del código intermedio.
*El código intermedio también puede ser útil al hacer que un compilador sea mas fácilmente re dirigible: si el código intermedio es hasta cierto punto independiente de la maquina objetivo, entonces genera código para una maquina objetivo diferente solo requiere volver a escribir el traductor de código intermedio a código objetivo, y por lo regular esto es mas fácil que volver a escribir todo un generador de código.
*La representación intermedia puede tener diversas formas, se trata una forma intermedia llamada "CÓDIGO DE TRES DIRRECCIONES" y el "CÓDIGO P"
*El código de tres direcciones consiste en una secuencia de instrucciones, cada una de las cuales tiene como máximo tres operadores.

            temp1 := entareal(60)
            temp2 := id3 * temp1
            temp3 := id2 + temp2
            id1 := temp3

Esta representación intermedia tiene varias propiedades.
- primera, cada instrucción de tres direcciones tiene a lo sumo un operador, además de la asignación. Por tanto, cuando genera esas instrucciones, el  compilador tienes de decidir el orden en que deben efectuarse las operaciones; la multiplicación precede a la adicción en el programa fuente.
- segunda, el compilador debe generar un nombre temporal para guardar los valores calculados por cada instrucción.
- tercera, algunas instrucciones de "tres direcciones" tiene menos de tres operadores, por ejemplo, la primera y la ultima instrucción.
                     EL CÓDIGO P
*El código P comenzó como un código ensamblador objetivo estándar producido por varios compiladores Pascal en la década de 1970 y principios de la de 1980. Fue diseñado para código real para una maquina de pila hipotética la idea era hacer que los compiladores de Pascal se transportaran fácilmente requiriendo solo que se volviera a escribir el interprete de la maquina P para una plataforma, el código P también a probado ser útil como código intermedio y sean utilizado varias extensiones y modificaciones del mismo en diverso compiladores de código nativo,
La mayor parte para lenguaje tipo Pascal.

*Como el código P fue diseñado para ser directamente ejecutable, contiene una descripción implícita de un ambiente de ejecución particular que incluye tamaños de datos, además de mucha información especifica para la maquina P, que debe conocer si se desea que un programa de código P se comprensible. La maquina P esta compuesta por una memoria de código, una memoria de datos no específica para variables nombre das y una pila para datos temporales, junto como cualquiera registro que sea necesario para mantener la pila y apoyar la ejecución.

        COMPARACIÓN
*El código P en muchos aspectos está más código de maquina real que al código de tres direcciones. Las instrucciones en código P también requiere menos de tres direcciones: tosas las instrucciones que hemos visto son instrucciones de "una dirección" o "cero direcciones". Por otra parte, el código P es menos compacto que el código de tres direcciones en términos de números de instrucciones, y el código P no esta "auto contenido" en el sentido que las instrucciones funciones implícitas en una pila (y las localidades de pila implícitas son de hecho las direcciones "perdidas"). La ventaja respecto a la pila es que contiene los valores temporales necesarios en cada punto del código, y el compilador no necesita asignar nombre a ninguno de ellos, como el código de tres direcciones.
            Ejemplo
·         — Se puede considerar esta una representación intermedia como un programa para una maquina abstracta.
·         — Traducción de una proposición  
            CÓDIGO DE TRES DIRECCIONES
Las reglas semánticas para generar código de tres direcciones  a partir de construcciones de lenguaje de programación comunes son similares a las reglas para construir arboles sintácticos o para notación posfija.
El código de tres direcciones es una secuencia de preposiciones  de la forma general

x := y op z

Donde 'x', 'y' y 'z' son nombres, constates o variables temporales generadas por el compilador, op representa cualquier valor, como un operador aritmético de punto fijo o flotante, o un operador lógico sobre datos con valores booleanos. Obsérvese que no se permite ninguna expresión aritmética compuesta, pues solo hay un operador en el lado derecho de una proposición. Por tanto, una expresión del lenguaje fuente como x+y*z se puede traducir en una secuencia

t1  :=  y * z
t2 :=  x + t1

Donde t1 y t2 son nombres temporales generados por el compilador.
El código de tres direcciones  es una reprehensión linealizada de un árbol sintáctico o un GDA en la que lo nombres explícitos corresponde a los nodos interiores del grafo.
            t1 := -c                                                                       t1 := -c
            t2 := b * t1                                                                 t2 := b*t1
            t3 := -c                                                                       t5 := t2 + t2
            t4 := b * t3                                                                 a := t5
            t5 := t2 +t4
            a := t5
(a) Código para el árbol sintáctico                      (b) Código para el GDA

Las proposiciones de tres direcciones son análogas al código ensamblador. Las proposiciones pueden tener etiquetas simbólicas y existen proposiciones para el flujo del control. Una etiqueta simbólica representa el índice de una proposición  de tres direcciones en la matriz que contiene código intermedio. Los índices reales se pueden sustituir por las etiquetas ya sea realizado una pasada independiente o mediante "relleno en retroceso".
La notación gen(x ':='  y '+' z) en la figura (1) para representar la proposición de tres direcciones x := y + z
Se puede añadir proposiciones de flujo del control al lenguaje de asignaciones de la figura (1) mediante producciones y reglas semánticas como las de las proposicioneswhile de la figura (2).

1.) Definición dirigida por la sintaxis para producir código de tres direcciones para las asignaciones.

Producción
Reglas semántica
S à id := E
S. Código := E. código || gen (id. lugar ':=' E. lugar)
E à E1 +E2
E. lugar := tempnuevo;
E. código := E1. código || E2. código || gen(E. lugar ':=' E1. lugar '+' E2.lugar)
E à E1 * E2
E. lugar := tempnuevo;
E. código := E1. código || E2. código || gen(E. lugar ':=' E1. lugar '*' E2.lugar)
E à -E1
E. lugar := tempnuevo;
E. código := E1. código || gen('E. lugar ':='  'menosu' E1. lugar)
E à (E1)
E. lugar  := E1. lugar;
E. código := E1. código
E à id
E. lugar := id. lugar;
E. código  := ' ' 



2.) Reglas semánticas que genera código para una proposición while:
IMPLEMENTACIÓN DE CÓDIGO DE TRES DIRECCIONES 
·         — Cuádruplas.
·         — Estructura con 4 campos: operador, operando1, operando2, resultado.
·         — Triplas.
·         — Estructura con 3 campos: operador, operando1, operando2. Los resultados temporales se referecian por la posición en que fueron calculados.
EL CÓDIGO P 
El código P comenzó como un código ensamblador objetivo estándar producido por varios compiladores Pascal en la década de 1970 y principios de la de 1980. la descripción de diversas versiones de código P.
La máquina P está compuesta por una memoria de código, una memoria de datos no especificada  para variables nombradas y una pila para datos temporales, junto cualquier registro que sea necesario para mantener la pila y apoyar la ejecución.
Como primer ejemplo se considera la expresión:
·         — La versión de código P para esta expresión es la que se muestra en seguida:
ldc 2   ; carga la constante 2
lod a   ; carga el valor de la variable a
mpi     ; multiplicación entera
lod b  ; carga el valor de la variable b
ldc 3   ; carga la constante 3
sbi      ; sustracción o resta entera
adi      ; adiciona de enteros

            Esta instrucción se ven  como si representaran las siguientes operaciones en una maquina P.
En primer lugar, ldc 2 inserta el valor 2 en la pila temporal. Luego, lod a inserta el valor de la variable a  en la pila. Las instrucción mpi extrae estos dos valores de la pila, los multiplica (en orden inverso) e inserta el resultado en la pial. Las siguientes dos instrucciones (lod b y ldc 3) inserta valor de b y la constante 3 en la pila (ahora tenemos tres valores en la pila). Posteriormente, la instrucción sbi extrae los dos valores superiores de la pila, resta el primero del segundo, e inserta el resultado. Finalmente, la instrucción adi extrae los dos valores restantes de la pila, los suma e inserta el resultado. El código final con un solo valor en la pila, que representa el resultado del cálculo.

IMPLEMENTACIÓN DEL CÓDIGO P
Históricamente, el código P ha sido en su mayor  parte generado como un archivo de texto, pero las  descripciones anteriores de las implementaciones de estructura de datos internas para el código de tres direcciones (cuádruples  y triples) también funcionara como una modificación propia para el código P.

GENERACION DEL CODIGO PARTIENDO DE LI. ALGORITMOS:
Se sabe que entre el parse y el lenguaje objeto resultado de la compilación, habrá una de estas dos cosas o ambas.
Un lenguaje intermedio LI.
Una generación de código.
Se supone la existencia de ambos componentes, nos hace falta ahora el regresar el código objeto para la maquina objeto deseada, que en el caso normal de no tratarse de un compilador cruzado, es el mismo código con el que está escrito el compilador.
Como ejemplo de las posibilidades existentes se mencionan las de la figura 5 para el lenguaje pascal.
Se emplea in código P para un maquina hipotética que opera con una pila. Este compilador es muy portable de una maquina a otra. Es el método usado en el USCD PASCAL que al estar todo escrito en el código de la maquina ficticia P, sólo se precisa tener un pequeño interprete distinto para cada maquina objeto dada.
Pero la hipotética maquina a pila, ya nos es tan hipotética puesto que ahora existe ya como microprocesador, con lo que el código P se ejecuta directamente.
También es como el primer caso, pero en vez de emplear un interprete, se traduce con un ensamblador para la maquina objeto dada.
El compilador puede dar directamente un módulo cargable para la maquina objeto en cuestión.
El compilador suministra un objeto responsable que se puede montar con otros objetos.

Para dar concreción vamos a definir el conjunto de instrucciones de un ordenador sencillo que tenga sólo un acumulador A y un registro índice X. Una instrucción simbólica con un ensamblador para esta maquina tendría hasta 4 partes separadas entre si por blancos:
-Una parte opcional, la etiqueta.
-El código de operación.
-El operando.
-Comentario opcional.
La forma de direccionar la memoria son las siguientes:
DIRECTA: Se toma como operando el contenido en memoria del campo de dirección.
INDIRECTA: Como antes pero, el contenido de memoria se considera a su vez como dirección del dato.
INMEDIATA: El valor de la dirección lo tomo inmediatamente como operando.
Y salvo en el caso del direccionamiento inmediato, las direcciones pueden ser:Absolutas o reales, Relativas a la instrucción actual, Indexadas con un registro.
TÉCNICAS BÁSICAS DE GENERACIÓN DE CÓDIGO
La generación de código intermedio(o generación de código objetivo directa sin código intermedio), en realidad, si el código generado se ve como un atributo de cadena, entonces este código se convierte en un atributo sintetizado.
Para ver como el código de tres direcciones, o bien, el código P se puede definir como un atributo sintetizado, considere la siguiente gramática que representa un pequeño subconjunto de expresiones en C:

exp à id = exp | aexp
aexp à aexp + factor | factor
factorà (exp)| num | id

El código P considerando el caso de la generación de código P en primer lugar, ya que la gramática con atributos es más simple debido a que no es necesario generar nombres para elementos temporales.


Por ejemplo, la expresión (x=x+3)+4 tiene ese atributo

lda      x
lod      x
ldc      3
adi
stn
ldc      4
adi
  
Gramática con atributos para código de tres direcciones de cadena sintetizada

Regla Gramatical
Reglas Semánticas
exp à id = exp2
exp1.pcode ="lda" ||id.strval++ exp2.pcode++"stn"
exp à aexp
exp. pcode =aexp.pcode
aexp1à aexp2 + factor
 aexp1. pcode = aexp2.pcode ++ factor. pcode ++ "adi"
aexp à factor
aexp. pcode =factor. pcode
factor à (exp)
factor. pcode =exp. pcode
factor à num
factor. pcode = "idc"||num.stval
factor à id
factor. pcode = "lod"||id.strval


Un parse es un procesador de cualquier lenguaje, por ejemplo, los navegadores llevan internamente procesadores de varios lenguajes, html, xhtml, xml, css, javascript, etc.
Los compiladores tienen un procesador de comandos que revisan la sintaxis antes de realizar la compilación.
Así que en general, los parsers o procesadores, son los motores de procesamiento del lenguaje (el que aplique en cada momento).


Analisis Semantico

El analisis semantico se compone de un conjunto de rutinas independientes, llamadas por los analizadores morfológico y sintáctico.
El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticas y preparar la generación de código.
En compiladores de un solo paso, las llamadas a las rutinas semánticas se realizan directamente desde el analizador sintáctico y son dichas rutinas las que llaman al generador de código. El instrumento más utilizado para conseguirlo es la gramática de atributos.
En compiladores de dos o más pasos, el análisis semántico se realiza independientemente de la generación de código, pasándose información a través de un archivo intermedio, que normalmente contiene información sobre el árbol sintáctico en forma linealizada (para facilitar su manejo y hacer posible su almacenamiento en memoria auxiliar).
En cualquier caso, las rutinas semánticas suelen hacer uso de una pila (la pila semántica) que contiene la información semántica asociada a los operandos (y a veces a los operadores) en forma de registros semánticos.

Propagación de atributos

Sea la expresión
    int a,b,c;
    a/(b+c^2)
El árbol sintáctico es:
          /
      ---------
      |       |
      a       +
          ---------
          |       |
          b       ^
              ---------
              |       |
              c       2
De la instrucción declarativa, la tabla de símbolos y el analizador morfológico obtenemos los atributos de los operandos:
          /
      ---------
      |       |
      a       +
     int  ---------
          |       |
          b       ^
         int  ---------
              |       |
              c       2
             int     int
Propagando los atributos obtenemos:
          / int
      ---------
      |       |
      a       + int
     int  ---------
          |       |
          b       ^ int
         int  ---------
              |       |
              c       2
             int     int
Si la expresión hubiera sido
    a/(b+c^-2)
El árbol sintáctico sería el mismo, sustituyendo 2 por -2. Sin embargo, la propagación de atributos sería diferente:
          / real
      ---------
      |       |
      a       + real
     int  ---------
          |       |
          b       ^ real
         int  ---------
              |       |
              c      -2
             int     int
En algún caso podría llegar a producirse error (p.e. si / representara sólo la división entera).
Si la expresión hubiera sido
    int a,b,c,d;
    a/(b+c^d)
El árbol sintáctico sería el mismo, sustituyendo 2 por d. Sin embargo, la propagación de atributos sería incompleta:
          / {int,real}
      ---------
      |       |
      a       + {int,real}
     int  ---------
          |       |
          b       ^ {int,real}
         int  ---------
              |       |
              c       d
             int     int
El analizador semántico podría reducir los tipos inseguros al tipo máximo (real) o utilizar un tipo interno nuevo (ej. arit={int,real}, una unión).
Lo anterior es un ejemplo de propagación bottom-up. La propagación top-down también es posible: lo que se transmite son las restricciones y los tipos de las hojas sirven de comprobación. Por ejemplo, si la división sólo puede ser entera, transmitimos hacia abajo la restricción de que sus operandos sólo pueden ser enteros. Al llegar a d, esa restricción se convierte en que d debe ser positiva. Si no lo es, error.
La implantación de todos los casos posibles de operación con tipos mixtos podría ser excesivamente cara. En su lugar, se parte de operaciones relativamente simples (ej. int+int, real+real) y no se implementan las restantes (ej. int+real, real+int), añadiendo en su lugar operaciones monádicas de cambio de tipo (ej. int->real).
Esta decisión puede introducir ambigüedades. Por ejemplo, sea el programa
    real a;
    int b,c;
    a:=b+c
El árbol sintáctico es:
          :=
      ---------
      |       |
      a       +
    real  ---------
          |       |
          b       c
         int     int
Existen dos conversiones posibles:
          := real                     := real
      ---------                   ---------
      |       |                   |       |
      a       + real              a       + int
    real  ---------             real  ---------
          |       |                   |       |
          b       c                   b       c
         int     int                 int     int
El problema es que no tenemos garantía de que los dos procedimientos sean equivalentes. El segundo puede dar overflow, el primero pérdida de precisión. La definición del lenguaje debe especificar estos casos.
Las transformaciones posibles se pueden representar mediante un grafo cuyos nodos son los tipos de datos y cada arco indica una transformación. Dado un operando de tipo A que se desea convertir al tipo B, se trata de encontrar una cadena de arcos que pase de A a B en el grafo anterior. Podría haber varios grafos, cada uno de los cuales se aplicará en diferentes condiciones, por ejemplo, uno para las asignaciones, otro para las expresiones, etc.

Gramática de atributos

Es una extensión de la notación de Backus que consiste en introducir en las reglas sintácticas ciertos símbolos adicionales no sintácticos (símbolos de acción) que, en definitiva, se reducen a llamadas implícitas o explícitas a rutinas semánticas.
Por ejemplo: sea la gramática simplificada que analiza las instrucciones de asignación:
  <AsSt> ::= id #PId := <Exp> #RAs
  <Exp>  ::= <Exp> + <T> #RS | <T>
  <T>    ::= id #PId | Ct #PCt
Se observará que hemos hecho uso de cuatro símbolos de acción:
  • #PId: PUSH a la pila semántica el registro asociado al identificador.
  • #PCt: PUSH a la pila semántica el registro asociado a la constante.
  • #RS: Realizar suma: POP los dos registros superiores de la pila; comprobar que es posible sumarlos; realizar la suma (mediante una llamada al generador de código) o generar representación intermedia (si es una compilación en dos o más pasos); PUSH registro semántico del resultado en la pila semántica.
  • #RAs: Realizar asignación: POP los dos registros superiores de la pila; comprobar que es posible realizar la asignación; realizarla (mediante una llamada al generador de código) o generar representación intermedia (si es una compilación en dos o más pasos).
En los analizadores sintácticos top-down basados en gramáticas LL(1), la introducción de los símbolos de acción en las rutinas correspondientes es trivial. En los analizadores bottom-up basados en gramáticas SLR(1) es más delicado, pues los estados del análisis se mueven simultáneamente sobre varias reglas. Sólo en el momento de realizar una reducción sabemos exactamente dónde estamos. Por ello, se suele introducir la restricción de que los símbolos de acción deben estar situados únicamente al final de una regla. Cuando no se cumple esto (como en el ejemplo anterior) es trivial conseguirlo, introduciendo símbolos no terminales adicionales. Algunos generadores de analizadores sintácticos (como YACC) lo realizan automáticamente. En nuestro ejemplo, quedaría:
  <AsSt> ::= <ASPI> := <Exp> #RAs
  <ASPI> ::= id #PId
  <Exp>  ::= <Exp> + <T> #RS | <T>
  <T>    ::= id #PId | Ct #PCt
Poner un ejemplo del análisis sintáctico-semántico bottom-up de la instrucción A := B + 1.
Otro ejemplo: instrucciones condicionales con las reglas
    <Instr> ::= If <Expr> #S2 then <Instr> #S1 |
                If <Expr> #S2 then <Instr> else #S3 <Instr> #S1
Más adelante se verá cuáles son las tres acciones semánticas. Para que todas queden al final de una regla, basta cambiar estas reglas por:
    <Instr> ::= If <Expr1> then <Instr> #S1 |
                If <Expr1> then <Instr> <Else> <Instr> #S1
    <Expr1> ::= <Expr> #S2
    <Else>  ::= else #S3

Generación de representaciones intermedias

Existen dos representaciones intermedias principales:
  • Notación sufija
  • Cuádruplas
Los operadores diádicos (o binarios) pueden especificarse mediante tres notaciones principales:
  • Prefija: el operador diádico es analizado antes que sus operandos.
  • Infija: el operador diádico es analizado entre sus operandos.
  • Sufija: el operador diádico es analizado después que sus operandos.
En los lenguajes de programación clásicos, los operadores diádicos se representan usualmente en notación infija. La notación prefija permite al operador influir sobre la manera en que se procesan sus operandos, pero a cambio suele exigir mucha más memoria. La sufija no permite esa influencia, pero es óptima en proceso de memoria y permite eliminar el procesado de los paréntesis.
Los operadores monádicos sólo pueden presentarse en notación prefija o sufija.
Además, un árbol sintáctico puede representarse en forma de tuplas de n elementos, de la forma (operador, operando-1, ..., operando-k, nombre). Las tuplas pueden tener longitud variable o fija (con operandos nulos). Las más típicas son las cuádruplas, aunque éstas pueden representarse también en forma de tripletes.

Notación sufija

Llamada también postfija o polaca inversa, se usa para representar expresiones sin necesidad de paréntesis.
Ejemplos:
   a*b          ab*
   a*(b+c/d)    abcd/+*
   a*b+c*d      ab*cd*+
Los identificadores aparecen en el mismo orden. Los operadores en el de evaluación (de izquierda a derecha).
Problema: operadores monádicos (unarios). O bien se transforman en diádicos (binarios) o se cambia el símbolo.
Ejemplo: -a se convierte en 0-a o en @a
   a*(-b+c/d)   ab@cd/+*
Existen dos problemas principales:
  • Construir la notación sufija a partir de la infija.
  • Analizar la notación sufija en el segundo paso de la compilación.

Rutina semántica para transformar de infijo a sufijo

Si el analizador sintáctico es bottom-up, hacemos la siguiente suposición: "Cuando aparece un no terminal V en el asidero, la cadena polaca correspondiente a la subcadena que se redujo a V ya ha sido generada".
Se utiliza una pila donde se genera la salida, inicialmente vacía. Las acciones semánticas asociadas a las reglas son:
  E ::= E + T           Push +
  E ::= E - T           Push -
  E ::= T
  T ::= T * F           Push *
  T ::= T / F           Push /
  T ::= F
  F ::= i               Push i
  F ::= (E)
  F ::= - F             Push @

Análisis de la notación sufija

La gramática completa que permite analizar la notación sufija es:
  <Operando> ::= id |
                 cte |
                 <Operando> <Operando> <Operador diádico> |
                 <Operando> <Operador monádico>
  <Operador diádico> ::= + | - | * | / | ...
  <Operador monádico> ::= @ | ...
Algoritmo de evaluación de una expresión en notación sufija que utiliza una pila:
  • Si el próximo símbolo es un identificador, se pasa a la pila. Corresponde a la aplicación de la regla
      <Operando> ::= id
  • Si el próximo símbolo es una constante, se pasa a la pila. Corresponde a la aplicación de la regla
      <Operando> ::= cte
  • Si el próximo símbolo es un operador diádico, se aplica el operador a los dos operandos situados en lo alto de la pila y se sustituyen éstos por el resultado de la operación. Corresponde a la aplicación de la regla
      <Operando> ::= <Operando> <Operando> <Operador diádico>
  • Si el próximo símbolo es un operador monádico, se aplica el operador al operando situado en lo alto de la pila y se sustituye éste por el resultado de la operación. Corresponde a la aplicación de la regla
      <Operando> ::= <Operando> <Operador monádico>
Ejemplo: calcular ab@cd/+*.

Extensión de la notación sufija a otros operadores

  • La asignación, teniendo en cuenta que podemos no querer valor resultante. Además, no interesa tener en la pila el valor del identificador izquierdo, sino su dirección.
       a:=b*c+d     abc*d+:=
  • La transferencia (GOTO).
       GOTO L       L TR
  • La instrucción condicional
       if p then inst1 else inst2
    se convierte en
       p L1 TRZ inst1 L2 TR inst2
                        L1:   L2:
  • Subíndices:
       a[exp1; exp2; ...; expn]
    se convierte en
       a exp1 exp2 ... expn SUBIN-n

Cuádruplas

Una operación diádica se puede representar mediante la cuádrupla
  (<Operador>, <Operando1>, <Operando2>, <Resultado>)
Ejemplo:
  (*,A,B,T)
Una expresión se puede representar mediante un conjunto de cuádruplas. Ejemplo: la expresión a*b+c*d equivale a:
  (*,a,b,t1)
  (*,c,d,t2)
  (+,t1,t2,t3)
Ejemplo: la expresión c:=a[i;b[j]] equivale a:
  (*,i,d1,t1)
  (+,t1,b[j],t2)
  (:=,a[t2],,c)

Tripletes

No se pone el resultado, se sustituye por referencias a tripletes. Por ejemplo: la expresión a*b+c*d equivale a:
  (1) (*,a,b)
  (2) (*,c,d)
  (3) (+,(1),(2))
mientras que a*b+1 equivale a:
  (1) (*,a,b)
  (2) (*,(1),1)
Tripletes indirectos: se numeran arbitrariamente los tripletes y se da el orden de ejecución. Ejemplo, sean las instrucciones:
  a := b*c
  b := b*c
Equivalen a los tripletes
  (1) (*,b,c)
  (2) (:=,(1),a)
  (3) (:=,(1),b)
y el orden de ejecución es (1),(2),(1),(3). Esta forma es útil para preparar la optimización de código. Si hay que alterar el orden de las operaciones o eliminar alguna, es más fácil hacerlo ahí.

Generación automática de cuádruplas

En un análisis bottom-up, asociamos a cada símbolo no terminal una información semántica, y a cada regla de producción una acción semántica. Ejemplo, sea la gramática
  E ::= E + T
  E ::= E - T
  E ::= T
  T ::= T * F
  T ::= T / F
  T ::= F
  F ::= i
  F ::= (E)
  F ::= -F
La regla F::=i asocia a F como información semántica el identificador concreto.
La regla F::=(E) asocia a F como información semántica la información semántica asociada a E.
La regla U::=V asocia a U como información semántica la información semántica asociada a V.
La regla U::=VoW analiza la compatibilidad de los operandos, crea la cuádrupla (o,Sem(V),Sem(W),Ti) y asocia a U la información semántica Ti.
La regla U::=oV crea la cuádrupla (o,Sem(V),,Ti) y asocia a U la información semántica Ti.
La información semántica se suele almacenar en otra pila paralela.
Ejemplo: análisis de a*(b+c)
  Pila             Entrada         Regla        Cuádrupla
  -----------      -------------   ------------ ---------
  |                a*(b+c)|
  |a               *(b+c)|         F::=i
  |F(a)            *(b+c)|         T::=F
  |T(a)            *(b+c)|
  |T(a)*           (b+c)|
  |T(a)*(          b+c)|
  |T(a)*(b         +c)|            F::=i
  |T(a)*(F(b)      +c)|            T::=F
  |T(a)*(T(b)      +c)|            E::=T
  |T(a)*(E(b)      +c)|
  |T(a)*(E(b)+     c)|
  |T(a)*(E(b)+c    )|              F::=i
  |T(a)*(E(b)+F(c) )|              T::=F
  |T(a)*(E(b)+T(c) )|              E::=E+T
  |T(a)*(E(b)+T(c) )|              E::=E+T      (+,b,c,T1)
  |T(a)*(E(T1)     )|
  |T(a)*(E(T1))    |               F::=(E)
  |T(a)*F(T1)      |               T::=T*F      (*,a,T1,T2)
  |T(T2)           |               E::=T
  |E(T2)           |

Ejemplo de generación de cuádruplas en análisis top-down

  unsigned int E (char *cadena, unsigned int i)
  {
    if (i<0) return i;
    switch (cadena[i]) {
      case 'i':
        push (id);
        i++;
        i = V (cadena, i);
        break;
      case '(':
        i++;
        i = E (cadena, i);
        i = C (cadena, i);
        i = V (cadena, i);
        break;
      default: return -1;
        }
    return i;
  }

  unsigned int V (char *cadena, unsigned int i)
  {
    unsigned int j;
    if (i<0) return i;
    switch (cadena[i]) {
      case '*':
      case '/':
        j = i;
        i++;
        i = T (cadena, i);
        cuad (cadena[j], pop(), pop(), gen(Ti));
        push (Ti);
        i = X (cadena, i);
        break;
      case '+':
      case '-':
        j = i;
        i++;
        i = E (cadena, i);
        cuad (cadena[j], pop(), pop(), gen(Ti));
        push (Ti);
        break;
        }
    return i;
  }

  unsigned int X (char *cadena, unsigned int i)
  {
    unsigned int j;
    if (i<0) return i;
    switch (cadena[i]) {
      case '+':
      case '-':
        j = i;
        i++;
        i = E (cadena, i);
        cuad (cadena[j], pop(), pop(), gen(Ti));
        push (Ti);
        break;
        }
    return i;
  }

  unsigned int T (char *cadena, unsigned int i)
  {
    if (i<0) return i;
    switch (cadena[i]) {
      case 'i':
        push (id);
        i++;
        i = U (cadena, i);
        break;
      case '(':
        i++;
        i = E (cadena, i);
        i = C (cadena, i);
        i = U (cadena, i);
        break;
      default: return -2;
        }
    return i;
  }

  unsigned int U (char *cadena, unsigned int i)
  {
    if (i<0) return i;
    unsigned int j;
    switch (cadena[i]) {
      case '*':
      case '/':
        j = i;
        i++;
        i = T (cadena, i);
        cuad (cadena[j], pop(), pop(), gen(Ti));
        push (Ti);
        break;
        }
    return i;
  }

  unsigned int F (char *cadena, unsigned int i)
  {
    if (i<0) return i;
    switch (cadena[i]) {
      case 'i':
        push (id);
        i++;
        break;
      case '(':
        i++;
        i = E (cadena, i);
        i = C (cadena, i);
        break;
      default: return -3;
        }
    return i;
  }

  unsigned int C (char *cadena, unsigned int i)
  {
    if (i<0) return i;
    switch (cadena[i]) {
      case ')':
        i++;
        break;
      default: return -4;
        }
    return i;
  }

Semántica de instrucciones condicionales

Sean las reglas
    <Instr> ::= If <Expr> S2 then <Instr> S1 |
                If <Expr> S2 then <Instr> else S3 <Instr> S1
Una secuencia de cuádruplas equivalente a "If E1 then I1 else I2"
 (p-1)  (?,?,?,t1)         Análisis de E1
 (p)    (TRZ,(q+1),t1,)    S2: Crear cuádrupla (p) | Push p
        ...                Análisis de I1
 (q)    (TR,(r),,)         S3: Crear cuádrupla (q)
                               Poner (cl.sig.) en top | Pop
                               Push (q)
 (q+1)  ...                Análisis de I2
 (r)                       S1: Poner (cl.sig.) en top | Pop
Una secuencia de cuádruplas equivalente a "If E1 then I1"
 (p-1)  (?,?,?,t1)         Análisis de E1
 (p)    (TRZ,(r),t1,)      S2: Crear cuádrupla (p) | Push p
        ...                Análisis de I1
 (r)                       S1: Poner (cl.sig.) en top | Pop
Al generar la cuádrupla (p) no conocemos el valor de (q). Guardamos en una pila el número de la cuádrupla asociada y lo rellenamos más tarde, como indican los ejemplos.

Semántica de etiquetas y GOTO

Suponemos que las etiquetas aparecen en la tabla de símbolos con tres valores asociados: (tipo=etiqueta, bit=declarada/no declarada, número de cuádrupla).
Sea la regla
    <Instr> ::= id : <Instr>
Semántica asociada:
  {
  Buscar id en la tabla de símbolos;
  if (no está)
    Insertar id,valor=(etiqueta, declarada, cuádrupla siguiente);
  else {
    if (tipo==etiqueta && bit==no declarada) {
      i=número de cuádrupla;
      while (i) {
        j=cuádrupla[i][2];
        cuádrupla[i][2]=cuádrupla siguiente;
        i=j;
        }
      Cambiar valor a (etiqueta, declarada, cuádrupla siguiente);
      }
    else error();
    }
  }
Sea la regla
    <Instr> ::= GOTO id
Semántica asociada:
  {
  Buscar id en la tabla de símbolos;
  if (no está) {
    Insertar id,valor=(etiqueta, no declarada, cuádr.siguiente);
    Generar cuádrupla (TR,,,);
    }
  else {
    if (tipo==etiqueta) {
      if (bit==declarada)
        Generar cuádrupla (TR,número de cuádrupla,,);
      else if (bit==no declarada) {
        i=número de cuádrupla;
        Cambiar valor a (etiqueta, no declarada, cuádr.siguiente);
        Generar cuádrupla (TR,i,,);
        }
      }
    else error();
    }
  }
Si se permiten etiquetas locales a bloques, podemos encontrar el siguiente caso:
    L:  ...
        {
          ...
          GOTO L;
          ...
Tenemos ambigüedad: GOTO L puede ir a la etiqueta externa (ya definida o no) o a una etiqueta local al bloque posterior a la instrucción. Tenemos tres posibilidades:
  • Un compilador en dos pasos.
  • Forzar declaraciones de etiquetas.
  • Tratar L en el bloque como si fuera local. Si al final del bloque descubrimos que no ha sido declarada, tratarla como si fuera global. La lista de referencias debería fundirse con la de L global (si L global no ha sido definida aún) o rellenarse con el valor de L (si ya ha sido definida). Si L global no existe, debe crearse, y pasarle la lista de referencias de L local.

Semántica de bloques

Sean las reglas
    <Instr> ::= do <id> := <Expr> S1
                , <Expr> S2
                <CD1> <LInstr> end S5
    <CD1>   ::= , <Expr> S3 | ^ S4
Semántica asociada al análisis de "do x:=n1,n2,n3; I1; I2; end":
  • S1:
        Generar cuádruplas asociadas a instrucción de asignación x:=n1.
    Guardar i=número de cuádrupla siguiente.
  • S2:
        Guardar j=número de cuádrupla siguiente.
    Generar cuádrupla (TRG,,x,(n2)).
    Generar cuádrupla (TR,,,).
  • S3:
        Generar cuádrupla (+,x,(n3),x).
    Generar cuádrupla (TR,(i),,).
    Hacer cuádrupla[j+1][2]=cuádrupla siguiente.
  • S5:
        Generar cuádrupla (TR,(j+2),,).
    Hacer cuádrupla[j][2]=cuádrupla siguiente.
Además, S4:
    Generar cuádrupla (:=,x,1,x).
    Generar cuádrupla (TR,(i),,).
    Hacer cuádrupla[j+1][2]=cuádrupla siguiente.

Evaluación óptima de las expresiones booleanas

Las operaciones booleanas usualmente se definen así:
   O | T  F   Y | T  F   NO| T  F
   --|-----   --|-----   --|-----
   T | T  T   T | T  F     | F  T
   F | T  F   F | F  F
y la sintaxis adecuada para que la precedencia sea: NO, Y, O. Sin embargo, es posible simplificarlas considerablemente. Basta fijarse en la expresión
   a Y (b O NO c)
Si a es falso, no hace falta calcular el paréntesis, sabemos que el resultado es falso. Por tanto, redefiniremos la sintaxis y la semántica así:
  <ZB> ::= <EB>
  <EB> ::= <TB> O <EB> | <TB>
  <TB> ::= <FB> Y <TB> | <FB>
  <FB> ::= i | ( <EB> ) | NO <FB>

  a O b <=> if (a) TRUE else b;
  a Y b <=> if (a) b else FALSE;
  NO a  <=> if (a) FALSE else TRUE;

Análisis top-down

El programa queda:
  void ZB (char *cadena)
  {
    int FL=0, TL=0, i;
    cuad (":=", "T", NULL, x);
    i = EB (cadena, 0, &FL, &TL);
    FILL (FL);
    cuad (":=", "F", 0, x);
    FILL (TL);
  }

  unsigned int EB (char *cadena, unsigned int i, int *FL, int *TL)
  {
    int tl=0;
    i = TB (cadena, i, FL, &tl);
    MERGE (TL, tl);
    if (i<strlen(cadena)) switch (cadena[i]) {
      case 'O':
        i++;
        FILL (*FL);
        *FL = 0;
        i = EB (cadena, i, FL, TL);
        break;
      default:
        break;
        }
    return i;
  }

  unsigned int TB (char *cadena, unsigned int i, int *FL, int *TL)
  {
    int fl=0;
    i = FB (cadena, i, &fl, TL);
    MERGE (FL, fl);
    if (i<strlen(cadena)) switch (cadena[i]) {
      case 'Y':
        i++;
        FILL (*TL);
        *TL = 0;
        i = TB (cadena, i, FL, TL);
        break;
      default:
        break;
        }
    return i;
  }

  unsigned int FB (char *cadena, unsigned int i, int *FL, int *TL)
  {
    if (i<strlen(cadena)) switch (cadena[i]) {
      case 'i':
        i++;
        *TL = cuádrupla siguiente;
        *FL = - cuádrupla siguiente;
        cuad (TRB, id, 0, 0);
        break;
      case '(':
        i++;
        i = EB (cadena, i, FL, TL);
        i = C (cadena, i);
        break;
      case 'NO':
        i++;
        i = FB (cadena, i, FL, TL);
        *FL <-> *TL
        break;
      default: error (cadena, i);
        }
    else error (cadena, i);
    return i;
  }

  unsigned int C (char *cadena, unsigned int i)
  {
    if (i<strlen(cadena)) switch (cadena[i]) {
      case ')':
        i++;
        break;
      default: error (cadena, i);
        }
    else error (cadena, i);
    return i;
  }

  void FILL (int lista)
  {
    int i,j,n;
    n = lista;
    while (n) {
      if (n>0) i=2; else i=3;
      j = abs (n);
      n = cuad[j][i];
      cuad[j][i] = cuádrupla siguiente;
      }
  }

  void MERGE (int *uno, int dos)
  {
    int i,k;
    if (*uno==0) *uno = dos;
    else {
      k = *uno;
      for (;;) {
        if (k>0) i=2; else i=3;
        k = abs (k);
        if (cuad[k][i]==0) break;
        k = quad[k][i];
        }
      cuad[k][i] = dos;
      }
  }
Analicemos "a O b O NO c"
  ZB ("a O b O NO c")
    cuad (":=", "T", NULL, "X");
    i = EB ("a O b O NO c", 0, &FL, &TL);
      i = TB ("a O b O NO c", 0, FL, &tl);
        i = FB ("a O b O NO c", 0, &fl, TL);
          case id:
            i=1;
            *TL = 1;
            fl = -1;
            cuad (TRB, a, 0, 0);
        MERGE (FL, fl);
          FL = -1;
      MERGE (TL, tl);
          TL = 1;
      case 'O':
        i=2;
        FILL (FL);
          n = -1;
          while (n) {
            i = 3;
            j = 1; (abs(FL))
            n = 0; (cuad[1][3])
            cuad[1][3] = 2;
            }
        FL = 0;
        i = EB ("a O b O NO c", 2, FL, TL);
          i = TB ("a O b O NO c", 2, FL, &tl);
            i = FB ("a O b O NO c", 2, &fl, TL);
              case 'i':
                i=3;
                *TL = 2;
                *fl = -2;
                cuad (TRB, b, 0, 0);
            MERGE (FL, fl);
              FL = -2;
          MERGE (TL, tl);
            k = 1;
            for (;;) {
              i = 2;
              k = 1;
              }
              cuad[1][2] = 2;
          case 'O':
            i=4;
            FILL (FL);
              n = -2;
              while (n) {
                i = 3;
                j = 2;  (abs (n))
                n = 0;  (cuad[2][3])
                cuad[2][3] = 3;
                }
            FL = 0;
            i = EB ("a O b O NO c", 4, FL, TL);
              i = TB ("a O b O NO c", 4, FL, &tl);
                i = FB ("a O b O NO c", 4, &fl, TL);
                  case 'NO':
                    i=5;
                    i = FB ("a O b O NO c", 5, FL, TL);
                      case 'i':
                        i=6;
                        *TL = 3;
                        *FL = -3;
                        cuad (TRB, c, 0, 0);
                    FL <-> TL
                MERGE (FL, fl);
                  FL = 3;
              MERGE (TL, tl);
                k = 1;
                for (;;) {
                  i = 2;
                  k = 1;  (abs (k))
                  k = 2;  (cuad[1][2])
                  }
                cuad[2][2] = -3;
    FILL (FL);
      cuad[3][2] = 4;
    cuad (":=", "F", 0, "X");
    FILL (TL);
      cuad[1][2] = 5;
      cuad[2][2] = 5;
      cuad[3][3] = 5;
Cuádruplas obtenidas:
  0: (":=", "T",, x);
  1: ("TRB", a, 5, 2);
  2: ("TRB", b, 5, 3);
  3: ("TRB", c, 4, 5);
  4: (":=", "F",, x);
  5:

Analisis Sintactico

GLC.
Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X → α, donde X es una variable y α es una cadena que puede contener variables y constantes. Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”)
  • Capturan la noción de constituyente sintáctico y la noción de orden.
  • Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurador.
  • Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.
Una Gramática Libre de Contexto es una tupla con 4 parámetros:
  • G = (V, T, P, S)
  • V – conjunto de símbolos variables
  • T – conjunto de símbolos terminales
  • S Є V, símbolo inicial
  • P – conjunto de reglas de producción: A → α, con α sucesión de símbolos de V U T, eventualmente vacía (α = ε)
Una GLC es un dispositivo generador.
Definimos el lenguaje LG generado por una gramática G del siguiente modo: G = { w / S →* w } , siendo ⇒* una “especie” de clausura transitiva de → y w una tira de terminales
Árbol de derivación.
Es una representación gráfica (en forma de árbol invertido) de un proceso de derivación en una gramática. Se define el árbol de derivación como sigue:
  • la raíz del árbol será el símbolo inicial de la gramática
  • los nodo interiores del árbol están etiquetados por los símbolos no terminales
  • las hojas están etiquetadas por símbolos terminales
  • si un nodo interior etiquetado por A, posee como hijos los nodos etiquetados por X1,X2, …Xn , entonces A→ X1,X2, …Xn es una producción de la gramática, en donde Xi , representa símbolo terminal o no terminal.
Sea la siguiente gramática:
G=( Σ={a, b}, N={S,A,B},S P ) P: S→aABAa , A→ε |aA , B→ε|bB la construcción de un árbol de derivación en el proceso de la generación de la palabra aa es el siguiente:
Propiedades de un árbol de derivación.

Sea G = (N, T, S, P) una gramática libre de contexto, sea A Є N una variable. Diremos que un árbol TA= (N, E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes:
  • La raíz del árbol es un símbolo no terminal
  • Cada hoja corresponde a un símbolo terminal o λ.
  • Cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena.
Árbol de derivación.

Ejemplo:

Sea G=(N, T, S, P) una GLC con P: S→ ab|aSb

La derivación de la cadena aaabbb será: S → aSb → aaSbb → aaabbb y el árbol de derivación:
Formas normales de Chomsky.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:

A → BC o
A → a o

donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.

Sea G = (∑ N, ∑T, P, $) una gramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:
Variables accesibles:
  • Si existe una derivación desde el símbolo inicial que contiene X, es decir, existe $ → * α Xβ donde α, β Є∑*
Variables generativas:
  • Si existe una derivación desde el la variable que produce una sentencia , es decir, existe X →* ω donde ω Є *T.
Variables útiles:
  • Si existe una derivación desde el símbolo inicial usando que produce una sentencia ω, es decir, existe $ →* α X β →*ω donde α, β Є ∑* y ω Є ∑*T.
6.4 Diagramas de sintaxis

Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF, por sus siglas en inglés) o la Forma Extendida de Backus-Naur (EBNF, por sus siglas en ingles).

Los diagramas de ferrocarril son más comprensibles para la mayoría de la gente. Alguna parte de la popularidad del formato de intercambio de datos JSON se debe a su representación en los diagramas de ferrocarril.

Un segundo método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Ésta es una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama. En la figura 10.5 se ilustrará los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF.

Eliminación de la ambigüedad

Una GLC es ambigua si existe una cadena w Є L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más arboles de derivación .

En casi de y que toda cadena w Є L (G) tenga un único árbol de derivación no es ambigua.

Ejemplo: La gramática S → aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda S Þ aS Þ aa S Þ Sa Þ aa.
Tipos de Ambigüedad

Dentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

Ambigüedad Inherente:

Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan:

Un lenguaje L es inherentemente ambiguo si todas sus gramáticas; si existe cuando menos una gramática no ambigua para L, L no es ambiguo.
  • El lenguaje de las expresiones no es Ambiguo
  • Las expresiones regulares no son ambiguas
Ejemplo de un lenguaje inherentemente ambiguo:
La gramática es ambigua: hay cadenas con más de una derivación más izquierda:


6.6 Generación de matriz predictiva (cálculo first y follow)
FIRST: Sea G := (V; ∑; Q0; P) una gramática libre de contexto. Para cada forma sentencial α Є (V U ∑)* y para cada k Є N definiremos la función.

En otras palabras, el operador F IRST k asocia a cada forma sentencial los primeros k símbolos de cualquier forma terminal alcanzable desde α mediante derivaciones “masa la izquierda".

FOLLOW: Con las mismas notaciones anteriores, para cada forma sentencial α Є (V U ∑)*  definiremos la función FOLLOWG GK (α) del modo siguiente.
De nuevo nos ocuparemos solamente de FOLLOW: = FOLLOW1. Obsérvese que FOLLOW k (α) ⊂ ∑* y que para cada x Є FOLLOW (α), Ixl ≤ k. Obsérvese que para cada variable A Є V, FOLLOW(A) son todos los símbolos terminales que pueden aparecer a la derecha de A en alguna forma sentencial de la gramática.

Tipos de analizadores sintácticos

Analizador Descendente:

Se construye el árbol de análisis sintético partiendo del símbolo inicial y aplicando las producciones mediante derivaciones por la izquierda, el símbolo a expandir es el que esta mas a la izquierda.

Analizador Ascendente:

Se construye el árbol de análisis sintético partiendo de la frase a reconocer y aplicando las producciones mediante reducciones hasta llegar al símbolo inicial de la gramática.
Ejemplo:

G= ({+,*, ID, (,)}, {E, T, P},E, P)P={E:=E+T | T; T:=T*P | P; P:= ID | (E) }FraseID + ( ID * ID )

Ejemplo:

G= ({+,*, ID, (,)}, {E, T, P},E, P)P={E:=E+T | T; T:=T*P | P; P:= ID | (E) }FraseID + ( ID * ID )
Manejo de errores.

Un compilador es un sistema que en la mayoría de los casos tiene que manejar una entrada incorrecta. Sobre todo en las primeras etapas de la creación de un programa, es probable que el compilador se utiliza para efectuar las características que debería proporcionar un buen sistema de edición dirigido por la sintaxis, es decir, para determinar si las variables han sido declaradas antes de usarla, o si faltan corchetes o algo así.

Por lo tanto, el manejo de errores es parte importante de un compilador y el escritor del compilador siempre debe tener esto presente durante su diseño.

Hay que señalar que los posibles errores ya deben estar considerados al diseñar un lenguaje de programación. Por ejemplo, considerar si cada proposición del lenguaje de programación comienza con una palabra clave diferente (excepto la proposición de asignación, por supuesto). Sin embargo, es indispensable lo siguiente:

El compilador debe ser capaz de detectar errores en la entrada;
  • El compilador debe recuperarse de los errores sin perder demasiada información;
  • Y sobre todo, el compilador debe producir un mensaje de error que permita al programador encontrar y corregir fácilmente los elementos (sintácticamente) incorrectos de su programa.
Errores Sintácticos.

Muchos errores de naturaleza sintáctica Recuperación: Al producirse un error el compilador debe ser capaz de informar del error y seguir compilando. (Ideal).

El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:
  • Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.
  • Recuperarse del error, para poder seguir examinando la entrada.
  • No ralentizar significativamente la compilación.
Un buen compilador debe hacerse siempre teniendo también en mente los errores que se pueden producir; con ello se consigue:
  • Simplificar la estructura del compilador.
  • Mejorar la respuesta ante los errores.
Errores semánticos.
Un lenguaje con comprobación fuerte de tipos es capaz de garantizar que los programas se pueden ejecutar sin errores de tipo, por lo que los errores de tipo se detectarán siempre en tiempo de compilación.
Como mínimo, ante un error, un comprobador de tipos debe informar de la naturaleza y posición del error y recuperarse para continuar con la comprobación del resto del programa a analizar.

Veamos algunas de las operaciones a tener en cuenta en una comprobación de tipos:
  • Conversión de tipos: A veces es necesario transformar el tipo de una expresión para utilizar correctamente un operador o para pasar de forma adecuada un parámetro a una función.
  • Coerción: Es una conversión de tipos que realiza de forma implícita el propio compilador. Si es el programador el que realiza la conversión se tratará entonces de una conversión explícita.
  • Sobrecarga de operadores: La sobrecarga se resuelve determinando el tipo de cada una de las expresiones intervinientes en la sobrecarga.
  • Funciones polimórficas: Son aquellas que trabajan con argumentos cuyo tipo puede cambiaren distintas llamadas a la función.
Generadores de analizadores sintácticos

ANTLR:
(ANother Tool for Language Recognition; en español "otra herramienta para reconocimiento de lenguajes") es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes de programación).

GNU bison:
Es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores léxicos se pueden también obtener de otras formas.

Grammatica:
Es un generador de analizadores sintácticos de C# y Java libre. Es similar a otras herramientas como Yacc o ANTLR. Grammatica soporta el algoritmo LL(k) para gramáticas con un número ilimitado de tokens de anticipación. Está bastante bien probado, y ha sido auto compilado desde la versión 0.1. La documentación contiene una lista completa de características, así como una comparación con otros generadores de analizadores.

JavaCC:
(Java Compiler Compiler) es un generador de analizadores sintácticos de código abierto para el lenguaje de programación Java. JavaCC es similar a Yacc en que genera un parser para una gramática presentada en notación BNF, con la diferencia de que la salida es en código Java. A diferencia de Yacc, JavaCC genera analizadores descendentes (top-down), lo que lo limita a la clase de gramáticas LL (K) (en particular, la recursión desde izquierda no se puede usar). El constructor de árboles que lo acompaña, JJTree, construye árboles de abajo hacia arriba (bottom-up).

Yacc:
Es un programa para generar analizadores sintácticos. Las siglas del nombre significan Yet Another Compiler-Compiler, es decir, "Otro generador de compiladores más". Genera un analizador sintáctico (la parte de un compilador que comprueba que la estructura del código fuente se ajusta a la especificación sintáctica del lenguaje) basado en una gramática analíticaescrita en una notación similar a la BNF. Yacc genera el código para el analizador sintáctico en el Lenguaje de programación C.
Suscribirse a: Comentarios (Atom)