Generación de código intermedio

Generador de código intermedio.

• La administración de la memoria se da en esta etapa. 

• Se debe considerar tanto la memoria estática como dinámica, y en esta se utilizan generalmente pilas.

• Los lenguajes intermedios generalmente tienen árboles de derivación más pequeños que su contraparte original. 

• Se puede representar un árbol sintáctico con un Grafo Dirigdo Acíclico (GDA). 

• La notación postfija es una manera linealizada de representar un árbol sintáctico.

• a := b*-c+b*-c 

• abc -*bc -*+= 

• x := y op z 

• x+y*z 

• t1:=y*z 

• t2:=x+t1

Lenguajes intermedios.

• Los lenguajes intermedios nos sirven para representar la producción final de nuestro lenguaje fuente. 

• Existen muchos lenguajes intermedios, la mayoría de ellos son una representación más simplificada del código original para facilitar la traducción hacia el código final.

• Otros lenguajes intermedios sirven de base o como representación parcial de otros procesos. 

• Por ejemplo al compilar un programa en C en Windows o DOS, se produce un código objeto con extensión .obj para que posteriormente el enlazador cree finalmente el código executable .exe

• En sistemas basados en Unix, también ocurre algo similar generándose un archivo .o y el executable a.out.

• Otros lenguajes intermedios famosos son los generados para la máquina virtual de Java el bytecode; y para la máquina virtual de .NET el MISL para luego ejecutarse en tiempo de ejecución JIT (Just in Time).

• Otros lenguajes intermedios se utilizan en sistemas distribuidos como RPC, CORBA y su IDL, etc. • En este caso estos lenguajes intermedios se encargan de enmascarar toda la heterogeneidad de las comunicaciones distribuidas en una computadora.

Notaciones.

• Las notaciones sirven de base para expresar sentencias bien definidas. 

• El uso más extendido de las notaciones sirve para expresar operaciones aritméticas. 

• Las expresiones aritméticas se pueden expresar de tres formas distintas: infija, prefija y postfija.

• La diversidad de notaciones corresponde en que para algunos casos es más sencillo un tipo de notación. 

• Las notaciones también dependen de cómo se recorrerá el árbol sintáctico, el cual puede ser en inorden, preorden o postorden; teniendo una relación de uno a uno con la notación de los operadores.

Infija.

• La notación infija es la más utilizada por los humanos por que es la más comprensible ya que ponen el operador entre los dos operandos. Por ejemplo a+b-5. 

• No existe una estructura simple para representar este tipo de notación en la computadora por esta razón se utilizan otras notaciones.

Postfija.

• La notación postfija pone el operador al final de los dos operandos, por lo que la expresión queda: ab+5- 

• La notación posftfija utiliza una estructura del tipo LIFO (Last In First Out) pila, la cual es la más utilizada para la implementación.

Prefija.

• La notación prefija pone el operador primero que los dos operandos, por lo que la expresión anterior queda: +ab-5. Esto se representa con una estructura del tipo FIFO (First In First Out) o cola. 

• Las estructuras FIFO son ampliamente utilizadas pero tienen problemas con el anidamiento aritmético.

Representación de código intermedio.

• Existen maneras formales para representar código intermedio. 

• Estas notaciones simplifican la traducción de nuestro código fuente a nuestro código objeto ya que ahorran y acotan símbolos de la tabla de símbolos.

Notación Polaca.

La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables.

El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda.

Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta.

Por ejemplo, el axioma de no contradicción, que en notación estándar escribimos ¬(p ∧ ¬ p), en notación polaca lo expresaríamos así: NKpNp.

Conectivas en notación polaca.

Tradicionalmente, la notación polaca usa letras mayúsculas para expresar conectivas, tomando normalmente la primera letra del nombre de la conectiva en polaco. Aquí tenemos una lista con los símbolos más comunes:

Conectiva	Notación estándar	Notación polaca
Negación	¬	N
Implicación	→	C
Conjunción	∧	K
Disyunción	∨	A
Bicondicional	↔	E
Posibilidad	⋄	M
Necesidad	◻	L
Cuantificador universal	∀	Π
Cuantificador existencial	∃	Σ

Definición de fórmula bien formada en notación polaca.

Tomando la lista anterior de conectivas en notación polaca más un conjunto de variables proposicionales como alfabeto de un lenguaje, tenemos la siguiente definición recursiva de fórmula bien formada en dicho lenguaje:

