III.2 Programación
Dirigida por Sintaxis
(Un Método de Desarrollo de
Sistemas Basado
en el Lenguaje del Usuario)
Fernado Galindo Soria*
Resumen
La Programación Dirigida por Sintaxis es un método de desarrollo basado en la Lingüística Matemática y orientado a facilitar la comunicación hombre-máquina.
Este método tiene la característica de permitir desarrollar el sistema de información a partir del lenguaje del usuario, por lo que, el manejo de requerimientos se realiza en un “lenguaje natural restringido” parecido al que utiliza el usuario en su comunicación dentro del área problema.
La idea original partió de los métodos de construcción de compiladores con los cuales a partir de la gramática de un lenguaje se puede construir un traductor capaz de reconocer instrucciones en ese lenguaje, por lo que originalmente se construyeron reconocedores que tenían como entrada la gramática de un lenguaje muy restringido (tipo FORTRAN, BASIC ó PASCAL) y que interpretaba instrucciones de éste lenguaje. Más adelante se amplio el concepto de lenguaje y se construyeron traductores de lenguajes orientado a base de datos, sistemas operativos y validación de datos entre otros, para lo cual únicamente se cambió la gramática, ya que el reconocedor siguió siendo el mismo, por lo que se vio que ahora el problema principal era encontrar la gramática representativa de un lenguaje dado, ya que contando con la gramática el proceso de reconocimiento se tenía resuelto (y en realidad existen muchisimos métodos de reconocimiento de un lenguaje a partir de su gramática en los libros de construcción de compiladores), por lo que se buscaron y desarrollaron métodos de inferencia gramatical con los cuales se puede encontrar la gramática de un lenguaje a partir de ejemplos de éste. (ejemplos de estos métodos aparecen en trabajos sobre reconocimiento sintáctico de patrones), más adelante se reordenaron éstos métodos para que quedaran en una forma lógica,
* Fernando Galindo Soria, enero 1988
en la cual primero se estudia el área y se encuentran ejemplos significativos del lenguaje (Análisis), más adelante se obtiene una gramática con atributos que representa el lenguaje (Diseño) y finalmente se construye el reconocedor del lenguaje (Implantación).
Introducción
En la actualidad se considera que el proceso de
razonamiento se desarrolla principalmente mediante métodos deductivos e
inductivos; en los métodos deductivos se
aplica un conjunto de reglas
preestablecidas para encontrar la solución de un problema dado y por su
parte los métodos inductivos buscan obtener precisamente reglas generales o
patrones a partir de casos particulares, de donde se ve que son métodos
complementarios.
Sin embargo, en
la actualidad, prácticamente todas las formas de programación que se utilizan
se orientan al manejo de sistemas de
tipo deductivo (o sea que aplican un conjunto de reglas preestablecidas
para resolver un problema) y esto ocurre independientemente de la aplicación
(nomina, manejador de base de datos, sistema experto, simulador de juegos,
etc.) y del lenguaje o herramienta automatizada que se utilice (COBOL, FORTRAN,
Pascal, LISP, PROLOG, Lotus, etc.), por lo que el informático o programador
tiene que desarrollar la parte inductiva del problema a mano (lo cual ha
propiciado el surgimiento de métodos para encontrar reglas generales para
resolver problemas como son: el Desarrollo de Sistemas, Algorítmica, Ingeniería
de Software, Ingeniería de Conocimientos, etc.).
Por esto surge
la idea de desarrollar y en su caso automatizar métodos de Programación de tipo Inductivo mediante los cuales sea
relativamente fácil encontrar el conjunto de reglas generales de un problema a
partir de casos particulares.
En éste
documento se presenta un método de programación de tipo inductivo basado en la
Teoría de Lenguajes y en los métodos de Reconocimiento de Patrones (o formas) y
orientados a facilitar la comunicación entre el usuario y la computadora en un
lenguaje lo más natural posible y al manejo por parte de la computadora y de
formas ó patrones más que de datos o conocimientos específicos.
Este método
tiene la característica de permitir desarrollar el sistema de información a
partir del lenguaje del usuario. Por lo que, el manejo de requerimientos se
realiza en un “ lenguaje natural restringido” parecido al que utiliza el
usuario en su comunicación dentro del área problema. A pesar de que
tradicionalmente en la literatura se presenta el problema de manejo del
lenguaje natural como un problema de alta complejidad y que por tal motivo sólo
puede ser atacado por personas de muy alto nivel y no es factible su manejo por
la generalidad de los informáticos, sin embargo, se ha detectado que éste
planteamiento es erróneo y que por el contrario, atacar los problemas
informáticos a base del “lenguaje natural restringido” no sólo es más sencillo
que los enfoque tradicionales sino que además permite resolver los problemas de
una forma más completa, ya que al encadenarse con los métodos de reconocimiento
sintáctico patrones se tiene un doble mecanismo en el cual se parte de múltiples
ejemplos del lenguaje del usuario, se puede encontrar una gramática en la cual
se encuentra precisamente representada la forma del lenguaje, y a partir de
esta gramática es relativamente fácil construir por ejemplo las instrucciones
de un sistema de información o el conjunto de reglas de inferencia de un
sistema experto, de donde el sistema experto, el sistema de información se
transforma en la parte deductiva de un sistema mucho más poderoso.
La idea de éste
método surge de los métodos de construcción de compiladores con los cuales a
partir de la gramática de un lenguaje se puede construir un traductor capaz de
reconocer instrucciones de ese lenguaje, por lo que originalmente se
construyeron reconocedores que tenían como entrada la gramática de un lenguaje
muy restringido (tipo FORTRAN, BASIC ó Pascal) y que interpretan instrucciones
de éste lenguaje. Más adelante de amplió el concepto de lenguaje y se
construyeron traductores de lenguajes orientados a base de datos, sistemas
operativos y validación de datos, entre otros. Para lo cual únicamente se
cambió la gramática, ya que el reconocedor siguió siendo el mismo, por lo que
se vió que ahora el problema principal era el de encontrar la gramática
representativa de un lenguaje dado, ya que contando con la gramática el proceso
de reconocimiento se tenía resuelto (y en realidad existen muchisimos métodos
de reconocimiento de un lenguaje a partir de su gramática en los libros de
construcción de compiladores) por lo que se buscaron y desarrollaron métodos de
inferencia gramatical, con los cuales se puede encontrar la gramática de un
lenguaje a partir de ejemplos de éste. (ejemplos de éstos métodos aparecen en
trabajos sobre reconocimiento sintáctico de patrones), más adelante se
ordenaron estos métodos para que quedaran en una forma lógica y al método
resultante se le llamó Programación Dirigida por Sintaxis.
En la
actualidad éste método se ha utilizado para desarrollar sistemas en áreas tan
disímbolas como construcción de compiladores, sistemas operativos, editores,
bases de datos, comunicación de datos, seguridad, etc.; lenguajes para paquetes
estadísticos, de validación de datos, de control de paquetes de graficación y
simuladores de robots; y aplicando el concepto de lenguaje en áreas no
tradicionales se han utilizado para enseñar a la computadora a reconocer reglas
ortográfica, análisis de contenido, reconocimiento de imágenes, aprendizaje de
juegos (viendo las imágenes y las jugadas como ejemplos de oraciones y para
desarrollar modelos neurales y secuencias lógicas de actividades) por lo que
como se observa, el potencial de ésta herramienta es muy grande, ya que en
contra de lo que se maneja tradicionalmente, es relativamente sencillo
construir sistemas capaces de reconocer un “lenguaje natural restringido“, por
lo que ésta herramienta ha trascendido el área académica se utiliza
actualmente, tanto en empresas privadas como en diversas áreas del sector
público, con el fin de desarrollar sus sistemas con una orientación mayor hacia
el usuario, por lo que, uno de los objetivos de éste trabajo es el de difundir
éste tipo de métodos y
lograr que un grupo mayor de la comunidad I.A. se involucre en su utilización y
principalmente en su estudio, ya que es un área nueva y existen múltiples temas
abiertos de investigación, como por ejemplo:
1) Ampliación del concepto de lenguaje.
2) Inferencia Gramatical
3) Automatización de las diferentes etapas del
método.
4) Construcción de Sistemas Evolutivos.
Con éste documento se
pretende entre otras cosas:
1) Mostrar un método de programación no
tradicional.
2) Lograr que los sistemas de información
tengan comunicación más orientada al usuario.
3) Mostrar que los métodos de construcción de
compiladores no son exclusivos de los especialistas en esa área, sino que
lo mismo se puede aplicar para construir un compilador, un sistema manejador de
base de datos, un sistema operativo, una nómina ó sistema de inventarios, con
lo cual se ve en un momento dado el hecho de tener diferentes aplicaciones no
implica que no pueda usar la misma herramienta.
4) Presentar un proceso integrado para resolver
problemas y que actualmente no se maneja de ésta forma (por ejemplo en los
cursos de compiladores es común que se indique como obtener el lenguaje ó a
partir de éste cómo obtener la gramática).
5) Mostrar la gran importancia que tiene la
teoría de gramáticas (en general los sistemas formales) como herramientas
para el desarrollo de sistemas.
6) Mostrar la gran importancia que tiene la
Teoría de Reconocimiento de Formas (en particular el Reconocimiento
Sintáctico de Patrones) como herramientas para el desarrollo de sistemas y
mostrar como su integración con la Teoría de Gramáticas proporciona una
herramienta aplicable en diversas aplicaciones.
I Conceptos Generales
Como se ha comentado anteriormente éste método se basan
principalmente en herramientas de Lingüística Matemática y de Reconocimiento
Sintáctico de Patrones y en particular en las Gramáticas Libres de Contexto (o
tipo 2 de la Jerarquía de Chomsky)por lo que como primer punto se presentará en
forma general éste concepto y más adelante se mostrará su ámbito de aplicación.
1 Definición de Gramáticas Libre de Contexto
Una Gramática Libre de Contexto es una herramienta, con
la cual se puede describir la estructura de las oraciones de una lengua, ésta
herramienta consiste básicamente en cuatro componentes: G = <Vn , Vt, S, P
> donde:
1) Vn
es un conjunto de elementos o variables no terminales que sirven para
representar los cambios de un estado a otro, normalmente las variables no
terminales se denotan con letras mayúsculas.
2) Vt
es un conjunto de elementos o variables terminales que equivalen a las señales
u órdenes sobre el sistema, normalmente se denotan con letra minúscula.
3) Se
tiene un elemento no terminal que indica el estado inicial o el axioma del
sistema y se denota como S.
4) P es
un conjunto de reglas con las cuales se describe la estructura del problema y
son de la forma:
A ®
a
donde A
es algún estado e indica que esa regla sólo se aplica si se encuentra el
problema en el estado A y a es una cadena de
estados y señales.
P es un
conjunto de relaciones o reglas de producción con domino y contradominio en V*
(V = Vn È Vt). V* es el conjunto
de todas las posibles cadenas formadas por la concatenación de elementos de V.
Si a Î V* se dice que a es una cadena de
elementos.
Ejemplo: El conjunto de reglas:
S ® v A
A ® + v A
A ® ;
Indican que si se está en el estado S entonces se debe
verificar que llegue la señal v, si
llega v entonces se pasa al estado
A. En el caso del estado A se tienen dos posibles caminos: si llega la señal + se toma uno y si llega la señal ; se
toma el otro. Por simplicidad cuando existen varios caminos se puede denotar
como:
A ® + v A | ;
donde el símbolo |
indica camino alterno.
Si no llega alguna de las señales esperadas entonces se
detecta que ese no era un camino válido y se regresa al estado anterior a
buscar otro camino, si ya no existe ninguno camino posible entonces la señal es
errónea.
En éste ejemplo en particular las cadenas de señales
válidas es de la forma:
v ;
v + v ;
v + v + v ;
…
v + v + . . . + v ;
O sea ésta gramática espera señales que indiquen sumas de
variables.
2 Equivalencia Estructural entre Gramáticas y
Sistemas de Información
Si partimos de que un lenguaje es un mecanismo con el que
se puede representar y transmitir el conocimiento y observamos el lenguaje que
se utiliza el alguna área problema podemos encontrar que en éste se encuentran
en forma natural los componentes de un sistema de información, ya que podemos encontrar un conjunto de
acciones que se refieren a ciertos objetos en un orden dado, donde las
acciones del lenguaje se pueden representar como acciones en el sistema; a
partir de los objetos se pueden obtener las entidades, atributos y valores de
la estructura de datos y finalmente a partir del orden en que aparecen las
acciones y objetos en la oración se puede encontrar el orden o estructura de
control del Sistema de Información.
En particular,
mediante la gramática que representa el lenguaje se puede representar la
estructura del Sistema de Información. Esta posibilidad de representar un
sistema como una gramática permite por ejemplo obtener la gramática del Sistema
de Información y estudiar la estructura del sistema y en su momento encontrar
una nueva gramática que realice lo mismo (gramática equivalente) y a partir de
ésta proponer un mejor sistema.
Por lo que a
continuación se verá que cualquier sistema, programa o estructura de datos es
estructuralmente (también se le dice débilmente) equivalente a una gramática y
como esto nos permite utilizar las gramáticas como un mecanismo para
representar sistemas (como los diagramas de Warnier, de Flujo, de Flujo de
Datos, etc.)
2.1 Equivalencia de Gramáticas y Programas
Como primer punto, se verá que la estructura de un
programa se puede representar con una gramática y viceversa.
La equivalencia
entre una gramática y un programa se puede observar si se toma un programa
típico.
Programa típico
Rutina A
Ejecuta B
Si C entonces D sino E
Mientras F ejecuta G
Llama a D
Fin rutina
ya que en éste se pueden encontrar cuatro estructuras de
control básicas:
1) Sentencias
2) Interacciones
3) Decisiones
4) Recursión
y cada una de estas puede representarlas en abstracto
mediante una gramática:
1) Sentencias: A ® B
2) Iteraciones: A ® E*
3) Decisiones A ®{C | D}
4) Recursiónes: A ® d A
Por lo que una rutina de la forma:
Rutina A
B
D ó E
(G)*
Fin rutina
se puede representar mediante la siguiente producción
A ®B {C | D} G*
o de otra forma
A ® B X Y
X ® D | E
Y ® G*
Por otro lado, a partir de la gramática se puede
encontrar el programa, ya que:
1) S ® D
equivale a
Rutina S
llama a D
Fin rutina
2) S ® A B C
equivale
a
Rutina S
llama a A
llama a B
llama a C
Fin rutina
3) S ® a A
equivale
a
Rutina S
Si a entonces llama a A
Fin rutina
4) S ® a A | b B
equivale
a
Rutina S
Si a entonces llama a A
sino Si b entonces llama a B
Fin si
Fin rutina
5) S ® a A | b B | c C | … | z Z
equivale
a
Cualquier programa es equivalente estructuralmente a una
gramática por lo que se puede tomar un programas, encontrar su gramática y
detectar:
1) El
tipo de lenguaje que tiene.
2)
Problemas estructurales.
3) Oraciones
que no reconoce.
4)
etc., etc.
Se puede tomar
una gramática y construir un programa que la representa, con lo que se tendría
el Sistema de Información.
2.2 Equivalencia entre Grmáticas y Diagramas de
Warnier
Los diagramas de Warnier son herramientas para
representar sistemas, ya que absorben las características de los diagramas
Top/Down y de la programación estructurada con la ventaja de ser sencillos de
manejar y con ellos se puede representar fácilmente, por ejemplo, Sistemas de
Información, Estructuras de Datos y programas de tipo administrativo.
En estos
diagramas se permite:
1) La
secuencia. La rutina A se compone de B, C y D
2) La
decisión.En la rutina A se ejecuta B ó C
3) La
iteración.En la rutina A se repite el proceso B, b veces
Dado
que es muy fácil obtener los programas y el sistema de información del diagrama
de Warnier, este es de aplicación general, por lo que veremos que es
equivalente a una gramática.
1)
equivale
a:
A ® B C D
2)
equivale
a:
A ® B | C
3)
equivale
a:
A ® {B}b C
como no
es de uso común el exponente se puede sustituir por una gramática recursiva:
A ® B X
X ® B X | C
El proceso de equivalencia
es el mismo por lo que por ejemplo de la gramática:
S ®
a A | X
A ® b B | C e f
X ®
j k l m
2 Método de Programación Dirigida por Sintaxis
El hecho de que sea relativamente fácil representar un
sistema de información como una gramática y que por el otro lado la gramática
represente los patrones o reglas generales de algún lenguaje plantea la
posibilidad de contar con un mecanismo que nos permita obtener a partir del
lenguaje la estructura de un sistema de información y de ahí obtener el
sistema.
A continuación
describiremos el método de Programación Dirigida por Sintaxis y en los
siguientes puntos se presentará a detalle cada paso con el fin de mostrar su
uso y algunas de sus posibilidades.
El método en
general consta de una fase de Análisis, en la cual se estudia el área significativa
y se encuentran ejemplos significativos del lenguaje, otra de Diseño en la cual
se encuentra una gramática con atributos que representa los patrones del
comportamiento del lenguaje y la estructura del sistema y finalmente una fase
de Implantación, donde se desarrollan las herramientas para reconocer el
lenguaje.
Detallando un
poco, el método consta de las siguientes parte:
1)
Análisis:
i)
Detección de un área de aplicación o campa problema.
ii)
Estudio del lenguaje del área y detección de ejemplos significativos del
lenguaje.
2)
Diseño:
i)
Detección de las unidades léxicas del enunciado.
ii)
Obtención de una Gramática Generativa Canónica, mediante la sustitución de cada
una de las unidades léxicas en las oraciones por un símbolo que indica su tipo
de unidad léxica e introduciendo un axioma que genere las oraciones.
iii)
Obtención de una Gramática Generalizada mediante Técnicas de Inferencia
Gramatical.
iv)
Obtención de la Gramática con Atributos mediante la inclusión de rutinas
semánticas.
v) Detección
de problemas estructurales y obtención de una gramática determinística (si
existe) o de una gramática con pocos problemas.
3)
Implantación:
i)
Construcción de una Tabla Gramatical en la que se representa la estructura del
sistema a partir de la gramática.
ii)
Construcción o uso de algún Reconocedor de Lenguaje que recibe por un lado, la
gramática de lenguaje (que representa los patrones de comportamiento del
sistema) y por otro los requerimientos del usuario en un lenguaje natural,
orientado a la aplicación y genera respuestas a los requerimientos.
III Estudio del Lenguaje y Detección de Ejemplos
Significativos
Dado que se tiene un área de aplicación o algún problema
a resolver, el primer punto importante consiste en la detección del lenguaje
involucrado.
Tradicionalmente el concepto de lenguaje está muy
restringido y por lo común o se
piensa en instrucciones muy restringidas (tipo FORTRAN, Pascal, PROLOG, JCL,
QUERY, etc.) o si bien va en términos de “Lenguaje natural restringido” , con
lo que se quiere indicar algún subconjunto del Español escrito, sin embargo el
concepto de lenguaje es mucho más amplio, ya que cualquier mecanismo en el que
se encuentre un conjunto de elementos (alfabeto) sobre los que se puede aplicar
un conjunto de reglas para relacionarlas (sintaxis) y asociarle un significado
(semántica) se puede decir que se cuanta con un lenguaje, en su momento puede
existir lenguajes de múltiples tipos : natural escrito, simbólico, hablado,
visual, etc.; por lo que cuando se desarrolla un sistema mediante éste método,
el universo de posibles mecanismos de comunicación se amplio enormemente y en
su momento es un factor a tomar en cuanta, ya que sería poco adecuado
restringirse a lenguajes tradicionales (menú, ensamblador, pseudocódigo, natural
restringido, etc.) si existe algún otro lenguaje más adecuado.
1) En
diagnóstico médico, la conversación del paciente con el médico.
2) En
la nómina, la descripción escrita de los cambios o modificaciones requeridas.
3) En
visión, la imagen a reconocer. La cual por ejemplo, se puede transformar en una
oración tradicional mediante la aplicación de las técnicas de las primeras
vecinos y número de forma.
4)
Juegos de Tablero, la trayectoria de la pieza. En éste caso la idea es que la
trayectoria de una pieza en el tablero se puede ver como una imagen visual y
por tanto aplicarle las herramientas de 3)
5)
Características Especiales, en éste caso el concepto de lenguaje pasa a otro
nivel, ya que lo que se pretende es representar conceptos no tangibles como arriba,
abajo, al lado, etc. En éste caso se requiere la confluencia de varios
mecanismos de captación de información que la integran en una sola oración, por
ejemplo (mecanismo visual, mecanismo especial y mecanismo escrito).
6)
Atributos Generales, partiendo de la idea anterior del uso de varios mecanismos
de captación que integran en una sola oración se pueden captar características
como: más claro, más obscuro, verde, azul, curvo, etc.
7)
Características Temporales, se puede integrar en una sola opción, eventos
ocurridos en diferentes tiempos,
(introduciendo
un operador temporal é) y captar por ejemplo
cambios lógicos en un sistema (por ejemplo el crecimiento de una célula se rige
por esos cambios lógicos, ya que no se transforma en forma brusca).
8) En
pruebas de personalidad, éste es un ejemplo en el cual el concepto de lenguaje
es de una simplicidad extrema y su fuerza es muy grande, ya que en éste caso la
oración está formada únicamente por una cadena de letras, donde cada letra
representa la respuesta a una pregunta de la prueba (normalmente tienen un máximo de 5 posibles respuestas) y la
cadena representa todas las posibles respuestas dadas por una persona, de donde
una oración típica se parece a una cadena binaria.
Como se observa
de los ejemplos anteriores el concepto de lenguaje y es importante saber elegir
el que se adecue más a nuestro problema. Ya que se eligió un lenguaje X el
siguiente paso consiste en captar muchos ejemplos de oraciones (grabando,
observándolo, sientiéndolo, etc.) como ejemplos distintivos o que muestran
alguna característica gramatical que los distinga.
IV Detección de las Unidades Léxicas
En ésta etapa es necesario analizar las oraciones con el
fin de detectar las unidades léxicas ( Unidades mínimas con significado en el
lenguaje) y clasificarlas en tipo de unidades léxicas, por ejemplo:
1) En
la información visual se puede tener la siguiente convención: