Gramáticas

Vista previa del material en texto

Sintaxis y Semántica de los Lenguajes pág. 10 de Página 10 de 25 
GRAMÁTICAS 
 
Hemos definido un Lenguaje como un conjunto finito de palabras o cadenas construidas 
a partir de un alfabeto determinado. Ahora preguntémonos… 
 
¿Cómo creemos que se determinan las palabras o cadenas (o construcciones, o 
sentencias, u oraciones) que pertenecen a un lenguaje? 
Podemos hacerlo por extensión enumerando una a una las cadenas miembros (tal 
como lo hemos hecho hasta ahora en nuestros ejemplos previos). 
O podemos hacerlo por comprensión, es decir, estableciendo reglas que nos permitan 
producir (o generar) aquellas cadenas o palabras que son parte del lenguaje. 
 
Ejemplo: 
En español, hay una regla gramatical que establece que las palabras agudas terminadas en n, s 
o vocal van acentuadas. Esto nos permite establecer que canción pertenece al lenguaje mientras 
que canción no pertenece. 
 
Así, las Gramáticas proporcionan un conjunto de reglas que aplicadas sobre un alfabeto 
permiten generar las construcciones sintácticas válidas en un lenguaje. 
En general, el establecimiento de este conjunto de reglas, que conforman la gramática 
de un lenguaje, puede hacerse. 
 
De manera no formal o coloquial tal como lo hemos hecho en nuestro ejemplo 
anterior. Describiendo las regla coloquialmente. Por ejemplo: la que se da en los 
tutoriales de lenguajes. En este caso estamos en presencia de una GRAMÁTICA NO 
FORMAL 
 
De manera específica, usando una notación estricta y no ambigua. En lo posible, 
matemática. En este caso estamos en presencia de una GRAMÁTICA FORMAL. 
 
Sintaxis y Semántica de los Lenguajes pág. 11 de Página 11 de 25 
Sobre estas últimas nos centraremos a partir de ahora, puesto que la definición formal 
de los Lenguajes de Programación se realiza en términos de gramáticas formales. 
 
 
Una gramática, constituye una herramienta para generar cadenas o palabras en un 
lenguaje, y se define formalmente por la cuaterna de elementos 
∑t: define el alfabeto de símbolos terminales de la gramática, aquellos que pueden 
aparecer en las cadenas o palabras del lenguaje descripto por la gramática. 
∑n: define el alfabeto de símbolos no terminales de la gramática, que servirán a los fines 
de aplicar las producciones o derivaciones. 
S un símbolo no terminal, particular, que constituye el punto de partida de todas las 
derivaciones o producciones que permitirán general palabras o cadenas en la gramática 
P: un conjunto de reglas de producción o derivación, en el sentido que se han definido 
anteriormente 
Ejemplo 
Dada G1: 
 t={x,y} 
 n={S,A} 
 P: 
 SxA 
 AxAy| 
Una derivación posible es S->xA->xxAy->xxxAyy->xxxyy->xxxyyy Luego la cadena xxxyyy ha 
sido generada por la gramática descripta. 
 Así, esta gramática genera todas las cadenas de la forma x, xxy, xxxyy, xxxxyyy, etc. O 
sea, todas las cadenas que tienen una x más que el número de y. 
Sintaxis y Semántica de los Lenguajes pág. 12 de Página 12 de 25 
 
Def.: Lenguaje Generado por una Gramática L(G) 
El Lenguaje Generado por una Gramática L(G), es entonces: el conjunto de todas las 
sentencias de la gramática; es decir, todas las palabras o cadenas que se pueden 
obtener a partir de axioma de la gramática por la aplicación de derivaciones. 
L(G)={x/S*x, x  *t} 
 
Ejemplo: 
(en relación al ejemplo anterior) 
L(G1)={xn+1yn / n>=0} 
 
Def. Equivalencia de Gramáticas 
Dos gramáticas G1 y G2 son equivalentes si L(G1)=L(G2). Es decir si generan el mismo 
lenguaje. 
 
Ejemplo: 
(manteniendo relación con el ejemplo anterior) 
Sea G2: 
t={x,y} 
 n={S,A} 
 P: 
 Sx|A 
 AxSy 
 Tenemos que G1 es equivalente a G2, puesto que ambas generan el mismo lenguaje. 
De esto debemos rescatar como muy importante… 
 