• Sea α una variable proposicional. α es una fórmula bien formada.
• Sean α, β fórmulas bien formadas. Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα son fórmulas bien formadas.

Método para traducir una fórmula en notación estándar a notación polaca.

(1) Buscamos la conectiva principal y escribimos la equivalente en notación polaca.

(2) Si la conectiva es unaria, tomamos su argumento como una subfórmula y aplicamos (1).

(3) Si la conectiva es binaria, (3a) tomamos el primer argumento y aplicamos (1), a continuación tomamos el segundo argumento y aplicamos (1).

(4) Si el símbolo es una variable proposicional, la escribimos a continuación.

El procedimiento acaba en un número finito de pasos dado que en sucesivas aplicaciones de (1) la complejidad de la fórmula disminuye. Si se trata de una fórmula bien formada, el procedimiento acabará por darnos otra fórmula bien formada en notación polaca. Baste esta descripción para mostrar el carácter formal del procedimiento.

En la práctica, resultaría tedioso aplicar este procedimiento paso por paso. Resulta más adecuado entender la mecánica por medio de ejemplos y aplicarla directamente; con cierto entrenamiento la traducción se hace de manera casi automática.

Como ejemplo de este procedimiento vamos a utilizar una instancia de la ley de De Morgan, que en notación estándar escribiríamos así: ¬(p ∧ q) → (¬p ∨ ¬q). En este ejemplo la conectiva principal es la implicación, una conectiva binaria, cuyos argumentos tienen como conectiva principal la negación y la disyunción respectivamente. Tendremos que traducir las sucesivas subfórmulas hasta las variables variables proposicionales.

Notación estándar	Notación polaca	Operación
¬(p ∧ q) → (¬p ∨ ¬q)	C	(1), (3)
¬(p ∧ q) → (¬p ∨ ¬q)	C_____ _____	(3a)
¬(p ∧ q)	CN	(1)
¬(p ∧ q)	CN____	(2)
p ∧ q	CNK_ _	(1), (3)
p ∧ q	CNKp	(3a), (4)
p ∧ q	CNKpq	(3b), (4)
¬(p ∧ q) → (¬p ∨ ¬q)	CNKpq_____	(3b)
¬p ∨ ¬q	CNKpqA__ __	(1), (3)
¬p ∨ ¬q	CNKpqA__ __	(3a)
¬p	CNKpqAN_	(1), (2)
¬p	CNKpqANp	(4)
¬p ∨ ¬q	CNKpqANp__	(3b)
¬q	CNKpqANpN_	(1), (2)
¬q	CNKpqANpNq	(4)

Código de Conversión de Infija a Prefija:


package convers_infija_prefija;

public class ExpresionAritmeticaGui extends javax.swing.JFrame {

    /**
     * Creates new form ExpresionAritmeticaGui
     */
    public ExpresionAritmeticaGui() {
        initComponents();
        this.setLocationRelativeTo(null);
    }

