En informática , los símbolos terminales y no terminales son los elementos léxicos utilizados para especificar las reglas de producción que constituyen una gramática formal . Los símbolos terminales son los símbolos elementales del lenguaje definidos por una gramática formal. Los símbolos no terminales (o variables sintácticas ) se reemplazan por grupos de símbolos terminales de acuerdo con las reglas de producción.
Los símbolos terminales son símbolos literales que pueden aparecer en las salidas de las reglas de producción de una gramática formal y que no se pueden cambiar usando las reglas de la gramática. La aplicación de las reglas de forma recursiva a una cadena de símbolos de origen generalmente terminará en una cadena de salida final que constará solo de símbolos terminales.
Aquí дhay un símbolo de terminal porque no existe una regla que lo cambie a otra cosa. Por otro lado, רtiene dos reglas que pueden cambiarlo, por lo que es no terminal. Un lenguaje formal definido o generado por una gramática particular es el conjunto de cadenas que puede producir la gramática y que consisten únicamente en símbolos terminales .
Los símbolos no terminales son aquellos símbolos que se pueden reemplazar. También pueden denominarse simplemente variables sintácticas . Una gramática formal incluye un símbolo de inicio , un miembro designado del conjunto de no terminales a partir del cual se pueden derivar todas las cadenas del lenguaje mediante aplicaciones sucesivas de las reglas de producción. De hecho, el lenguaje definido por una gramática es precisamente el conjunto de cadenas terminales que pueden derivarse así.
Las gramáticas independientes del contexto son aquellas gramáticas en las que el lado izquierdo de cada regla de producción consta de un solo símbolo no terminal. Esta restricción no es trivial; no todos los lenguajes pueden ser generados por gramáticas libres de contexto. Los que pueden se llaman lenguajes libres de contexto. Estos son exactamente los lenguajes que pueden ser reconocidos por un autómata push down no determinista . Los lenguajes libres de contexto son la base teórica de la sintaxis de la mayoría de los lenguajes de programación .
Una gramática se define mediante reglas de producción (o simplemente 'producciones') que especifican qué símbolos pueden reemplazar a qué otros símbolos; estas reglas se pueden usar para generar cadenas o para analizarlas. Cada una de estas reglas tiene un encabezado , o lado izquierdo, que consiste en la cadena que puede reemplazarse, y un cuerpo , o lado derecho, que consiste en una cadena que puede reemplazarla. Las reglas a menudo se escriben en la forma cabeza → cuerpo ; por ejemplo, la regla a → b especifica que a puede ser reemplazada por b .