martes, 28 de marzo de 2017

Analizador sintactico

import java.io.*;
import java.lang.*;
import java.util.UUID;

public class automata_finito {

public static void main(String[] args) throws IOException {

BufferedReader a=new BufferedReader(new InputStreamReader (System.in));

String Usuario,contrasena;
int Password;

//UUID (Unique Universal Identifier)

System.out.println(UUID.randomUUID().toString().toUpperCase().substring(0, 12));


System.out.println("Usuario:");
Usuario= a.readLine();
System.out.println("Password:");
Password= Integer.parseInt(a.readLine());

if (Usuario.equals("Cristian") && Password == 12345){

System.out.println(" ¡Bienvenido Cristian!");
}
else {

System.out.println(" El Usuario y/o Password son incorrectos");
}

}

}

Este programa lo que hace es validar las contraseñas nuevas que se entan generando a partir de un RANDOM, el cual va a integrar caracteres como el alfabeto de la A-Z combinado con numeros de el 0-9.
El proceso de entrada solo es valido si la contraseña ingresada esta escrita correcta de manera correcta en como se esta imprimiendo.



ejemplo 2: (Analizador sintáctico)

package lenguaje_formal;

import java.io.*;
import java.lang.*;

public class Lenguaje_formal {

    public static void main(String[] args) throws IOException  {

        BufferedReader a=new BufferedReader(new InputStreamReader (System.in));
        int opcion;
        int variableentera;
        String variabletexto;
     
        System.out.println("ELIGE EL TIPO DE PALABRA RESERVADA QUE DESEAS UTILIZAR");
        System.out.println("1.-ENTERO");
        System.out.println("2.-TEXTO");
     
        opcion=Integer.parseInt (a.readLine());
        switch(opcion){
         
            case 1:
                System.out.println("Para usar tipo entero solo puedes usar numeros entre el 0 y el 9");
                System.out.println("Introduce la variable que quieras usar:");
                variableentera = Integer.parseInt(a.readLine());
             
if (variableentera == 0 || variableentera == 1 || variableentera == 2 || variableentera == 3 || variableentera ==4 || variableentera == 5
        || variableentera == 6 || variableentera == 7 || variableentera == 8 || variableentera == 9)
                {
                    System.out.println("Este tipo de caracter es permitido");
                }
                else{
                    System.out.println("Este parametro no esta permitido");
                }
                break;
             
            case 2:
                System.out.println("Para usar de tipo texto solo puedes utilizar vocales");
                System.out.println("Introduce la variable que quieras usar:");
                variabletexto = a.readLine();
             
                if (variabletexto.equals("a") || variabletexto.equals("e") || variabletexto.equals("i") || variabletexto.equals("o") || variabletexto.equals("u"))
                {
                    System.out.println("Este tipo de caracter es permitido");
                }
                else{
                    System.out.println("Este parametro no esta permitido");
                }
                 
                break;
             
            default:
                System.out.println("Esta no es una opcion valida");  
                break;
        }
    }
 
}

En este programa se va analizar la estructura con la cual ingresamos las palabras o los números, es decir que solo puede ingresarse cierto numero de caracteres entre letras o números de acuerdo a la opción deseada.

Si se elige la opción de números solo podrás ingresar números enteros positivos del 0 al 9, si ingresamos algún otro numero diferente a los permitidos se mandara una alerta de que el numero que estamos ingresando no es valido en este programa.

En el caso de elegir la opción de texto, podremos ingresar letras básicas como son vocales: a,e,i,o,u. Si ingresamos alguna otra letra diferente a estas definidas se enviara un mensaje el cual es: Este parámetro no esta permitido y tendrás que entrar de nuevo al programa.





lunes, 27 de marzo de 2017

Construcción de analizadores sintácticos.

3.1 Analizadores sintácticos.

Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico. 

En la práctica, el analizador sintáctico también hace: 

• Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico). 
• Chequeo de tipos ( del analizador semántico). 
• Generar código intermedio. 
• Generar errores cuando se producen. 

En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.
La tarea esencial de un analizador es determinar si una determinada entrada puede ser derivada desde el símbolo inicial, usando las reglas de una gramática formal, y como hacer esto, existen esencialmente dos formas:
  • Analizador sintáctico descendente (Top-Down-Parser): ..un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas, de esta forma funcionan los analizadores LL, un ejemplo es el javaCC.
  • Analizador sintáctico ascendente (Bottom-Up-Parser): un analizador puede empezar con la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta encontrar los símbolos más pequeños y progresivamente construir la jerarquía de símbolos hasta el inicial, los analizadores LR funcionan así y un ejemplo es el Yacc.

Características

El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
Parte del axioma de la gramática.
Procesa la entrada de izquierda a derecha.Escoge reglas gramaticales.
Bueno primeramente para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:
– ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática.
– ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena . Es decir por simple observación podemos identificar.
Ventajas:

  • genera código intermedio
  • reconoce si una o varias cadenas de caracteres forman parte de un determinado lenguaje.
  • lenguajes libres de contexto.
  • pueden clasificarse dependiendo de la forma en como se construyen los nodos del árbol de derivación sintáctico: ascendentes y descendentes