    @SuppressWarnings("unchecked")
    // <editor-fold defaultstate="collapsed" desc="Generated Code">                         
    private void initComponents() {

        botonAPrefijo = new javax.swing.JButton();
        jLabel1 = new javax.swing.JLabel();
        Infijo = new javax.swing.JTextField();
        salir = new javax.swing.JButton();
        resultado = new javax.swing.JTextField();

        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
        setTitle("Expresiones Aritmeticas");

        botonAPrefijo.setBackground(new java.awt.Color(102, 102, 102));
        botonAPrefijo.setText("CONVERTIR");
        botonAPrefijo.setBorder(new javax.swing.border.LineBorder(new java.awt.Color(51, 51, 51), 4, true));
        botonAPrefijo.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                botonAPrefijoActionPerformed(evt);
            }
        });

        jLabel1.setFont(new java.awt.Font("Tahoma", 1, 18)); // NOI18N
        jLabel1.setText("Conversión de Infija a Prefija");

        Infijo.setFont(new java.awt.Font("Arial", 0, 14)); // NOI18N
        Infijo.setHorizontalAlignment(javax.swing.JTextField.CENTER);
        Infijo.setBorder(javax.swing.BorderFactory.createTitledBorder(null, "Infija", javax.swing.border.TitledBorder.DEFAULT_JUSTIFICATION, javax.swing.border.TitledBorder.DEFAULT_POSITION, new java.awt.Font("Tahoma", 3, 12), new java.awt.Color(51, 51, 51))); // NOI18N
        Infijo.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                InfijoActionPerformed(evt);
            }
        });

        salir.setBackground(new java.awt.Color(153, 153, 153));
        salir.setText("SALIR");
        salir.setBorder(new javax.swing.border.LineBorder(new java.awt.Color(51, 51, 51), 4, true));
        salir.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                salirActionPerformed(evt);
            }
        });

        resultado.setEditable(false);
        resultado.setFont(new java.awt.Font("Arial", 0, 14)); // NOI18N
        resultado.setHorizontalAlignment(javax.swing.JTextField.CENTER);
        resultado.setBorder(javax.swing.BorderFactory.createTitledBorder(null, "Prefija", javax.swing.border.TitledBorder.DEFAULT_JUSTIFICATION, javax.swing.border.TitledBorder.DEFAULT_POSITION, new java.awt.Font("Tahoma", 3, 12), new java.awt.Color(51, 51, 51))); // NOI18N

        javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
        getContentPane().setLayout(layout);
        layout.setHorizontalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(layout.createSequentialGroup()
                .addGap(48, 48, 48)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addGroup(layout.createSequentialGroup()
                        .addComponent(resultado, javax.swing.GroupLayout.DEFAULT_SIZE, 262, Short.MAX_VALUE)
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)
                        .addComponent(salir, javax.swing.GroupLayout.PREFERRED_SIZE, 47, javax.swing.GroupLayout.PREFERRED_SIZE)
                        .addGap(8, 8, 8))
                    .addComponent(jLabel1)
                    .addComponent(Infijo, javax.swing.GroupLayout.PREFERRED_SIZE, 260, javax.swing.GroupLayout.PREFERRED_SIZE)))
            .addGroup(layout.createSequentialGroup()
                .addGap(137, 137, 137)
                .addComponent(botonAPrefijo, javax.swing.GroupLayout.PREFERRED_SIZE, 80, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addGap(0, 0, Short.MAX_VALUE))
        );
        layout.setVerticalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
            .addGroup(layout.createSequentialGroup()
                .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
                    .addGroup(layout.createSequentialGroup()
                        .addComponent(jLabel1, javax.swing.GroupLayout.PREFERRED_SIZE, 28, javax.swing.GroupLayout.PREFERRED_SIZE)
                        .addGap(18, 18, 18)
                        .addComponent(Infijo, javax.swing.GroupLayout.PREFERRED_SIZE, 70, javax.swing.GroupLayout.PREFERRED_SIZE)
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)
                        .addComponent(botonAPrefijo)
                        .addGap(13, 13, 13)
                        .addComponent(resultado, javax.swing.GroupLayout.PREFERRED_SIZE, 68, javax.swing.GroupLayout.PREFERRED_SIZE))
                    .addComponent(salir))
                .addContainerGap())
        );

        pack();
    }// </editor-fold>                       

    private void InfijoActionPerformed(java.awt.event.ActionEvent evt) {                                     
        // TODO add your handling code here:
    }                                     

    private void botonAPrefijoActionPerformed(java.awt.event.ActionEvent evt) {                                             
        ConvertidorInfijoAPrefijo aPrefijo = new ConvertidorInfijoAPrefijo();
        String text = Infijo.getText();
        aPrefijo.convertidorInfijoAPrefijo(new StringBuffer(text));

resultado.setText(aPrefijo.prefijo.toString());
    }                                           

    private void salirActionPerformed(java.awt.event.ActionEvent evt) {                                     
        System.exit(0);
    }                                   

    /**
     * @param args the command line arguments
     */
    public static void main(String args[]) {
        /*
         * Set the Nimbus look and feel
         */
        //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) ">
        /*
         * If Nimbus (introduced in Java SE 6) is not available, stay with the
         * default look and feel. For details see
         * http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html
         */
        try {
            for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {
                if ("Nimbus".equals(info.getName())) {
                    javax.swing.UIManager.setLookAndFeel(info.getClassName());
                    break;
                }
            }
        } catch (ClassNotFoundException ex) {
            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (InstantiationException ex) {
            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (IllegalAccessException ex) {
            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (javax.swing.UnsupportedLookAndFeelException ex) {
            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        }
        //</editor-fold>
        //</editor-fold>

        /*
         * Create and display the form
         */
        java.awt.EventQueue.invokeLater(new Runnable() {

            public void run() {
                new ExpresionAritmeticaGui().setVisible(true);
            }
        });
    }
    // Variables declaration - do not modify                   
    private javax.swing.JTextField Infijo;
    private javax.swing.JButton botonAPrefijo;
    private javax.swing.JLabel jLabel1;
    private javax.swing.JTextField resultado;
    private javax.swing.JButton salir;
    // End of variables declaration                 
}

package convers_infija_prefija;

public class ExpresionAritmeticaGui extends javax.swing.JFrame {

    /**

     * Creates new form ExpresionAritmeticaGui

     */

    public ExpresionAritmeticaGui() {

        initComponents();

        this.setLocationRelativeTo(null);

    }

    @SuppressWarnings("unchecked")

    // <editor-fold defaultstate="collapsed" desc="Generated Code">                          

    private void initComponents() {

        botonAPrefijo = new javax.swing.JButton();

        jLabel1 = new javax.swing.JLabel();

        Infijo = new javax.swing.JTextField();

        salir = new javax.swing.JButton();

        resultado = new javax.swing.JTextField();

        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);

        setTitle("Expresiones Aritmeticas");

        botonAPrefijo.setBackground(new java.awt.Color(102, 102, 102));

        botonAPrefijo.setText("CONVERTIR");

        botonAPrefijo.setBorder(new javax.swing.border.LineBorder(new java.awt.Color(51, 51, 51), 4, true));

        botonAPrefijo.addActionListener(new java.awt.event.ActionListener() {

            public void actionPerformed(java.awt.event.ActionEvent evt) {

                botonAPrefijoActionPerformed(evt);

            }

        });

        jLabel1.setFont(new java.awt.Font("Tahoma", 1, 18)); // NOI18N

        jLabel1.setText("Conversión de Infija a Prefija");

        Infijo.setFont(new java.awt.Font("Arial", 0, 14)); // NOI18N

        Infijo.setHorizontalAlignment(javax.swing.JTextField.CENTER);

        Infijo.setBorder(javax.swing.BorderFactory.createTitledBorder(null, "Infija", javax.swing.border.TitledBorder.DEFAULT_JUSTIFICATION, javax.swing.border.TitledBorder.DEFAULT_POSITION, new java.awt.Font("Tahoma", 3, 12), new java.awt.Color(51, 51, 51))); // NOI18N

        Infijo.addActionListener(new java.awt.event.ActionListener() {

            public void actionPerformed(java.awt.event.ActionEvent evt) {

                InfijoActionPerformed(evt);

            }

        });

        salir.setBackground(new java.awt.Color(153, 153, 153));

        salir.setText("SALIR");

        salir.setBorder(new javax.swing.border.LineBorder(new java.awt.Color(51, 51, 51), 4, true));

        salir.addActionListener(new java.awt.event.ActionListener() {

            public void actionPerformed(java.awt.event.ActionEvent evt) {

                salirActionPerformed(evt);

            }

        });

        resultado.setEditable(false);

        resultado.setFont(new java.awt.Font("Arial", 0, 14)); // NOI18N

        resultado.setHorizontalAlignment(javax.swing.JTextField.CENTER);

        resultado.setBorder(javax.swing.BorderFactory.createTitledBorder(null, "Prefija", javax.swing.border.TitledBorder.DEFAULT_JUSTIFICATION, javax.swing.border.TitledBorder.DEFAULT_POSITION, new java.awt.Font("Tahoma", 3, 12), new java.awt.Color(51, 51, 51))); // NOI18N

        javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());

        getContentPane().setLayout(layout);

        layout.setHorizontalGroup(

            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

            .addGroup(layout.createSequentialGroup()

                .addGap(48, 48, 48)

                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

                    .addGroup(layout.createSequentialGroup()

                        .addComponent(resultado, javax.swing.GroupLayout.DEFAULT_SIZE, 262, Short.MAX_VALUE)

                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)

                        .addComponent(salir, javax.swing.GroupLayout.PREFERRED_SIZE, 47, javax.swing.GroupLayout.PREFERRED_SIZE)

                        .addGap(8, 8, 8))

                    .addComponent(jLabel1)

                    .addComponent(Infijo, javax.swing.GroupLayout.PREFERRED_SIZE, 260, javax.swing.GroupLayout.PREFERRED_SIZE)))

            .addGroup(layout.createSequentialGroup()

                .addGap(137, 137, 137)

                .addComponent(botonAPrefijo, javax.swing.GroupLayout.PREFERRED_SIZE, 80, javax.swing.GroupLayout.PREFERRED_SIZE)

                .addGap(0, 0, Short.MAX_VALUE))

        );

        layout.setVerticalGroup(

            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)

            .addGroup(layout.createSequentialGroup()

                .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)

                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)

                    .addGroup(layout.createSequentialGroup()

                        .addComponent(jLabel1, javax.swing.GroupLayout.PREFERRED_SIZE, 28, javax.swing.GroupLayout.PREFERRED_SIZE)

                        .addGap(18, 18, 18)

                        .addComponent(Infijo, javax.swing.GroupLayout.PREFERRED_SIZE, 70, javax.swing.GroupLayout.PREFERRED_SIZE)

                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)

                        .addComponent(botonAPrefijo)

                        .addGap(13, 13, 13)

                        .addComponent(resultado, javax.swing.GroupLayout.PREFERRED_SIZE, 68, javax.swing.GroupLayout.PREFERRED_SIZE))

                    .addComponent(salir))

                .addContainerGap())

        );

        pack();

    }// </editor-fold>                        

    private void InfijoActionPerformed(java.awt.event.ActionEvent evt) {                                       

        // TODO add your handling code here:

    }                                      

    private void botonAPrefijoActionPerformed(java.awt.event.ActionEvent evt) {                                              

        ConvertidorInfijoAPrefijo aPrefijo = new ConvertidorInfijoAPrefijo();

        String text = Infijo.getText();

        aPrefijo.convertidorInfijoAPrefijo(new StringBuffer(text));

resultado.setText(aPrefijo.prefijo.toString());

    }                                             

    private void salirActionPerformed(java.awt.event.ActionEvent evt) {                                      

        System.exit(0);

    }                                     

    /**

     * @param args the command line arguments

     */

    public static void main(String args[]) {

        /*

         * Set the Nimbus look and feel

         */

        //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) ">

        /*

         * If Nimbus (introduced in Java SE 6) is not available, stay with the

         * default look and feel. For details see

         * http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html

         */

        try {

            for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {

                if ("Nimbus".equals(info.getName())) {

                    javax.swing.UIManager.setLookAndFeel(info.getClassName());

                    break;

                }

            }

        } catch (ClassNotFoundException ex) {

            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

        } catch (InstantiationException ex) {

            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

        } catch (IllegalAccessException ex) {

            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

        } catch (javax.swing.UnsupportedLookAndFeelException ex) {

            java.util.logging.Logger.getLogger(ExpresionAritmeticaGui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

        }

        //</editor-fold>

        //</editor-fold>

        /*

         * Create and display the form

         */

        java.awt.EventQueue.invokeLater(new Runnable() {

            public void run() {

                new ExpresionAritmeticaGui().setVisible(true);

            }

        });

    }

    // Variables declaration - do not modify                     

    private javax.swing.JTextField Infijo;

    private javax.swing.JButton botonAPrefijo;

    private javax.swing.JLabel jLabel1;

    private javax.swing.JTextField resultado;

    private javax.swing.JButton salir;

    // End of variables declaration                   

}

Código P.

• El código P hace referencia a máquinas que utilizan o se auxilian de pilas para generar código objeto. 

• En muchos caso la P se asociado a código portable el cual garantiza que el código compilado en una máquina se pueda ejecutar en otras.

• Para garantizar la portabilidad del código se necesita que el lenguaje este estandarizado por algún instituto y que dicho código no tenga extensiones particulares. 

• También se recomienda la no utilización de carácterísticas especiales exclusivas de alguna arquitectura de computadoras en particular.

Triplos.

• Las proposiciones de tres direcciones se parece mucho al ensamblador, el cual es un lenguaje intermedio más entendible para la máquina. 

• Las estructuras de control (if, switch, while, do-while, for) son realmente etiquetas goto disfrazadas.

• El problema de utilizar cuádruplos radica en que se tienen que colocar los valores temporales en la tabla de símbolo. 

• Con una estructura de tres campos se pueden omitir los valores temporales, dicha estructura recibe el nombre de triples y tiene los siguientes campos: op, arg1 y arg2.

• Generalmente el código que generan los triples recibe el nombre de código de dos direcciones, aunque en ocasiones puede variar.

• Cuando se utilizan triples se ocupan punteros a la misma estructura de los triples.

• * b t1 t2 //cuádruplos.

• * b (0) //triple.

