Los sistemas Q son un método de transformaciones de grafos dirigidas según reglas gramaticales dadas , desarrollado en la Universidad de Montreal por Alain Colmerauer en 1967-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ó Q-Systems como formalismo lingüístico.
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 generalmente se representa mediante un gráfico Q lineal donde cada arco lleva una palabra (el árbol se reduce a un nodo etiquetado con esta palabra). Después del análisis, el gráfico Q suele ser un conjunto de trayectorias de 1 arco, cada arco con 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 Q-System consta de una secuencia de Q-tratamientos, cada uno de los cuales es un conjunto de Q-reglas, de la forma <matched_path> == <added_path> [<condition>]. Los tratamientos Q se aplican en secuencia, a menos que uno de ellos produzca el Q-graph vacío, en cuyo caso el resultado es el último Q-graph 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 de manera exhaustiva, utilizando instanciación (unificación unidireccional), agregando así nuevas rutas al Q-graph actual (los arcos agregados y sus árboles se pueden usar para producir nuevas rutas). Si este proceso de adición se detiene, todos los arcos utilizados en alguna aplicación de regla exitosa se borran, así como todos los arcos no utilizados que ya no se encuentran en ninguna ruta desde el nodo de entrada al nodo de salida. Por lo tanto, el resultado, si lo hay (si termina el paso de suma), es nuevamente un gráfico Q. Eso permite encadenar varios Q-Systems, realizando cada uno de ellos una tarea especializada, formando juntos un sistema complejo. Por ejemplo, TAUM 73 constaba de quince Q-Systems 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 derecha 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 mecanografiadas) por parte de 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 gráficos 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 de Fortran). Esa implementación fue corregida, completada y ampliada (a etiquetas que utilizan caracteres Unicode y no solo a los caracteres imprimibles del CDC6600 de la versión histórica) por David Cattanéo en 2010-11.