Importante: Un mismo lenguaje puede ser generado por múltiples gramáticas. 
 
 
Sintaxis y Semántica de los Lenguajes pág. 13 de Página 13 de 25 
Clasificación de gramáticas según la Jerarquía de Chomsky 
El lingüista Noam Chomsky, definió cuatro tipos de gramáticas formales, las cuáles se 
diferencian entre sí por el tipo de restricciones impuestas a sus reglas de producción. 
Esta clasificación describe las gramáticas desde los tipos más generales a los más 
específicos, dependiendo de la forma de las reglas de la gramática. La clasificación de 
Chomsky permite introducir, al mismo tiempo, una clasificación de tipos de lenguajes 
que cada uno de estos tipos de gramática generan y finalmente, como veremos más 
adelante con detenimiento, en los autómatas que reconocen los lenguajes generados 
por dichas gramáticas (los autómatas son máquinas reconocedoras de lenguajes que 
estudiaremos luego). 
 
 
 
Tipo 0 – Irrestrictas: En la parte izquierda de cada producción, tiene que haber al 
menos un símbolo no Terminal. Respecto de las partes derechas no hay ningún tipo 
de restricción. 
Ejemplo: 
S0A 
0AB1 
B 
 
Tipo 1 – Dependientes del Contexto o Sensibles al Contexto: La parte izquierda 
debe tener un símbolo no terminal, que puede estar acompañado por un contexto de 
símbolos terminales y no terminales. Si este contexto aparece, debe estar presente 
también en la parte derecha. Sólo se admite como regla compresora la regla S-> 
 
Sintaxis y Semántica de los Lenguajes pág. 14 de Página 14 de 25 
Recuerda: Se denomina regla compresora aquella cuya parte derecha tiene menos 
símbolos que la parte izquierda. 
IMPORTANTE: Si se admite otra regla compresora (por ej.: la regla nula) que no sea el 
axioma se dice que la gramática no es estricta. 
Definición Alternativa 
Otra forma de definir las gramáticas sensibles al contexto, es aquella gramática formal 
con la única restricción que todas las producciones α -> β en P cumplan que |α| ≤ |β| 
donde |α| es la longitud de α. Se las llama gramáticas de longitud no decreciente. 
Se demuestra que las gramáticas sensibles al contexto, y las de longitud creciente son 
equivalentes en el sentido que generan los mismos lenguajes, a través de una doble 
contención, es decir, toda gramática sensible al contexto está contenida en las de 
longitud creciente y viceversa. 
 
Ejemplo: 
S → abc | aSBc 
cB → Bc 
bB → bb 
Esta gramática genera este lenguaje: , que es dependiente 
del contexto. 
 
 
 
Sintaxis y Semántica de los Lenguajes pág. 15 de Página 15 de 25 
Tipo 2 – Independientes del Contexto o de Libre Contexto: En estas gramáticas, la 
parte izquierda de las producciones sólo puede tener un símbolo no Terminal. 
 
Ejemplos: 
S → aSb | ε 
Esta gramática genera el lenguaje no regular . 
 
S → x | y | z | S + S | S - S | S * S | S/S | (S) 
Gramática libre de contexto para expresiones enteras algebraicas sintácticamente correctas 
sobre las variables x, y y z. Generaría, por ejemplo, la cadena ( x + y ) * x - z * y / ( x + x ) 
 
S → aSc | B 
B → bBc | ε 
la cual genera el Lenguaje 
Se debe observar que estas gramáticas se denominan de contexto libre porque a la 
hora de transformar una palabra en otra, el símbolo no terminal que se transforma no 
depende de los que estén a la izquierda o derecha de él. 
Se dice que una G2 (gramática de libre contexto) es Estricta, si cumple estrictamente 
con la restricción de que la única regla compresora sea el axioma S->. Si no cumple 
esta condición, se dice que la G2 es No Estricta. 
 
Sintaxis y Semántica de los Lenguajes pág. 16 de Página 16 de 25 
La siguiente filmina ilustra presenta ejemplos de G2 (libres o independientes del 
contexto). Se debe tener en cuenta al resolver estos caso, que la especificación dada 
debe cumplirse. Así, por ejemplo, si nos indican que la gramática debe tener dos 
símbolos no terminales, no podemos resolverlo con sólo un símbolo. 
 
Tipo 3 – Regulares, Normales o Lineales: Estas gramáticas, las más restrictivas 
pueden ser de dos tipos: 
Regulares por derecha: <No Terminal>:= <Terminal>|<Terminal><No Terminal>| 
Regulares por izquierda: <No Terminal>:=<Terminal>|<NoTerminal><Terminal>| 
 
Sintaxis y Semántica de los Lenguajes pág. 17 de Página 17 de 25 
Ejemplo 
(Normal o Regular por Derecha) 
S → aS 
S → bA 
A → cA 
A → ε 
Esta gramática describe el lenguaje L(G1)={anbcm / n>=0 y m>=0} 
Ejemplo 
(Normal o Regular por Izquierda) 
SB0 
BS1 
S 
Esta gramática genera el lenguaje L(G2)={(10)n / n>=0} 
Observar que para cada gramática regular izquierda, existe una gramática regular 
derecha equivalente y viceversa. 
 