• Se debe tener en cuenta el proceso de asignación, de declaración, expresiones booleanas. 

• Las expresiones lógicas también pueden pasarse a código de tres direcciones, utilizando para ello expresiones en corto circuito.

• La evaluación de expresiones en corto circuito implica que se evalúan condiciones revisando valores anteriores; por ejemplo, para el operador AND con una condición que se detecte como falsa toda la expresión es falsa, en el caso del operador OR si se encuentra una condición verdadera todo será verdadera.

• La notación de tres direcciones es una forma abstracta de código intermedio. 

• Esta notación se puede implementar como registros con campos para el operador y operadores. 

Intérpretes.

• Los interpretes generalmente utilizan este triplos para generar el código intermedio para ejecutarse una vez considerado la instrucción como válido. 

• En este sentido, un compilador es más difícil de implementar ya que tendrá que mantener todas las estructuras generadas que en muchas ocasiones serán cuadrúplos.

Cuádruplos.

• Es una estructura tipo registro con cuatros campos que se llaman: op, arg1, arg2 y resultado. OP tiene un código intermedio. 

• Los operadores unarios como x:=-y no utilizan arg2. Generalmente arg1, arg2 y resultado son valores de tipo puntero y apuntan a una entrada en la tabla de símbolos.

Esquemas de generación.

