Gramática libre de contexto

En la teoría del lenguaje formal , una gramática libre de contexto ( CFG ) es una gramática formal cuyas reglas de producción son de la forma

con un solo símbolo no terminal y una cadena de terminales y / o no terminales ( puede estar vacío). Una gramática formal está "libre de contexto" si sus reglas de producción se pueden aplicar independientemente del contexto de un no terminal. Independientemente de los símbolos que lo rodeen, el no terminal único en el lado izquierdo siempre se puede reemplazar por el lado derecho. Esto es lo que lo distingue de una gramática sensible al contexto .${\ Displaystyle A}$ ${\ Displaystyle \ alpha}$${\ Displaystyle \ alpha}$

Una gramática formal es esencialmente un conjunto de reglas de producción que describen todas las cadenas posibles en un lenguaje formal dado. Las reglas de producción son reemplazos simples. Por ejemplo, la primera regla de la imagen,

reemplaza con . Puede haber varias reglas de reemplazo para un símbolo no terminal dado. El lenguaje generado por una gramática es el conjunto de todas las cadenas de símbolos terminales que pueden derivarse, mediante aplicaciones repetidas de reglas, de algún símbolo no terminal particular ("símbolo de inicio"). Los símbolos no terminales se utilizan durante el proceso de derivación, pero no aparecen en su cadena de resultado final. ${\ Displaystyle \ langle {\ text {Stmt}} \ rangle}$${\ Displaystyle \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}$

Los lenguajes generados por gramáticas libres de contexto se conocen como lenguajes libres de contexto (CFL). Diferentes gramáticas libres de contexto pueden generar el mismo lenguaje libre de contexto. Es importante distinguir las propiedades del lenguaje (propiedades intrínsecas) de las propiedades de una gramática particular (propiedades extrínsecas). La cuestión de la igualdad del lenguaje (¿dos gramáticas libres de contexto dadas generan el mismo lenguaje?) Es indecidible .

Las gramáticas libres de contexto surgen en lingüística donde se utilizan para describir la estructura de oraciones y palabras en un lenguaje natural , y de hecho fueron inventadas por el lingüista Noam Chomsky para este propósito. Por el contrario, en informática , a medida que aumentaba el uso de conceptos definidos de forma recursiva, se utilizaban cada vez más. En una aplicación temprana, las gramáticas se utilizan para describir la estructura de los lenguajes de programación . En una aplicación más nueva, se utilizan en una parte esencial del Lenguaje de marcado extensible (XML) llamado Definición de tipo de documento . ^[2]

Extracto simplificado de la gramática formal ^[1] para el lenguaje de programación C (izquierda) y una derivación de un fragmento de código C (derecha) del símbolo no terminal . Los símbolos no terminales y terminales se muestran en azul y rojo, respectivamente.${\ Displaystyle \ langle {\ text {Stmt}} \ rangle}$