El problema de las gramáticas regulares recursivas a izquierda 
Tal como hemos visto en algunos ejemplos para las reglas de producción, la categoría 
sintáctica que define la regla (es decir el no terminal de la izquierda) puede usarse en 
la parte derecha de la regla para especificar repetición. Esta clase de regla o producción 
se conoce como Regla Recursiva. 
Cuando el primer símbolo del lado derecho de una producción es el mismo que el del 
lado izquierdo, se dice que la regla es Recursiva a Izquierda inmediata. 
 
Sintaxis y Semántica de los Lenguajes pág. 18 de Página 18 de 25 
Las gramáticas que tienen reglas recursivas a izquierda, presentan problemas para 
algunos tipos de analizadores (tema que veremos más adelante), por lo que se debe 
intentar eliminar este tipo de recursividad. La filmina anterior propone un mecanismo 
para convertir una gramática recursiva a izquierda inmediata, en otra recursiva a 
derecha equivalente. Veamos en la siguiente filmina un ejemplo de su aplicación. 
 
Observar en esta filmina, que la recursión a izquierda puede también ser indirecta. En 
este caso, el primer reemplazo evidencia que hay recursión a izquierda, aunque de un 
modo indirecto, lo cual es un poco más difícil de identificar que en el caso de la RI 
directa. Al hacer la sustitución del punto 1. Se transforma esa recursión indirecta en 
directa. Luego el proceso sigue tal como lo describió la primer filmina para eliminar la RI 
directa. 
Importante: Al aplicar este procedimiento para eliminar la RI en una gramática, se debe 
verificar que la gramática recursiva a derecha obtenida sea equivalente. Es decir, que 
ambas gramáticas generen el mismo lenguaje. 
 
En síntesis: como mencionamos anteriormente, cada uno de los tipos de gramática 
según Chomsky, es más restrictivo en cuanto a la forma de las producciones que el 
anterior, el cual las incluye. 
 
Sintaxis y Semántica de los Lenguajes pág. 19 de Página 19 de 25 
 
Las gramáticas Irrestrictas sólo se usan de manera teórica y no son aplicables a los 
lenguajes de programación. Las gramáticas sensibles al contexto tampoco tienen 
aplicación práctica en las ciencias de la Computación. Sólo las gramáticas 
independientes del contexto y las regulares o normales son útiles en la tecnología de 
compiladores. 
Más adelante veremos la correspondencia entre tipos de gramáticas y tipos de lenguajes 
que las mismas generan. Así como también las máquinas o autómatas que se usan para 
reconocer las cadenas válidas en cada uno de esos lenguajes. 
 
Sintaxis y Semántica de los Lenguajes pág. 20 de Página 20 de 25 
Notaciones y Expresiones 
 
Veamos ahora las notaciones que la teoría de lenguajes provee para especificar 
gramáticas independientes del contexto y gramáticas normales o regulares. 
 
Notación BNF (Backus Naur Form) 
La notación BNF (Backus Naur Form) incorpora los mismos elementos que hemos 
utilizado hasta ahora para escribir producciones. 
 
Esta forma rotacional propone representar: 
<no terminal>: los no terminales se encierran entre signos < y > 
::= las reglas de producción se leen como “se define como” 
| significa “o” 
 
Ejemplos: 
En el caso más sencillo podemos enumerar los elementos de un lenguaje finito por extensión a 
partir de una regla gramatical. 
 
 
 
 
 
<digito>::= 0|1|2|3|4|5|6|7|8|9 
Axioma Categoría 
Sintáctica 
Sintaxis y Semántica de los Lenguajes pág. 21 de Página 21 de 25 
Una vez que se ha definido un conjunto básico de categorías sintácticas se pueden usar para 
construir estructuras más complejas. 
 
 
Este ejemplo define la estructura de las sentencias while en C/C++, en donde suponemos ya 
definida la categoría sintáctica <enunciado> 
Tal como hemos visto anteriormente para las reglas de producción, la categoría sintáctica que 
define la regla (es decir la producción) puede usarse ella misma en esa regla para especificar 
repetición. Esta clase de regla o producción se conoce como Regla Recursiva 
 
 
 