• Los esquemas de generación son las estrategias o acciones que se deberán realizarse y tomarse en cuenta en el momento de generar código intermedio. 

• Los esquemas de generación dependen de cada lenguaje. Tomaremos algunos esquemas de generación del lenguaje C.

Expresiones.

• Para generar expresiones estas deben representarse de manera más simple y más literal para que su conversión sea más rápida. 

• Por ejemplo la traducción de operaciones aritméticas debe especificarse una por una, de tal forma que una expresión sea lo más mínimo posible.

Declaración de variables, constantes.

• Las declaraciones de variables y constantes deben separarse de tal manera que queden las expresiones una por una de manera simple. 

• Por ejemplo int a,b,c; se descompone a int a; int b; intc; respectivamente.

Estatuto de asignación. 

• Las operaciones de asignación deben quedar expresadas por una expresión sencilla, si está es compleja se debe reducir hasta quedar un operador sencillo. 

• Por ejemplo: x = a+b/5; debe quedar de la forma y = b/5; z = a+y; x=z.

Estatuto condicional.

• Las condiciones deben expresarse de manera lo más sencilla posible de tal forma que puedan evaluarse en cortocircuito. Por ejemplo una instrucción como: if (a == b && f!=5 && f%3==0) se evalúa primero x = (a==b && f!=5) y = x && f%3==0; if (y) 

• Las instrucciones de decisión compleja como switch se reducen a una versión complejas de if’s.

Estatuto de ciclos.

• Los ciclos se descomponen en un ciclo genérico, por lo que ciclos while, for y dowhile tienen la misma representación interna. En el caso de C, todo queda en forma de while. 

• Las condiciones lógicas también pueden ser evaluadas en cortocircuito y reducidas.

Arreglos.

• Los arreglos se descomponen en estructuras básicas de manejo de manera simple, así por ejemplo: char *a=“Hola”; se reduce a: a[0]=‘H’; a[1]=‘o’; a[2]=‘l’; a[3]=‘a’; a[4]=‘\0’;

Expresiones.

En esta función recibe una cadena que representa una línea de código intermedio y toma las medidas oportunas para que ese código se utilice. Estas medidas pueden ser escribir la línea en un fichero adecuado, almacenar la instrucción en una lista que después se pasará a otros módulos, o cualquier otra que necesitemos en nuestro compilador. Expresiones aritméticas Son aquella donde los operadores que intervienen en ella son numéricos, el resultado es un número y los operadores son aritméticos. Los operadores aritméticos más comúnmente utilizados son: +, - , * , / y %. Comenzamos el estudio por las expresiones aritméticas. Lo que tendremos que hacer es crear por cada tipo de nodo un método que genere el código para calcular la expresión y lo emita. Ese código dejará el resultado en un registro, cuyo nombre devolverá el método como resultado. Para reservar estos registros temporales, utilizaremos una función, reserva. En principio bastar ‘a con que esta función devuelva un registro distinto cada vez que se la llame. 

Cada nodo generará el código de la siguiente manera:

 Por cada uno de sus operandos, llamara al método correspondiente para que se evalúe la sub expresión. Si es necesario, reservara un registro para guardar su resultado. 

 Emitirá las instrucciones necesarias para realizar el cálculo a partir de los operandos. 

Instrucción de asignación.

La sintaxis general de la instrucción de asignación es: nombre_de_la_variable = valor El valor a la derecha del signo igual puede ser una constante, otra variable o una expresión que combine constantes y variables, pero siempre la variable y su valor deben ser del mismo tipo de dato. Ejemplos: 

