Gramática determinista libre de contexto - Deterministic context-free grammar

En la teoría de la gramática formal , las gramáticas libres de contexto deterministas ( 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 los autómatas pushdown deterministas y generan los lenguajes libres de contexto deterministas . Los DCFG siempre son inequívocos y son una subclase importante de los CFG inequívocos; sin embargo, existen CFG no deterministas e inequívocos.

DCFGs son de gran interés práctico, ya que se pueden analizar en el tiempo lineal y, de hecho, un programa de análisis pueden ser generados automáticamente de la gramática por un generador de analizadores sintácticos . Por tanto, se utilizan ampliamente en todas las ciencias de la computación. Varias formas restringidas de DCFG se pueden analizar mediante analizadores más simples y que consumen menos recursos y, por lo tanto, se utilizan a menudo. Estas clases de gramática se denominan por el tipo de analizador que las analiza, y ejemplos importantes son LALR, SLR y LL.

Historia

En la década de 1960, la investigación teórica en ciencias de la computación sobre expresiones regulares y autómatas finitos llevó al descubrimiento de que las gramáticas libres de contexto son equivalentes a los autómatas pushdown no deterministas . Se pensaba que estas gramáticas capturaban la sintaxis de los lenguajes de programación de computadoras. Los primeros lenguajes de programación de computadoras 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 fueron particularmente útiles porque podían ser analizadas secuencialmente por un autómata de empuje determinista , que era un requisito debido a las limitaciones de la memoria de la computadora. En 1965, Donald Knuth inventó el analizador sintáctico LR (k) y demostró que existe una gramática LR (k) para cada lenguaje determinista libre de contexto. Este analizador todavía requería mucha memoria. En 1969, Frank DeRemer inventó los analizadores sintácticos 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 idiomas. El analizador LALR fue la alternativa más sólida. 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 pueden implementarse analizadores sintácticos LR canónicos con requisitos de tabla reducidos drásticamente en comparación con el algoritmo de construcción de tablas de Knuth.

Ver también

Referencias

  1. ^ Chomsky, Noam (1962). "Gramáticas libres de contexto y almacenamiento pushdown". Informe de progreso trimestral, Laboratorio de Investigación en Electrónica del MIT . 65 : 187-194.
  2. ^ Evey, RJ (1963). "Aplicación de Máquinas Pushdown-Store". 1963 Actas de la AFIPS de la Conferencia Conjunta de Computación de Otoño : 215-227.
  3. ^ Schützenberger, Marcel Paul (1963). "Sobre lenguajes libres de contexto y autómatas pushdown" . Información y control . 6 : 246-264. doi : 10.1016 / s0019-9958 (63) 90306-1 .
  4. ^ A Salomaa; D Madera; S Yu, eds. (2001). Medio siglo de teoría de los autómatas . Publicaciones científicas mundiales. págs. 38–39.
  5. ^ Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
  6. ^ Franklin L. DeRemer (1969). "Traductores prácticos para idiomas LR (k)" (PDF) . MIT, Tesis Doctoral. Archivado desde el original (PDF) el 5 de abril de 2012.
  7. ^ X. Chen, Midiendo y extendiendo LR (1) análisis , tesis doctoral de la Universidad de Hawaii, 2009.