Desventajas:

  • genera errores cuando se producen 
  • numerosos patrones de funcionamiento en ellos
Aplicabilidad:
El uso más común de los analizadores sintácticos es como parte de la fase de análisis de los compiladores. De modo que tienen que analizar el código fuente del lenguaje. Los lenguajes de programación tienden a basarse en gramáticas libres de contexto, debido a que se pueden escribir analizadores rápidos y eficientes para estas.
Las gramáticas libres de contexto tienen una expresividad limitada y sólo pueden expresar un conjunto limitado de lenguajes. Informalmente la razón de esto es que la memoria de un lenguaje de este tipo es limitada, la gramatica no puede recordar la presencia de una construcción en una entrada arbitrariamente larga y esto es necesario en un lenguaje en el que por ejemplo una variable debe ser declarada antes de que pueda ser referenciada. Las gramáticas más complejas no pueden ser analizadas de forma eficiente. Por estas razones es común crear un analizador permisivo para una gramática libre de contexto que acepta un super conjunto del lenguaje (acepta algunas construcciones inválidas), después del análisis inicial las construcciones incorrectas pueden ser filtradas.

3.1.2 
Eliminación de recursión izquierda en las gramáticas, arboles de sintaxis.
Una gramática es recursiva por la izquierda si tiene un no terminal A tal que existe una derivación A Aα  para alguna cadena  α. Los métodos de análisis sintáctico descendente no pueden manejar gramáticas recursivas por la izquierda, así que se necesita una transformación que elimine la recursión por la izquierda.

Recursión por la izquierda inmediata simple  (Eliminación de la recursividad izquierda de las producciones)

En este caso la recursión por la izquierda se presenta solo en las reglas gramaticales

A → A α | β

Donde α y β son cadenas de terminales y no terminales y  β no comienza en A. Esta regla genera todas las cadenas de la forma β, β α, β α α…Todas las cadenas comienzan con una β, seguida por     (0 o mas α). Esta regla gramatical es equivalente a la expresión regular β αⁿ

Para eliminar  la recursión por la izquierda  volvemos a escribir estas reglas gramaticales divididas en dos: una para que primero genere β y otra que genere  las repeticiones de α utilizando recursión por la derecha en vez de recursión por la izquierda:

A → β A´
A´→ α A´|є

Ejemplo Considere de nueva cuenta la regla recursiva izquierda de la gramática de expresión simple:

exp → exp opsuma term | term

La forma de esta regla es  A → A α | β, con A= exp,  α=opsuma term y β=term. Al volverla a escribir para eliminar la recursividad por la izquierda obtenemos que

exp → term exp´
exp´→ opsuma term exp´ |є

Recursión por la izquierda inmediata general  (Eliminando la recursión directa por la izquierda de una producción general)

Este es el caso en que tenemos producciones de la forma

A → A α| A α|……|A α n | β | β |……… | βm

Donde ninguna β…… βm comienzan con una A. Después se sustituyen las producciones de A por:

A→ β A´| β  A´|…….| βm  A´
A´→ α A´| α A´|…….| α n A´|є

Ejemplo. Considere la regla gramatical

exp → exp + term | exp -  term | term

Eliminemos la recursión por la izquierda de la manera siguiente

exp → term exp´
exp → + term exp´ | - term exp´ |є

Recursión por la izquierda general (Eliminación de la recursividad izquierda de una gramática completa puede ser mas difícil debido a la recursividad izquierda indirecta).

Es indirectamente recursiva porque elimina por completo la recursividad izquierda


El algoritmo que aquí describimos  eliminara sistemáticamente la recursión por la izquierda general de una gramática. Siempre funciona si la gramática no tiene ciclos (donde un ciclo es una derivación de por lo menos un paso que comienza y finaliza con el mismo no terminal: 
A      A)


O producciones  є (producciones de la forma A → є)

Algoritmo

Entrada La gramática G sin ciclos ni producciones є
Salida Una gramática equivalente sin recursión por la izquierda

1.- Ordénense los no terminales en un orden A, A,……..,An
2.- PARA i =: 1 hasta n HACER
       COMIENZA {PARA i}
      PARA  j=: 1 hasta i-1 HACER
Reemplace cada producción de la forma  Ai → Ajβ por las producciones:

Ai → αβ| αβ|……| αk β

Donde:

Aj→ α| α|……| αk

Son todas las producciones de Aj actuales

Eliminar  la recursividad inmediata por la izquierda entre las producciones de Ai

Ejemplo: Dada la gramática

S→ Aa | b
A→ Ac|Sd|є

Se ordenan los no terminales S, A. No hay recursión directa por la izquierda entre las producciones de S, de modo que no ocurre  nada durante el paso 2 para el caso i=1. Para i=2, se sustituyen las producciones de S en A→ Sd para obtener las siguientes producciones de A.

A → Ac|Aad | bd  |є

Eliminando la recursión directa por la izquierda entre las producciones de A, se obtiene la siguiente gramática

S → Aa | b
A→bdA´ | A´
A´→c A´|ad A´| є

La eliminación de la recursión por la izquierda no cambia el lenguaje que se esta reconociendo, pero modifica la gramática y, en consecuencia, también los arboles de derivación.