Símbolos terminales y no terminales

En las lenguas 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 según las reglas de producción.

Las terminales y no terminales de una gramática particular se encuentran 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 cambiar utilizando las reglas de la gramática. La aplicación de las reglas de forma recursiva a una cadena fuente de símbolos normalmente terminará en una cadena de salida final que consta únicamente de símbolos terminales.

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

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

Aquí Бhay un símbolo terminal porque no existe ninguna regla que lo cambie en 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 constan únicamente de 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 se pueden reemplazar. También pueden denominarse simplemente variables sintácticas . Una gramática formal incluye un símbolo inicial , un miembro designado del conjunto de no terminales 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 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 consta de un solo símbolo no terminal. Esta restricción no es trivial; No todos los idiomas pueden generarse mediante gramáticas libres de contexto. Los que pueden hacerlo se denominan 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 .

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 se pueden utilizar para generar cadenas o analizarlas. Cada una de estas reglas tiene una cabeza , o lado izquierdo, que consta de la cuerda que puede ser reemplazada, y un cuerpo , o lado derecho, que consiste en una cuerda que puede reemplazarla. Las reglas suelen escribirse en la forma cabeza → cuerpo ; por ejemplo, la regla a → b especifica que a puede ser reemplazado por b .

En la formalización clásica de las 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 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 esté formado únicamente por una cadena vacía ^{[nota 1]} , se puede denotar con una notación especial (a menudo

Λ

e

ε

) para evitar confusiones.

{}^{*}

(\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 . Esta gramática formal a menudo se denomina sistema de reescritura o gramática de estructura de frase en la literatura. ^[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 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>son <integer>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.

Ver también

Notas

^ No contiene ningún símbolo.
^ Este ejemplo admite cadenas con ceros a la izquierda 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". Transacciones IRE sobre teoría de la información . 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 del Norte. págs. 8–9. ISBN 0-7204-2506-9.
^ Harrison, Michael A. (1978). Introducción a la teoría del lenguaje formal . Reading, Massachusetts: Addison-Wesley Publishing Company. págs.13. ISBN 0-201-02955-3.