edad% = 5 

area! = 12.3 

nombre$ = “Pedro” 

 Instrucciones de asignación compuesta Las instrucciones de asignación compuesta realizan primero una operación en una expresión antes de asignarla a un elemento de programación. En el siguiente ejemplo se muestra uno de estos operadores, +=, que incrementa el valor de la variable del lado izquierdo del operador con el valor de la expresión de la derecha. Una instrucción de asignación asigna el valor de una expresión a una variable. En general, si la variable que se va a asignar es una propiedad, la propiedad debe ser de lectura y escritura o de sólo escritura; en caso contrario, se produce un error de compilación. Si la variable es una variable de sólo lectura, la asignación debe producirse en un constructor Shared o un constructor de instancia apropiado para el tipo de la variable; en caso contrario, se producirá un error de compilación. 

Instrucciones de control. 

Esta forma de programación sólo permite resolver problemas sencillos. Para resolver problemas más complejos, nos puede interesar que dependiendo de los valores de los datos, se ejecuten unas instrucciones u otras. Las instrucciones condicionales nos van a permitir representar éste tipo de comportamiento. Sentencias IF y SWITCH. En otros casos, nos encontraremos con la necesidad de repetir una instrucción o instrucciones un número determinado de veces. En éstos casos utilizaremos instrucciones de control iterativas o repetitivas (ciclos). Sentencias WHILE, DO-WHILE y FOR.

Funciones.

• Las funciones pueden reducir a en línea, lo que se hace es expandir el código original de la función. 

• Las funciones se descomponen simplificando los parámetros de manera individual al igual que el valor de retorno.

Estructuras de Control.

Una vez sabemos cómo generar código para las expresiones y asignaciones, vamos a ver cómo podemos generar el código de las estructuras de control. Hay dos estructuras que ya hemos visto implícitamente. Por un lado, la estructura de control más simple, la secuencia, consiste simplemente en escribir las distintas sentencias una detrás de otra. En cuanto a las subrutinas, bastar´a con crear el correspondiente prólogo y epílogo seg´un vimos en el tema anterior. Las sentencias de su cuerpo no tienen nada especial. A continuación veremos algunas de las estructuras más comunes de los lenguajes de programación imperativos. Otras estructuras se pueden escribir de forma similar.


Diagrama de Flujo del Algoritmo de la Notación Polaca:

http://dsc.itmorelia.edu.mx/~jcolivares/courses/ps207b/ps2_u6.pdf

Pila Semántica de un Analizador Sintáctico

Pila Semántica de un Analizador Sintáctico:

Análisis Semántico:

Detecta la validez semántica de las sentencias aceptadas por el analizador sintáctico. El analizador semántico suele trabajar simultáneamente al analizador sintáctico. Se entiende por semántica al conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje. Las rutinas semánticas deben realizar la evaluación de los atributos de las gramáticas siguiendo las reglas semánticas asociadas a cada producción de la gramática. 

Análisis Sintáctico:

Analiza el símbolo, la pila y el estado del autómata, produce las estructuras necesarias para la siguiente etapa y en el caso de compilación dirigida por la sintaxis invoca llamadas directas al analizador semántico y al generador de código. Escribe mensajes de errores y trata de limitar el efecto de estos errores.

“Reconoce la estructura de una cadena de componentes léxicos”

Teoría de Pilas Y Colas: Son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación.

Estas estructuras pueden implementarse mediante arrays o listas enlazadas. Al utilizar arreglos para implementar pilas se tiene la limitación de que se debe reservar el espacio en memoria con anticipación. 

Una vez dado un máximo de capacidad a la pila no es posible insertar un número de elementos mayor que el máximo establecido. 

Una posible solución a este tipo de inconvenientes consiste en definir pilas de gran tamaño, pero esto resultará ineficiente y costoso.

No siempre es viable saber con exactitud el número de elementos a tratar, y siempre existe la posibilidad de que ocurra un error de desbordamiento. Colas

También son llamadas FIFO (First In First Out), que quiere decir “El primero que entra es el primero que sale”. Las rutinas semánticas suelen hacer uso de una pila (la pila semántica) que contiene la información semántica asociada a los operados (y a veces a los operadores) en forma de registros semánticos.

1. Colas Simples: Se inserta por un sitio y se saca por otro, en el caso de la cola simple se inserta por el final y se saca por el principio. Para gestionar este tipo de cola hay que recordar siempre cual es el siguiente elemento que se va a leer y cuál es el último elemento que se ha introducido.

