Introducción
Esta entrada del blog pretende explicar brevemente las ideas que he plasmado en el código del Proyecto GR para tratar expresiones regulares.
El tratamiento de autómatas es sólo una parte del Proyecto GR. Este proyecto pretende definir una estructura de datos que sea capaz de ir reconociendo la sintaxis del castellano. Intenta que la aplicación realice consultas a internet para averiguar aquella palabra que no tenga previamente procesada debiendo de obtener su tipo: adjetivo, sustantivo, pronombre… sus características como son el género, número… sus definiciones, etc. Toda esta información se va almacenando en una estructura de datos muy compleja que no viene al caso.
Caí en la cuenta que es un desperdicio de memoria y tiempo tener que trabajar con números por ejemplo ya que son infinitos y el valor de un número no hace falta estar consultándolo a internet, 1 es 1.
Esto me recordó a la asignatura de Autómatas y me puse como reto programar los algoritmos correspondientes para poder trabajar con Autómatas No Deterministas Landa, Autómatas Deterministas y Autómatas Deterministas Mínimos.
Pido disculpas si no utilizo correctamente los términos o nombres de los autómatas, hace años que di la asignatura y todo se olvida.
Estructura básica
El trabajo se reparte en dos bloques. Dada una cadena de texto se le pasa como parámetro al primer bloque que corresponde a los autómatas que realizarán el reconocimiento de dicha cadena para ver si cumplen alguna expresión regular de las programadas previamente. En el caso de que así sea nos devolverá el o los estados finales a los que ha llegado. Dichos estados finales llevarán asociado el nombre de la expresión regular reconocida. Ya sabiendo los nombres de las expresiones reconocidas, el segundo bloque les dará significado. Por ejemplo:
Teniendo las ER correspondientes a lo que es un dígito, un número natural, un número entero y un número real, si como cadena de entrada se le pasa al primer bloque -8 nos devolverá un único estado final correspondiente a número entero. Si a este mismo ejemplo se le pasa 9 nos dirá que se trata de un dígito, número natural y número entero. El segundo bloque nos diría que el valor del dígito 9 es 9 por ejemplo. Aquí parece evidente, ¿pero qué ocurre con un caso más complejo como pueden ser los números romanos…? El primer bloque tendría una expresión regular indicándole que un número romano es aquel que está formado por una sucesión de símbolos romanos como son I, V, X, L, C, M, () para indicar miles. El autómata reconocería una entrada como puede ser XX, pero es el segundo bloque el que lo interpreta y nos dice que se trata de un natural cuyo valor es 20.
Me voy a centrar en el primer bloque.
Se utilizan las siguientes estructuras de datos para trabajar en el primer bloque: ANDLT, ADFMínimo y dos diccionarios, uno que utiliza los nombres de las ER para su reconocimiento y otro directamente la ER. En ambos casos los nodos hoja apuntan a un ADFMínimo.
ANDLT
En su estructura se almacena la ER propiamente dicha, el nombre que se le ha dado, los símbolos que utiliza, la tabla de transiciones y los estados finales.
Por Ejemplo:
ER: 0+1+2+3+4+5+6+7+8+9
Nombre: digito
Símbolos: {0,1,2,3,4,5,6,7,8,9, L} L corresponde a Landa
Tabla de transiciones:
Q0 con L⇨Q0, Q1, Q3, Q5, Q7, Q9, Q11, Q13, Q15, Q17, Q19
Q1 con 0 ⇨Q2
Q2 con L ⇨Q21, Q21 estado final, 0 es un dígito
Q3 con 1 ⇨Q4
Q4 con L ⇨Q21, Q21 estado final, 1 es un dígito
…
Todo aquello que no esté en la tabla de transiciones el algoritmo lo conduce al estado Q-1, es decir, al estado Error.
En este ejemplo sólo hay un estado final Q21, pero se da el caso de que haya más de uno.
AFDMínimo
La estructura es semejante a la de los ANDLT sólo que únicamente hay un estado final, no tiene transiciones Landa y el número de estados es el mínimo.
Diccionarios
Como ya se ha comentado en la estructura de datos hay dos diccionarios. Uno hace las búsquedas por el nombre de la expresión regular, en el ejemplo sería digito y otro busca la propia expresión regular, que sería 0+1+2+3+4+5+6+7+8+9. Ambos nodos hoja de sus correspondientes diccionarios apuntan a la misma AFDMínimo en memoria.
¿Para qué sirven?
Si ya tiene en memoria el ADFMínimo de un dígito, para definir un número natural simplemente en la ER hay que decir:
ER: (digito)(digito)*
Nombre: natural
El diccionario de ADFMínimos se actualiza con (digito)(digito)* y el diccionario de Nombres de ER se actualiza con natural.
Para realizar su ADFMínimo va reconociendo y trabajando de modo recursivo la ER:
Encuentra ( y busca el siguiente ) trabaja con el contenido entre ambos símbolos.
Digito lo localiza en el diccionario de nombres de ER, con lo que ya tiene la tabla de transiciones mínima.
Encuentra ( y busca el siguiente ) pero se encuentra * seguido.
Vuelve a localizar en el diccionario de nombres de ER.
Genera un ANDLT concatenando la primera ER con la segunda ER teniendo en cuenta la *.
Genera un AFDMínimo a partir del ANDLT y actualiza los diccionarios.
Usando los diccionarios nos permite realizar ER más complejas al poder hacer sustituciones.
Estructura global
Un ANDLT lo une todo. Es decir, para cada nueva ER se genera un AFDMínimo usando los diccionarios generando un estado final correspondiente. El ANDLT global lo inserta en su estructura uniéndolo con una transición Landa.
Ejemplo de inserción de nuevas ER:
Inicialmente ANDLTGlobal vacío.
Nueva ER: Digito 0+1+2+3+4+5+6+7+8+9
AFDMínimo: estados [q0, q1], estado final [q1], símbolos {0,1,2,3,4,5,6,7,8,9}
Actualiza diccionario de AFD con 0+1+2+3+4+5+6+7+8+9.
Actualiza diccionario de nombres ER con digito.
Inserta en ANDLTGlobal: estados [q0,q1,q2], estado final [q2 (digito)], símbolos {0,1,2,3,4,5,6,7,8,9,L} donde las transiciones de q1 y q2 son copiadas del AFDMínimo de digito respetando los índices de ANDLTGlobal y q0 a q1 mediante una transición Landa.
Nueva ER: Natural (Digito)(Digito)* que significa uno o infinitos dígitos uno tras otro.
AFDMínimo: estados [q0, qn], estado final [qn], símbolos {0,1,2,3,4,5,6,7,8,9}
Actualiza diccionario de AFDMínimo con (0+1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*. Para su cálculo busca el contenido de los paréntesis en los diccionarios y los concatena los resultados de forma recursiva y por supuesto teniendo en cuenta los *. En el caso de encontrarse partes de la ER ya almacenados en los diccionarios copia sus tablas de transiciones. De no ser así los actualizará para que no vuelva a tener que calcularlas.
Actualiza diccionario de nombres ER con Natural. Cuando vuelva a tener que trabajar con un natural ya tiene toda la tabla de transiciones mínima calculada.
Inserta en ANDLTGlobal: estados [q0,q1,q2,q3,qn+2], estados finales [q2 (digito), qn+2 (natural)], símbolos {0,1,2,3,4,5,6,7,8,9}, donde desde q3 hasta qn+2 son copiados del AFDMínimo del natural respetando los índices de ANDLTGlobal y unidas mediante q0 a q3 con una transición Landa.
Reconocimiento de ER
A reconocer: 94
Estado: q0, Estados siguientes: q0,L a q1 y a q3, queda por reconocer: 94
Estado: q1, Estados siguientes: q1, 9 a q2, queda por reconocer 4.
Estado: q2 Final (digito), Estados siguientes: ninguno, queda por reconocer 4 No es digito.
Estado: q3, Estados siguientes: q3, 9 a q4, queda por reconocer 4.
Estado: q4, Estados siguientes: q5, 4 a qn, queda por reconocer nada.
Qn final (natural), es un natural.
Es una explicación sencilla aunque en realidad no trabaja de modo recursivo sino paralelamente con ayuda de Landa Clausura:
A reconocer: 94
(Q0),L -> (q1,q3)
(q1,q3),9 -> (q2,q4)
(q2,q4),4 -> (qn) final donde qn es natural.
El programa en ejecución
ANDLT: 10 [save] #guardar
ANDLT: 21 [resetAll] #resetear
ANDLT: 26 [newER] #ER
Según va insertando ER muestra el número de estados del ANDLTGlobal seguido del nombre de la ER entre corchetes y la ER.
Las que comienzan por # corresponden a comandos propios del programa.
ANDLT: 29 [digito] 0+1+2+3+4+5+6+7+8+9
ANDLT: 32 [natural] (digito)(digito)*
Las ya vistas en los ejemplos anteriores.
ANDLT: 36 [entero~positivo] (natural)+(@(natural))
ANDLT: 40 [entero~negativo] -(natural)
ANDLT: 44 [entero] (entero~positivo)+(entero~negativo)
Un entero positivo es un natural o +natural. Uso @ para no poner + ya que lo interpreta como una concatenación en lugar de un símbolo. De igual modo usa ~ para no insertar espacios en blanco en el nombre de una ER.
Un entero negativo es un natural precedido del símbolo –
Un entero puede ser un entero positivo o un entero negativo.
ANDLT: 52 [real~positivo] (entero~positivo)+((entero~positivo).)+(@.(natural))+(.(natural))+((entero~positivo).(natural))
ANDLT: 58 [real~negativo] (entero~negativo)+((entero~negativo).)+(-.(natural))+((entero~negativo).(natural))
ANDLT: 64 [real] (real~positivo)+(real~negativo)
Real positivo puede ser:
Entero positivo
Entero positivo.
+.natural
.natural
Entero positivo.natural
Lo mismo con los reales negativos.
ANDLT: 69 [fraccion~natural] (natural)/(natural)
ANDLT: 76 [fraccion~entera] (entero)/(entero)
ANDLT: 87 [fraccion~real] (real)/(real)
ANDLT: 98 [fraccion] (fraccion~natural)+(fraccion~entera)+(fraccion~real)
Todos los tipos de fracción posible.
ANDLT: 109 [número] (digito)+(natural)+(entero)+(real)+(fraccion)
ANDLT: 362 [digito~numeral~entero] ~+y+cero+ceros+un+uno+una+dos+tres+cuatro+cinco+seis+siete+ocho+nueve+diez+once+doce+trece+catorce+quince+dieciséis+diecisiete+dieciocho+diecinueve+veinte+veintiuno+veintiun+veintiuna+veintidós+veintitrés+veinticuatro+veinticinco+veintiséis+veintisiete+veintiocho+veintinueve+treinta+cuarenta+cincuenta+sesenta+setenta+ochenta+noventa+cien+ciento+cientos+doscientos+trescientos+cuatrocientos+quinientos+seiscientos+setecientos+ochocientos+novecientos+mil+millón+billón+trillón+millones+billones+trillones+más+menos
ANDLT: 583 [numeral~entero] (digito~numeral~entero)(digito~numeral~entero)*
ANDLT: 986 [numeral~real] (numeral~entero)~con~(numeral~entero)
ANDLT: 1390 [numeral~fraccion~EE] (numeral~entero)~entre~(numeral~entero)
ANDLT: 1998 [numeral~fraccion~ER] (numeral~entero)~entre~(numeral~real)
ANDLT: 2606 [numeral~fraccion~RE] (numeral~real)~entre~(numeral~entero)
ANDLT: 3418 [numeral~fraccion~RR] (numeral~real)~entre~(numeral~real)
ANDLT: 4637 [numeral~fraccion] (numeral~fraccion~EE)+(numeral~fraccion~ER)+(numeral~fraccion~RE)+(numeral~fraccion~RR)
Las ER para poder escribir los números de modo numeral.
ANDLT: 4640 [digito~romano] i+v+x+l+c+d+m+ł+¶
ANDLT: 4643 [numero~romano] (digito~romano)(digito~romano)*
Para interpretar los números romanos.
ANDLT: 4651 [digito~ordinal~forma~1] .º+.êr+.ª+.ôs+.âs
ANDLT: 4658 [ordinal~forma~1] (natural)(digito~ordinal~forma~1)
ANDLT: 4665 [digito~ordinal~forma~2] º+êr+ª+ôs+âs
ANDLT: 4671 [ordinal~forma~2] (natural)(digito~ordinal~forma~2)
ANDLT: 4683 [digito~ordinal~forma~3] er.+ro.+do.+to.+mo.+vo.+no.+ros.+dos.+tos.+mos.+vos.+nos.+ra.+da.+ta.+ma.+va.+na.+ras.+das.+tas.+mas.+vas.+nas.
ANDLT: 4691 [ordinal~forma~3] (natural)(digito~ordinal~forma~3)
ANDLT: 5038 [digito~ordinal~forma~4] ~+vigesimonona+vigesimonono+vigesimonovena+vigesimonoveno+vigesimoctavo+vigesimoctava+vigesimoséptimo+vigesimoséptima+vigesimosexto+vigesimosexta+vigesimoquinta+vigesimoquinto+vigesimocuarto+vigesimocuarta+vigesimotercero+vigesimotercera+vigesimosegundo+vigesimosegunda+vigesimoprimero+vigesimoprimera+decimonona+decimonono+decimonovena+decimonoveno+decimoctavo+decimoctava+decimoséptima+decimoséptimo+decimosexta+decimosexto+decimoquinta+decimoquinto+decimocuarto+decimocuarta+decimotercero+decimotercera+duodécimo+duodécima+decimosegundo+decimosegunda+undécimo+undécima+decimoprimero+decimoprimera+primero+primera+primer+segundo+segunda+tercero+tercera+tercer+cuarto+cuarta+quinto+quinta+sexta+sexto+sétimo+sétima+séptimo+séptima+octavo+octava+nono+nona+noveno+novena+décimo+décima+vigésimo+vigésima+trigésimo+trigésima+cuadragésimo+cuadragésimo+quincuagésimo+quincuagésima+sexagésimo+sexagésima+septuagésimo+septuagésima+octogésimo+octogésima+nonagésimo+nonagésima+duocentésimo+duocentésima+tricentésimo+tricentésima+cuadrigentésimo+cuadrigentésima+quingentésimo+quingentésima+sexcentésimo+sexcentésima+septingentésimo+septingentésima+octingentésimo+octingentésima+noningentésimo+noningentésima+centésimo+centésima+milésimo+milésima+millonésimo+millonésima
ANDLT: 5257 [ordinal~forma~4] (digito~ordinal~forma~4)(digito~ordinal~forma~4)*
ANDLT: 5480 [ordinal] (ordinal~forma~1)+(ordinal~forma~2)+(ordinal~forma~3)+(ordinal~forma~4)
Para trabajar con los ordinales.
Reconocimiento de 100
> 100
AFNDL: [entero, entero positivo, natural, número, real, real positivo]
[Num. Nat.] '100'
Valor Números Romanos: C
Valor natural: 100
Valor entero: 100
Valor real: 100.0
Valor numerador: [Num. Ent.] '100'
Valor denominador: [Num. Ent.] '1'
Valor Numeral: cien
Reconocimiento de -89
> -89
AFNDL: [entero, entero negativo, número, real, real negativo]
[Num. Ent.] '-89'
Valor natural: 89
Valor entero: -89
Valor real: -89.0
Valor numerador: [Num. Ent.] '-89'
Valor denominador: [Num. Ent.] '1'
Valor Numeral: menos ochenta y nueve
Reconocimiento de 1002.3 y -124.14
> 1002.3
AFNDL: [número, real, real positivo]
[Num. Real] '1002.3'
Valor natural: 1002
Valor entero: 1002
Valor real: 1002.3
Valor numerador: [Num. Real] '1002.3'
Valor denominador: [Num. Real] '1.0'
Valor Numeral: mil dos con tres
> -124.14
AFNDL: [número, real, real negativo]
[Num. Real] '-124.14'
Valor natural: 124
Valor entero: -124
Valor real: -124.14
Valor numerador: [Num. Real] '-124.14'
Valor denominador: [Num. Real] '1.0'
Valor Numeral: menos ciento veinticuatro con catorce
Reconocimiento de 10/4
> 10/4
AFNDL: [fraccion, fraccion entera, fraccion natural, fraccion real, número]
[Num. Fracc.] '10/4'
Valor natural: 2
Valor entero: 2
Valor real: 2.5
Valor numerador: [Num. Ent.] '10'
Valor denominador: [Num. Ent.] '4'
Valor Numeral: diez entre cuatro
Reconocimiento de -10./.120
> -10./.120
AFNDL: [fraccion, fraccion real, número]
[Num. Fracc.] '-10./.120'
Valor natural: 83
Valor entero: -83
Valor real: -83.33333333333334
Valor numerador: [Num. Real] '-10.0'
Valor denominador: [Num. Real] '0.12'
Reconocimiento de diez mil con quinientos trece entre ocho con dos
> diez mil con quinientos trece entre ocho con dos
AFNDL: [numeral fraccion, numeral fraccion RR]
[Num. Fracc.] '10000.513/8.2'
Valor natural: 1219
Valor entero: 1219
Valor real: 1219.5747560975612
Valor numerador: [Num. Real] '10000.513'
Valor denominador: [Num. Real] '8.2'
Valor Numeral: diez mil con quinientos trece entre ocho con dos
Reconocimiento de 3er.
> 3er.
AFNDL: [ordinal, ordinal forma 3]
Natural: 3
Cifras 1: 3.º
Cifras 2: 3º
Cigras 3: 3ro.
Orginal: tercero
Número: Singular
Género: Masculino
Reconocimiento de cuarto
> cuarto
AFNDL: [digito ordinal forma 4, ordinal, ordinal forma 4]
Natural: 4
Cifras 1: 4.º
Cifras 2: 4º
Cigras 3: 4to.
Orginal: cuarto
Número: Singular
Género: Masculino
Reconocimiento de cmxiv
> cmxiv
AFNDL: [numero romano]
[Num. Rom.] 'cmxiv'
Valor Números Romanos: CMXIV
Valor natural: 914
Valor entero: 914
Valor real: 914.0
Valor numerador: [Num. Nat.] '914'
Valor denominador: [Num. Nat.] '1'
Valor Numeral: novecientos catorce