Así, para la cadena de entrada abcd, si graficamos las derivaciones directas como ramas de un 
árbol tendríamos… 
 
 
 
 
 
 
 
 
 
 
 
 La notación BNF se definió en la década del `60 (1962) para la definición 
sintáctica de ALGOL. 
 Una gramática BNF completa es tan solo un conjunto de esta clase de reglas 
gramaticales, las cuales definen en conjunto una jerarquía que conduce a la categoría 
sintáctica de máximo nivel; es decir al axioma de la gramática. En un lenguaje de 
programación, la categoría sintáctica de máximo nivel es <programa> 
 Al mismo tiempo que se definía la forma de Backus Naur, el lingüista Noam 
Chomsky desarrollaba las “gramáticas de libre contexto” para la definición de la 
sintaxis de lenguajes naturales. Si nos fijamos en su definición, tanto las gramáticas 
BNF como las gramáticas de libre contexto (tipo 2) son equivalentes en cuanto a su 
poder descriptivo (es decir ambas pueden describir la misma categoría o tipología de 
lenguajes); su única diferencia radica en la forma rotacional. Por esta razón, a los 
efectos de nuestro estudio, las trataremos como sinónimos. 
<enunciado-iterativo> ::= while { <enunciado> } 
<cadena>::=<letra>|<cadena><letra> 
<letra>::=a|b|c… 
 
Sintaxis y Semántica de los Lenguajes pág. 22 de Página 22 de 25 
Notación EBNF (BNF Extendida) 
 La EBNF es una notación que define algunas extensiones o agregados sobre 
las gramáticas BNF. Estas extensiones no implican modificación sobre los alcances o 
restricciones de una gramática BNF; pero facilitan la escritura de reglas sintácticas 
complejas. 
Las extensiones son: 
[…] Lo que está entre corchetes es un elemento optativo. 
{…}+ Los elementos que están entre llaves con + se pueden repetir 1 o más veces. 
{…}* {} Los elementos que están entre llaves con/sin estrella se repiten 0 o más veces. 
Ejemplo: 
 BNF EBNF 
<cadena>::=<letra>|<cadena><letra> 
<letra>::=a|b|c… 
<cadena>::={<letra>}* 
<letra>:=a|b|c… 
<entero>::=+<numero>|-<numero>|<numero> 
<numero>::=<digito><numero>|<digito> 
<entero>::=[+|-]{<digito>}* 
 
Diagrama de sintaxis , diagramas sintácticos o diagramas de ferrocarril 
Un diagrama sintáctico, o diagrama de ferrocarril es una forma gráfica de expresar 
reglas EBNF (BNF Extendida). 
 
Cada regla se representa por un camino que va de izquierda (entrada) a derecha 
(salida). Los círculos en ese camino representan elementos terminales y los recuadros 
representan nodos no terminales. 
Sintaxis y Semántica de los Lenguajes pág. 23 de Página 23 de 25 
Cualquier trayecto válido de la entrada a la salida representa una cadena válida para 
esa regla. 
 
 
 
 
BNF, EBNF y diagramas sintácticos son herramientas que permiten describir gramáticas 
del tipo G2 (y por contención también G3). 
 
Otros ejemplos: 
 
EBNF <var>::= [<letra>|’-‘]{<letra>|<digito>{‘-’}} 
 
 
EBNF <expresion>::= <termino>{(+|-)<termino>} 
Símbolos terminales 
Símbolos no terminales 
Sintaxis y Semántica de los Lenguajes pág. 24 de Página 24 de 25 
 
EBNF <exp_condicional>::= ‘if’ <exp_booleana>’then’<enunciado> [‘else’<enunciado>] 
 
 
Este tipo de diagramas se popularizó en la década del ’70 con Pascal. 
 
Notación en expresiones 
La estructura sintáctica de las expresiones (algebraicas, lógicas, etc.), se ajusta, 
dependiendo del lenguaje, a una de las siguientes tres formas. 
 
Notación infija 
La sintaxis establece que el operador va entre los dos operandos. El problema con esto 
es quesiempre tengo que avanzar hacia delante en el recorrido de la expresión para 
saber si puedo ir resolviendo partes o no (por la prioridad de los operadores). 
 
Sintaxis y Semántica de los Lenguajes pág. 25 de Página 25 de 25 
 
 
Notación postfija o polaca inversa 
Aquí la sintaxis establece que el operador va a la derecha de los operandos. Esta otra 
alternativa es deseable para los lenguajes interpretados porque el recorrido o su 
evaluación resulta más directo. Aquí nunca aparecen paréntesis. 
 
Notación prefija o funcional 
En este caso la regla sintáctica establece que el operador va a la izquierda de los 
operandos. 
 
En unos lenguajes se adoptará una de las alternativas y en otros otra. Pero una vez que 
se define cuál es la notación que se utilizará, las expresiones en ese lenguaje deberán 
respetarla. De lo contrario, habrá un “Error de Sintaxis”. 
La sintaxis que se establezca, guiará al traductor o compilador en la generación de las 
operaciones correctas para evaluar la expresión.