Usando Graphviz para hacer gráficas de autómatas

October 18, 2007 soullost GNU/Linux, Parsing 2 Comments

Hoy me he dado un momento para empezar a usar Graphviz (http://www.graphviz.org) que es un programa para realizar gráficas. Graphviz es exactamente el mismo programa que usa Kakuy (proyecto SEPa). Kakuy es un software en windows que usa para animar (por medio de gráficas) técnicas de parsing, muy recomendado más por la extensa documentación sobre las técnicas de parsing ;) .

Bueno, para empezar hay que saber que Graphviz usa documentos *.dot para que por medio de dot (comando) se pueda leer la estructura de éste y se genere la gráfica correspondiente.

Un ejemplo simple:

ejemplo.dot

PLAIN TEXT
CODE:
  1. digraph G{
  2.   rankdir=LR;
  3.   node [shape = doublecircle]; q3;
  4.   node [shape = circle];
  5.   q0 -> q1 [ label = "a" ];
  6.   q1 -> q2 [ label = "b" ];
  7.   q2 -> q3 [ label = "c" ];
  8. }

Para crear un archivo *.png mediante el archivo ejemplo.dot en nuestra consola hacemos:

PLAIN TEXT
CODE:
  1. dot -Tpng ejemplo.dot -o ejemplo.png

PLAIN TEXT
CODE:
  1. soullost@UnderHouse ~/dots $ ls *.png
  2. ejemplo1.png

La imagen:

Ejemplo

:o ! Ya tenemos nuestro primer autómata dibujado! :D XD

La razón de usar Graphviz es porque quisiera poner más ejemplos de parsing pero no encontraba como dibujar los autómatas de una forma sencilla :P , en fin puedes obtener Graphviz de:

Windows: http://www.graphviz.org/Download_windows.php
Linux: http://www.graphviz.org/Download_linux.php

Gentoo :) :

PLAIN TEXT
CODE:
  1. emerge graphviz

Hay cosas más interesantes sobre Graphviz, por ejemplo, hay una librería para C y Python (me parece xD)..

Recomendado leer:
- PDF dot guide

Nos vemos!!..

Califica el tema:
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5 out of 5)
Loading ... Loading ...

Autómata de pila X^n W Y^n

July 11, 2007 root Parsing, Programación No Comments

No me voy a liar con conceptos y demás, entonces, miren la wikipedia:

http://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila

Claro cualquier duda también pueden dejarme un comentario y trataré de ayudarle si me es posible :).

Como repaso rápido, un autómata de pila no es más que un algoritmo que aparte de verificar un lenguaje determinado, tiene la posibilidad de poder controlar la aparición de los símbolos definidos en alfabeto de nuestro lenguaje. Para ser más práctico, un ejemplo claro de esto es en los lenguajes de programación, cuando hacemos la llamada a la instrucción if, que tiene sintaxis:

if ( condicion|comparacion ) ;

Como regla básica la instrucción if debe contener un parénesis abierto y otro cerrado, entonces, esta es la posibilidad de un autómata de pila.

Ahora les comparto el código de un programa que determina si la palabra escrita pertenece o no al siguiente lenguaje:

X^n W Y^n
Donde n>=1.

Donde la expresión mínima del lenguaje es:

Expresion a validar:
xwy
SINTAXIS CORRECTA

Las transíciones son:

1) (q0,x,#) -> (q1, )
2) (q1,x,#) -> (q1,a)
3) (q1,w,a) -> (q2, )
4) (q2,y,a) -> (q3,&)
5) (q3,y,a) -> (q3,&)
6) (q3,y,#) -> (q4, )

Más o menos, aclarar que "&" representa quitar un elemento de la pila.

Para compilar con g++:

g++ a202301.cpp -o a202301

Les dejo el código:

PLAIN TEXT
C++:
  1. /*
  3. Autor: Soul Lost
  5. Descripcion: Lenguaje: x^n w y^n
  7. Donde n>=1.
  9. */
  10.  
  11.  
  12.  
  13. #include<iostream.h>
  14.  
  15. #include<stdlib.h>
  16.  
  17.  
  18.  
  19. typedef char cadena[80];
  20.  
  21. enum alfabeto{x,y,w,FDC};
  22.  
  23. enum status{mal,bien};
  24.  
  25. cadena linea;
  26.  
  27. status result=mal;
  28.  
  29. alfabeto simbolo;
  30.  
  31. int pos;
  32.  
  33. char tope;
  34.  
  35.  
  36.  
  37. //Estructura para llevar el control de la pila
  38.  
  39.  
  40.  
  41. struct nodo{
  42.  
  43.     char smb;
  44.  
  45.     nodo* next;
  46.  
  47. };
  48.  
  49.  
  50.  
  51. nodo* first=NULL;
  52.  
  53.  
  54.  
  55. int leerCar();
  56.  
  57. int resultado();
  58.  
  59. int estado1();
  60.  
  61. int estado2();
  62.  
  63. int estado3();
  64.  
  65. int estado4();
  66.  
  67. int estado5();
  68.  
  69. int meter(char);
  70.  
  71. int sacar();
  72.  
  73. char obtener();
  74.  
  75.  
  76.  
  77. int main(){
  78.  
  79.     pos=-1;
  80.  
  81.     system("clear");
  82.  
  83.     cout<<"Expresion a validar:"<<endl;
  84.  
  85.     cin>>linea;
  86.  
  87.     meter('#');
  88.  
  89.     estado1();
  90.  
  91.     resultado();
  92.  
  93.     system("sleep 2");
  94.  
  95.     return 0;
  96.  
  97. }
  98.  
  99.  
  100.  
  101. int resultado(){
  102.  
  103.     if(result) cout<<"SINTAXIS CORRECTA"<<endl;
  104.  
  105.     else cout<<"EXPRESION NO VALIDA"<<endl;
  106.  
  107.     return 0;
  108.  
  109. }
  110.  
  111.  
  112.  
  113. int leerCar(){
  114.  
  115.     char caracter;
  116.  
  117.     pos++;
  118.  
  119.     caracter=toupper(linea[pos]);
  120.  
  121.     tope=obtener();
  122.  
  123.     if(caracter=='X') simbolo=x;
  124.  
  125.     else if(caracter=='Y') simbolo=y;
  126.  
  127.     else if(caracter=='W') simbolo=w;
  128.  
  129.     else if(caracter=='\0') simbolo=FDC;
  130.  
  131.     return 0;
  132.  
  133. }
  134.  
  135.  
  136.  
  137. int estado1(){
  138.  
  139.     leerCar();
  140.  
  141.     if(simbolo==x && tope=='#'){
  142.  
  143.             meter('a');
  144.  
  145.             estado2();
  146.  
  147.         }
  148.  
  149.     return 0;
  150.  
  151. }
  152.  
  153.  
  154.  
  155. int estado2(){
  156.  
  157.     leerCar();
  158.  
  159.     if(simbolo==x && tope=='a'){
  160.  
  161.             meter('a');
  162.  
  163.             estado2();
  164.  
  165.         }
  166.  
  167.     else if(simbolo==w && tope=='a') estado3(); 
  168.  
  169.     return 0;
  170.  
  171. }
  172.  
  173.  
  174.  
  175. int estado3(){
  176.  
  177.     leerCar();
  178.  
  179.     if(simbolo==y && tope=='a'){
  180.  
  181.             sacar();
  182.  
  183.             estado4();
  184.  
  185.         }
  186.  
  187.     return 0;
  188.  
  189. }
  190.  
  191. int estado4(){
  192.  
  193.     leerCar();
  194.  
  195.     if(simbolo==y && tope=='a'){
  196.  
  197.             sacar();
  198.  
  199.             estado4();
  200.  
  201.         }
  202.  
  203.         else if(simbolo==FDC) estado5();
  204.  
  205.     return 0;
  206.  
  207. }
  208.  
  209.  
  210.  
  211. int estado5(){
  212.  
  213.     if(tope=='#') result=bien;
  214.  
  215.     delete first;
  216.  
  217.     return 0;
  218.  
  219. }
  220.  
  221.  
  222.  
  223. int meter(char a){
  224.  
  225.     nodo* nuevo = new nodo;
  226.  
  227.     nuevo->smb=a;
  228.  
  229.     nuevo->next=first;
  230.  
  231.     first=nuevo;
  232.  
  233.     return 0;
  234.  
  235. }
  236.  
  237.  
  238.  
  239. int sacar(){
  240.  
  241.     if(first==NULL)
  242.  
  243.         return 0;
  244.  
  245.     if(first->next==NULL){
  246.  
  247.         delete first;
  248.  
  249.     }
  250.  
  251.     nodo* actual=first->next;
  252.  
  253.     nodo* temp=first;
  254.  
  255.     first=actual;
  256.  
  257.     delete temp;
  258.  
  259.     return 0;
  260.  
  261. }
  262.  
  263.  
  264.  
  265. char obtener(){
  266.  
  267.     return first->smb;
  268.  
  269. }

Automata de Pila

Califica el tema:
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

FIN DE SEMESTRE

June 16, 2007 root General, Parsing, Programación No Comments

A que no saben qué? Llegó fin de semestre y la semana y media para los exámenes (recuperaciones, extraordinarios), por lo tanto, como soy relisto xD estuve esta semana sin navegar mucho :P.

Resumiendo las materias (copiando a la madona):

Matemáticas V: :):):):(:(:(
Teoría de la Computación: :):):):):):)
Desarrollo sustentable: :):):):):):)
IO: >:( N/A
Circuitos: :):):):):(:(

Como sea, me llevo buenos cimientos sobre analizadores sintácticos, circuitos y matemáticas xD (que realmente fueron las únicas materias rescatables). Lo bueno es que la semana que viene ya prácticamente se termino todo, dos días más para extraordinarios y se acabo :D (no pregunten si me llevo extras de mate XD).

Bueno, hoy tengo mucho sueño O.o y les comparto un pequeño programa (que se puede pasar a POO y demás yerbas, pero por el tiempo encima, ps 8) que pasa de un gramática libre de contexto a la FNC (forma normal de chomsky) con algunas restricciones :P.

El código es:

PLAIN TEXT
C++:
  1. /**
  3. Descripcion: Convierte a forma normal de chomsky.
  5.                      
  7. Ejemplo:
  9.        
  11.         Gramatica:
  13.             A -> Ac    Donde: A     - Es un no terminal
  15.             A -> w           Ac   - Es la derivacion del no terminal A
  17.            
  19.         Gramatica en Forma Normal de Chomsky:
  21.             A -> AZ
  23.             A -> w
  25.             Z -> c
  27.            
  29. Notas:
  31.         1) Los terminales deben ser de un solo caracter.
  33.         2) Como terminales acepta a-z y +,-,*,/,%,( y ).
  35.         3) Las derivaciones no deben contener espacios.
  37.             
  39. **/
  40.  
  41.  
  42.  
  43. #include<iostream.h>
  44.  
  45. #include<stdlib.h>
  46.  
  47. #include<stdio.h>
  48.  
  49. #include<string.h>
  50.  
  51.  
  52.  
  53. typedef char cadena[80];
  54.  
  55.  
  56.  
  57. struct g{
  58.  
  59.     char nterminal;
  60.  
  61.     cadena derivacion;
  62.  
  63. };
  64.  
  65.  
  66.  
  67. g gramatica[20];
  68.  
  69. g fnc[30];
  70.  
  71.  
  72.  
  73. int pos=0;
  74.  
  75. int pos2=0;
  76.  
  77. int convertir();
  78.  
  79. int sprReglasUnitarias();
  80.  
  81. int verificar();
  82.  
  83. int duplicidad(char,int,int);
  84.  
  85. int crear(int,char,int,int);
  86.  
  87. int eliminar(char,int);
  88.  
  89. int terminal(int,int);
  90.  
  91. int noTerminal(int,int);
  92.  
  93.  
  94.  
  95. int main(){
  96.  
  97.     system("CLS");
  98.  
  99.    
  100.  
  101.     cout<<"Escribe una gramatica: "<<endl;
  102.  
  103.     cout<<"Para terminal: $"<<endl;
  104.  
  105.     do{
  106.  
  107.         cout<<"No terminal: "; cin>>gramatica[pos].nterminal;
  108.  
  109.         gramatica[pos].nterminal=toupper(gramatica[pos].nterminal);
  110.  
  111.         if(gramatica[pos].nterminal!='$'){
  112.  
  113.             cout<<"Derivacion: "; cin>>gramatica[pos].derivacion;
  114.  
  115.             pos++;
  116.  
  117.         }
  118.  
  119.         else{
  120.  
  121.             break;
  122.  
  123.         }
  124.  
  125.     }while(pos<20);
  126.  
  127.  
  128.  
  129.     system("CLS");
  130.  
  131.     cout<<"La gramatica es:"<<endl;
  132.  
  133.     for(int j=0; j<pos; j++){
  134.  
  135.         cout<<gramatica[j].nterminal<<" -> "
  136.  
  137.                 <<gramatica[j].derivacion<<endl;
  138.  
  139.     }
  140.  
  141.     convertir();
  142.  
  143.     cout<<"La gramatica en FNC:"<<endl;
  144.  
  145.     for(int j=0; j<pos2; j++){
  146.  
  147.         cout<<fnc[j].nterminal<<" -> "
  148.  
  149.                 <<fnc[j].derivacion<<endl;
  150.  
  151.     }
  152.  
  153.  
  154.  
  155.     system("PAUSE");
  156.  
  157.  
  158.  
  159.     return 0;
  160.  
  161.  
  162.  
  163. }
  164.  
  165.  
  166.  
  167. int convertir(){
  168.  
  169.    
  170.  
  171.     // Suprime reglas unitarias
  172.  
  173.     sprReglasUnitarias();   
  174.  
  175.     // Verifica y da formato a la forma normal de chomsky
  176.  
  177.     verificar();
  178.  
  179.     return 0;   
  180.  
  181. }
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189. int sprReglasUnitarias()