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 terminales y no terminales de una gramática particular son dos conjuntos disjuntos .
Símbolos terminales
Los símbolos terminales son símbolos literales que pueden aparecer en los resultados 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 fuente normalmente terminará en una cadena de salida final que consta únicamente de símbolos terminales.
Considere una gramática definida por dos reglas. Usando marcas pictóricas que interactúan entre sí:
- El símbolo
ר
puede convertirseди
- El símbolo
ר
puede convertirseд
Aquí д
hay un símbolo terminal porque no existe una regla que lo cambie a otra cosa. Por otro lado, ר
tiene dos reglas que pueden cambiarlo, por lo que no es 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 consta solo de símbolos terminales .
Símbolos no 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 del que 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.
Las gramáticas libres de contexto son aquellas 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 denominan lenguajes libres de contexto. Estos son exactamente los lenguajes que pueden ser reconocidos por un autómata de empuje hacia abajo 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 .
Reglas de producció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 pueden usarse para generar cadenas o para analizarlas. Cada una de estas reglas tiene una cabeza , o lado izquierdo, que consiste en la cuerda que puede ser reemplazada, y un cuerpo , o lado derecho, que consiste en una cuerda que puede reemplazarla. Las reglas a menudo se escriben en la forma head → body ; por ejemplo, la regla a → b especifica que a se puede reemplazar por b .
En la formalización clásica de gramáticas generativas propuesta por primera vez por Noam Chomsky en la década de 1950, [1] [2] una gramática G consta de los siguientes componentes:
- Un conjunto finito de símbolos no terminales .
- Un conjunto finito de símbolos terminales que es disjunto de.
- Un conjunto finito de reglas de producción , cada regla de la forma
- dónde es el operador estrella de Kleene y denota unión de conjuntos , entonces representa cero o más símbolos, y significa un símbolo no terminal . Es decir, cada regla de producción se asigna de una cadena de símbolos a otra, donde la primera cadena contiene al menos un símbolo no terminal. En el caso de que el cuerpo consista únicamente en la cadena vacía , es decir, que no contenga ningún símbolo, se puede denotar con una notación especial (a menudo , o ) para evitar confusiones.
- Un símbolo distinguido ese es el símbolo de inicio .
Una gramática se define formalmente como el cuádruple ordenado . Esta gramática formal a menudo se denomina sistema de reescritura o gramática de estructura de frases en la literatura. [3] [4]
Ejemplo
Por ejemplo, lo siguiente representa un número entero (que puede estar firmado) expresado en una variante de la forma Backus – Naur :
< dígito > :: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' < entero > :: = ['-'] < dígito > { < dígito > }
En este ejemplo, los símbolos (-, 0,1,2,3,4,5,6,7,8,9) son símbolos terminales y
Nota: Este ejemplo admite cadenas con ceros iniciales como "0056" o "0000", así como cadenas de ceros negativos como "-0" y "-00000".
Otro ejemplo es:
S -> cAd
A -> a | ab
En este ejemplo, los símbolos a, b, c, d son símbolos terminales y S, A son símbolos no terminales.
Ver también
Referencias
- ^ Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje". Transacciones IRE sobre teoría de la información . 2 (3): 113–123. doi : 10.1109 / TIT.1956.1056813 .
- ^ Chomsky, Noam (1957). Estructuras sintácticas . La Haya: Mouton .
- ^ Ginsburg, Seymour (1975). Propiedades teóricas algebraicas y autómatas de los lenguajes formales . Holanda Septentrional. págs. 8–9. ISBN 0-7204-2506-9.
- ^ Harrison, Michael A. (1978). Introducción a la teoría del lenguaje formal . Reading, Mass .: Addison-Wesley Publishing Company. pp. 13 . ISBN 0-201-02955-3.