En la teoría de la gramática formal , las gramáticas deterministas libres de contexto ( DCFG ) son un subconjunto adecuado de las gramáticas libres de contexto . Son el subconjunto de gramáticas libres de contexto que pueden derivarse de autómatas pushdown deterministas y generan lenguajes deterministas libres de contexto . Los DCFG son siempre inequívocos y son una subclase importante de CFG inequívocos; Sin embargo, existen CFG inequívocos y no deterministas.
Los DCFG son de gran interés práctico, ya que se pueden analizar en tiempo lineal y, de hecho, un generador de analizadores puede generar automáticamente un analizador a partir de la gramática . Por tanto, se utilizan ampliamente en toda la informática. Varias formas restringidas de DCFG pueden analizarse mediante analizadores más simples y que requieren menos recursos y, por lo tanto, se utilizan con frecuencia. Se hace referencia a estas clases de gramática por el tipo de analizador que las analiza, y ejemplos importantes son LALR , SLR y LL .
En la década de 1960, la investigación teórica en informática sobre expresiones regulares y autómatas finitos condujo al descubrimiento de que las gramáticas libres de contexto son equivalentes a autómatas pushdown no deterministas . [1] [2] [3] Se pensaba que estas gramáticas capturaban la sintaxis de los lenguajes de programación de computadoras. Los primeros lenguajes de programación informática de alto nivel estaban en desarrollo en ese momento (ver Historia de los lenguajes de programación ) y escribir compiladores era difícil. Pero el uso de gramáticas libres de contexto para ayudar a automatizar la parte de análisis del compilador simplificó la tarea. Las gramáticas deterministas libres de contexto eran particularmente útiles porque podían ser analizadas secuencialmente por un autómata pushdown determinista , lo cual era un requisito debido a limitaciones de memoria de la computadora. [4] En 1965, Donald Knuth inventó el analizador LR(k) y demostró que existe una gramática LR(k) para cada lenguaje determinista libre de contexto. [5] Este analizador todavía requería mucha memoria. En 1969, Frank DeRemer inventó los analizadores LALR y Simple LR , ambos basados en el analizador LR y con requisitos de memoria muy reducidos a costa de una menor capacidad de reconocimiento de lenguaje. El analizador LALR fue la alternativa más fuerte. [6] Desde entonces, estos dos analizadores se han utilizado ampliamente en compiladores de muchos lenguajes informáticos. Investigaciones recientes han identificado métodos mediante los cuales se pueden implementar analizadores LR canónicos con requisitos de tabla drásticamente reducidos en comparación con el algoritmo de creación de tablas de Knuth. [7]