2. Colas Circulares: En las colas circulares se considera que después del último elemento se accede de nuevo al primero. De esta forma se reutilizan las posiciones extraídas, el final de la cola es a su vez el principio, creándose un circuito cerrado.

3. Colas con Prioridad: Las colas con prioridad se implementan mediante listas o arrays Ordenados. No nos interesa en este caso que salgan en el orden de entrada sino con una prioridad que le asignemos. Puede darse el caso que existan varios elementos con la misma prioridad, en este caso saldrá primero aquel que primero llego (FIFO).

Reglas semánticas 

Conjunto de normas y especificaciones que definen al lenguaje de programación y están dadas por la sintaxis del lenguaje, las reglas semánticas asignan un significado lógico a ciertas expresiones definidas en la sintaxis del lenguaje. 

Analizador Sintáctico Descendente: Parten del axioma inicial de la gramática, se va descendiendo utilizando las derivaciones izquierdas, hasta llegar a construir la cadena analizada. 

Analizador Sintáctico Ascendente: Se va construyendo el árbol desde sus nodos terminales. Es decir, se construye desde los símbolos de la cadena hasta llegar al axioma de la gramática. Un Analizador Sintáctico Ascendente utiliza durante el análisis una pila. En esta va guardando datos que le permiten ir haciendo las operaciones de reducción que necesita. Para incorporar acciones semánticas como lo es construir el árbol sintáctico, es necesario incorporar a la pila del analizador sintáctico ascendente otra columna que guarde los atributos de los símbolos que se van analizando; para la integración total del sistema. El Diseño Descendente es un método para resolver el problema que posteriormente se traducirá a un lenguaje comprensible por la computadora. Es el proceso mediante el cual un problema se descompone en una serie de niveles o pasos sucesivos de refinamiento. La metodología descendiente consiste en efectuar una relación entre las sucesivas etapas de estructuración de modo que se relacionen unas con otras mediante entradas y salidas de información. Pila

Una colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope.

Las Pilas tienen dos operaciones básicas: Push (para insertar un elemento)  Pop (para extraer un elemento). Gracias a las pilas es posible el uso de la recursividad. La variable que llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas. Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO.

2) CARACTERÍSTICAS

 Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO (del inglés Last In First Out). Una posible implementación mediante listas enlazadas sería insertando y extrayendo siempre por el principio de la lista.

 Gracias a las pilas es posible el uso de la recursividad. La variable que llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

 Contiene la información semántica asociada a los operandos (y a veces a los operadores) en forma de registros semánticos.

 Los Autómatas con Pila son una extensión de los AFD a los que se les añade una memoria (pila).

En la pila se almacenan símbolos de la cadena de entrada y de la gramática, así como caracteres especiales (#) para indicar el estado de pila vacía.

 Las transiciones son de la forma: (p, x, s; q, t):

p=estado inicial

q=estado al que llega

x= símbolo de la cadena de entrada

s=símbolo que se desapila

t=símbolo que se apila

 Una pila es utilizada para almacenar el prefijo viable de una forma sentencial de una derivación más a la derecha. Los símbolos,  y  son utilizados para identificar el pivote, por lo tanto sabremos cuando Desplazar o cuando Reducir.

3) VENTAJAS

 Es posible el uso de la recursividad. La variable que llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

 Simplifican ciertas operaciones de programación. Se pueden implementar mediante arrays o listas enlazadas.

4) DESVENTAJAS

Se tiene la limitación de que se debe reservar el espacio en memoria con anticipación. Una vez dado un máximo de capacidad a la pila no es posible insertar un número de elementos mayor que el máximo establecido.

 Si esto ocurre, en otras palabras si la pila está llena y se intenta insertar un nuevo elemento, se producirá un error conocido como desbordamiento-overflow.

 Se deben definir pilas de gran tamaño, pero esto resultará ineficiente y costoso.

 No siempre es viable saber con exactitud el número de elementos a tratar, y siempre existe la posibilidad de que ocurra el error de desbordamiento.

5) EJEMPLOS DE CÓMO TRABAJA LA PILA SEMÁNTICA CON

LAS EXPRESIONES REGULARES

Este ejemplo tendrá que aceptar cualquier fecha del año 2011, esta fecha tendrá que ser válida (que lleve relación el mes con el día)

AUTÓMATA DE LOS MESES

Mapa Mental de la Pila Semántica del Analizador Sintáctico.