Símbolos terminales y no terminales

Categorías de símbolos en gramáticas formales

En los lenguajes formales , 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 como parte de 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 están en dos conjuntos completamente separados .

Símbolos de terminales

Los símbolos terminales son símbolos que pueden aparecer en los resultados de las reglas de producción de una gramática formal y que no se pueden modificar mediante las reglas de la gramática. La aplicación recursiva de las reglas a una cadena de origen de símbolos normalmente terminará en una cadena de salida final que consta únicamente de símbolos terminales.

Considere una gramática definida por dos reglas. En esta gramática, el símbolo Бes un símbolo terminal y Ψes a la vez un símbolo no terminal y el símbolo inicial. Las reglas de producción para crear cadenas son las siguientes:

El símbolo Ψpuede convertirse enБΨ
El símbolo Ψpuede convertirse enБ

Aquí Бhay un símbolo terminal porque no existe ninguna regla que lo cambie por 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 consisten únicamente en símbolos terminales . El diagrama 1 ilustra una cadena que se puede producir con esta gramática.

Símbolos no terminales

Los símbolos no terminales son aquellos símbolos que pueden reemplazarse. También pueden llamarse simplemente variables sintácticas . Una gramática formal incluye un símbolo de inicio , un miembro designado del conjunto de no terminales del que pueden derivarse 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 de esa manera.

Las gramáticas libres de contexto son aquellas gramáticas en las que el lado izquierdo de cada regla de producción consiste en un solo símbolo no terminal. Esta restricción no es trivial; no todos los lenguajes pueden generarse mediante gramáticas libres de contexto. Aquellos que pueden hacerlo se denominan lenguajes libres de contexto. Estos son exactamente los lenguajes que pueden ser reconocidos por un autómata de inserción 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 .

Normas 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 se pueden usar para generar cadenas o para analizarlas. Cada una de estas reglas tiene una cabecera , o lado izquierdo, que consiste en la cadena que se puede reemplazar, y un cuerpo , o lado derecho, que consiste en una cadena que puede reemplazarla. Las reglas se escriben a menudo en la forma cabecera → cuerpo ; 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, ^[2]^[3] una gramática G consta de los siguientes componentes:

Un conjunto finito $N$ de símbolos no terminales .
Un conjunto finito $Σ$ de símbolos terminales que es disjunto de $N$ .
Un conjunto finito $P$ de reglas de producción , cada regla de la forma

(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}

donde es el operador de estrella de Kleene y

\cup

denota unión de conjuntos , por lo que representa cero o más símbolos, y

N

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 ^{[nota 1]} , se puede denotar con una notación especial (a menudo

Λ

,

e

o

ε

) para evitar confusiones.

{\estilo de visualización {}^{*}}

(\Sigma \cup N)^{*}

Un símbolo distinguido que es el símbolo de inicio . $S\en N$

Una gramática se define formalmente como la cuádruple ordenada . A este tipo de gramática formal se la suele denominar en la literatura sistema de reescritura o gramática de estructura de frase . ^[4]^[5] $\langle N,\Sigma ,P,S\rangle$

Ejemplo

La forma Backus-Naur es una notación para expresar ciertas gramáticas. Por ejemplo, las siguientes reglas de producción en la forma Backus-Naur se utilizan para representar un número entero (que puede tener signo):

< 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 <digit>y <integer>son símbolos no terminales. ^{[nota 2]}

Otro ejemplo es:

{\ce {S -> cAd}}

{\ce {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.

Véase también

Notas

^ No contiene ningún símbolo.
^ Este ejemplo admite cadenas con ceros iniciales como "0056" o "0000", así como cadenas con ceros negativos como "-0" y "-00000".

Referencias

^ Rosen, KH (2012). Matemática discreta y sus aplicaciones. McGraw-Hill. páginas 847-851.
^ Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje". IRE Transactions on Information Theory . 2 (3): 113–123. doi :10.1109/TIT.1956.1056813. S2CID 19519474.
^ Chomsky, Noam (1957). Estructuras sintácticas . La Haya: Mouton .
^ Ginsburg, Seymour (1975). Propiedades teóricas algebraicas y de autómatas de los lenguajes formales . Holanda Septentrional. pp. 8-9. ISBN 0-7204-2506-9.
^ Harrison, Michael A. (1978). Introducción a la teoría formal del lenguaje . Reading, Mass.: Addison-Wesley Publishing Company. pp. 13. ISBN 0-201-02955-3.

[4] No contiene ningún símbolo.

[7] Este ejemplo admite cadenas con ceros iniciales como "0056" o "0000", así como cadenas con ceros negativos como "-0" y "-00000".

[1] Rosen, KH (2012). Matemática discreta y sus aplicaciones. McGraw-Hill. páginas 847-851.

[Chomsky1956-2] Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje". IRE Transactions on Information Theory . 2 (3): 113–123. doi :10.1109/TIT.1956.1056813. S2CID 19519474.

[Chomsky1957-3] Chomsky, Noam (1957). Estructuras sintácticas . La Haya: Mouton .

[5] Ginsburg, Seymour (1975). Propiedades teóricas algebraicas y de autómatas de los lenguajes formales . Holanda Septentrional. pp. 8-9. ISBN 0-7204-2506-9.

[6] Harrison, Michael A. (1978). Introducción a la teoría formal del lenguaje . Reading, Mass.: Addison-Wesley Publishing Company. pp. 13. ISBN 0-201-02955-3.