Los sistemas Q son un método de transformación de grafos dirigidos según reglas gramaticales dadas , desarrollado en la Universidad de Montreal por Alain Colmerauer entre 1967 y 1970 para su uso en el procesamiento del lenguaje natural . El sistema de traducción automática de la Universidad de Montreal, TAUM-73 , utilizó los sistemas Q como formalismo de lenguaje.
La estructura de datos manipulada por un sistema Q es un gráfico Q, que es un gráfico acíclico dirigido con un nodo de entrada y un nodo de salida, donde cada arco lleva un árbol ordenado etiquetado. Una oración de entrada se representa generalmente mediante un gráfico Q lineal donde cada arco lleva una palabra (árbol reducido a un nodo etiquetado por esta palabra). Después del análisis, el gráfico Q es generalmente un conjunto de caminos de 1 arco, cada arco lleva un posible árbol de análisis. Después de la generación, el objetivo suele ser producir tantos caminos como resultados deseados, nuevamente con una palabra por arco.
Un sistema Q consiste en una secuencia de tratamientos Q, cada uno de los cuales es un conjunto de reglas Q, de la forma <matched_path> == <added_path> [<condition>]. Los tratamientos Q se aplican en secuencia, a menos que uno de ellos produzca el gráfico Q vacío, en cuyo caso el resultado es el último gráfico Q obtenido. Las tres partes de una regla pueden contener variables para etiquetas, árboles y bosques. Todas las variables después de "==" deben aparecer en la parte <matched_path>. Las variables son locales a las reglas.
Un tratamiento Q funciona en dos pasos: adición y limpieza. Primero aplica todas sus reglas exhaustivamente, utilizando instanciación (unificación unidireccional), agregando así nuevas rutas al gráfico Q actual (los arcos agregados y sus árboles se pueden usar para producir nuevas rutas). Si este proceso de adición se detiene, se borran todos los arcos utilizados en alguna aplicación de regla exitosa, así como todos los arcos no utilizados que ya no se encuentran en ninguna ruta desde el nodo de entrada hasta el nodo de salida. Por lo tanto, el resultado, si lo hay (si el paso de adición termina), es nuevamente un gráfico Q. Eso permite encadenar varios sistemas Q, cada uno de los cuales realiza una tarea especializada, formando juntos un sistema complejo. Por ejemplo, TAUM 73 constaba de quince sistemas Q encadenados.
Una extensión de la idea básica de los Q-Systems, es decir, reemplazar la instanciación por la unificación (para decirlo simplemente, permitir "nuevas" variables en la parte del lado derecho de una regla y reemplazar árboles etiquetados parametrizados por términos lógicos) condujo a Prolog , diseñado por Alain Colmerauer y Philippe Roussel en 1972. Los refinamientos en la otra dirección (reduciendo el no determinismo e introduciendo etiquetas tipificadas) por John Chandioux condujeron a GramR, utilizado para programar METEO desde 1985 en adelante.
En 2009, Hong Thai Nguyen de GETALP, [1] Laboratoire d'Informatique de Grenoble [2] reimplementó el lenguaje Q en C, utilizando ANTLR para compilar los sistemas Q y los grafos Q, y un algoritmo propuesto por Christian Boitet (ya que no se había publicado ninguno y se habían perdido las fuentes de la implementación anterior en Fortran ). Esa implementación fue corregida, completada y extendida (a etiquetas que utilizan caracteres Unicode y no solo los caracteres imprimibles del CDC6600 de la versión histórica) por David Cattanéo en 2010-11.