Alfabetos y lenguajes (1)

Vista previa del material en texto

Sintaxis y Semántica de los Lenguajes pág. 1 de Página 1 de 25 
FILMINAS COMENTADAS 
SINTÁXIS Y SEMÁNTICA DE LENGUAJES 
 
INTRODUCCIÓN 
 
El presente documento, toma como hilo conductor las filminas de clase e incluye notas 
y ejemplos que pretenden explicar sintéticamente los principales contenidos de la 
asignatura. Es una guía, que debe ser ampliada luego con la lectura bibliográfica, el 
material digital complementario propuesto, la resolución de trabajos prácticos y la 
indagación personal y autónoma por parte de los alumnos. 
 
GRAMÁTICAS Y RECONOCIMIENTO DE LENGUAJES 
 
 
En principio (y simplificando muchos aspectos), un programa es una secuencia de 
instrucciones o sentencias que la máquina tiene que ejecutar en un cierto orden y que 
están escritas en algún lenguaje. En particular, en Algoritmos, aprendieron a escribir 
programas simples en pseudocódigo (que es una forma de lenguaje de programación 
muy cercana a nuestro lenguaje natural). 
Cualquier tipo de lenguaje, sea un lenguaje natural o de programación está compuesto 
por un alfabeto (un conjunto de símbolos válidos), un conjunto de palabras válidas para 
el lenguaje y un conjunto de reglas sintácticas y semánticas que definen las 
construcciones válidas y su significado. 
 
Sintaxis y Semántica de los Lenguajes pág. 2 de Página 2 de 25 
Ejemplo: 
X  P +Z; (Esta estructura es sintácticamente válida en pseudocódigo y su semántica indica 
que se deben sumar los valores alojados en las variables P y Z y asignárselo a X). 
X Y + Z; (Esta estructura NO es sintácticamente válida en pseudocódigo. Observar que no es 
un problema léxico dado que las palabras son correctas y pertenecen al lenguaje, sino 
sintáctico dado que la estructura de la frase no es correcta en ese lenguaje). 
 
 
Esta estructura es sintácticamente válida en el lenguaje castellano, pero 
semánticamente ambigua, ya que su significado no es único. 
Este problema de la ambigüedad sintáctica o semántica cobra especial importancia en 
los lenguajes de programación; ya que ellos deben ser traducidos por un traductor (que 
es un programa informático - limitado) desde el lenguaje de alto nivel (que es el 
lenguaje de programación, más cercano a nuestro lenguaje natural) hasta el lenguaje 
de máquina (secuencia de 0 y 1 que la máquina entiende). 
 
 
Más adelante dedicaremos tiempo a estudiar el problema de la traducción (la teoría de 
compiladores e intérpretes) y cómo este problema se ha vuelto más complejo de 
acuerdo a la evolución de los lenguajes en el tiempo; desde los lenguajes de máquina 
o ensambladores hasta los lenguajes de alto nivel de nuestros días. Ahora, lo que nos 
interesa dejar claro es que para un lenguaje de programación, no es deseable la 
ambigüedad y otra serie de características flexibles que a veces encontramos en los 
Sintaxis y Semántica de los Lenguajes pág. 3 de Página 3 de 25 
lenguajes naturales y que para ello deben ser especificados en términos formales, cuasi-
matemáticos. 
 
Especificar un lenguaje implica definir su léxico (reglas de buena formación de palabras 
o cadenas válidas en el lenguaje), su estructura sintáctica (reglas de buena formación 
de frases, sentencias, estructuras y bloques de construcción válidos en el lenguaje) y 
su semántica (reglas que asignan significado a las construcciones sintácticas del 
lenguaje). La semántica en términos de lenguajes de programación podría, de manera 
simplificada, entenderse como aquella información que permite al traductor del lenguaje 
reconocer que conjunto de instrucciones deben ejecutarse a bajo nivel, en respuesta a 
cada instrucción que está escrita en el programa a alto nivel. 
 
Ejemplo 
En C/C++ para la sentencia X:=7; 
Su léxico serían las palabras X, :=, 3, ; 
Su sintaxis sería <sentencia_de_asignación>=<Identificador><operador_asignacion>(<ctte_litral> 
Su semántica indicaría implementar a bajo nivel una celda de memoria, vinculada a una dirección 
que almacena el número 3 en binario complemento a dos con el bit de mayor orden de magnitud 
como bit de signo. 
 
 
Sintaxis y Semántica de los Lenguajes pág. 4 de Página 4 de 25 
Para especificar lenguajes en términos formales, se utilizan notaciones formales. A partir 
de ahora, comenzaremos a estudiar estas notaciones y a presentar conceptos generales 
sobre lenguajes y gramáticas formales. 
 
Alfabeto 
Llamamos Alfabeto  a todo conjunto no vacío finito de símbolos (letras, números, 
combinaciones de letras y/o números) 
 
Ejemplo: 
Alfabeto Español 1={a,b,c,…,A,B,C…} 
Alfabeto Números Arábigos 2={0,1,2,3,…} 
Alfabeto binario 3={0,1} 
Alfabeto 4={00,01,10,11} 
Alfabeto 5={ma,pa} (observar que este alfabeto tiene sólo 2 símbolos) 
Palabra o Cadena 
 Definimos como palabra o cadena a toda secuencia finita de símbolos de un 
alfabeto 
 
Ejemplo: 
(Siguiendo nuestro ejemplo anterior) 
x = mama x formada con símbolos de 1 
 x formada con símbolos de 5 
y = 010011 y formada con símbolos 3 
 y formada con símbolos 4 
 
Sintaxis y Semántica de los Lenguajes pág. 5 de Página 5 de 25 
Longitud de una palabra 
 La longitud |x| de una palabra x formada por símbolos de un alfabeto ; es el 
número de símbolos del alfabeto que la forman. 
 
Ejemplo: 
(Siguiendo nuestro ejemplo anterior) 
|x| para 1 es 4. 
 para 5 es 2. 
 
|y| para 3 es 6. 
 para 4 es 3. 
 
Llamamos palabra vacía ; a una palabra de longitud cero || = 0. O sea, una palabra 
que no contiene ningún símbolo. 
 
Universo de un alfabeto 
Definimos como el Universo de un alfabeto  , W() al conjunto infinito de palabras 
que se pueden formar con los símbolos del alfabeto . 
 
Importante: La palabra vacía  pertenece a todos los universos. 
 
Ejemplo: 
(Siguiendo nuestro ejemplo anterior) 
W(3)={,0,1,00,01,10,11,000,001,…} 
 
Lenguaje sobre un alfabeto 
Un lenguaje L() sobre el alfabeto ; es todo subconjunto de W (). Como el universo 
asociado al alfabeto  es infinito, hay infinitos lenguajes sobre un alfabeto. 
Ejemplo: 
(Siguiendo nuestro ejemplo anterior) 
L1(5) = {mama,papa} 
L2(5) = {mapa,mamama,papapa,…} 
 
L1(3)={00,01,10,11} 
L2(3)={000,001,010,011,100,110,…} 
Sintaxis y Semántica de los Lenguajes pág. 6 de Página 6 de 25 
Operaciones con palabras 
 Sean x e y dos palabras, definimos: 
 
Concatenación: x.y 
(o directamente xy) como la palabra formada por los 
símbolos de x, seguidos por los símbolos de y. 
Ejemplo: En 3={0,1}, dadas x=001 e y=100 
 x.y=001100 
 
Potencia xi La potencia i-ésima de la palabra x, se forma por la 
concatenación i veces de x; 
O sea: xi=x.x. ... .x (i-veces). 
Ejemplo: En 3={0,1}, dadas x=01 
 X3 = 010101 
 
Por definición: x0= 
Reflexión x-1 Si la palabra x está formada por los símbolos A1,A2,…,An 
entonces la palabra inversa x-1 se forma invirtiendo el 
orden de los símbolos en la palabra. X-1=An, An-1,…,A2,A1 
Ejemplo: En 3={0,1}, dadas x=000111 
 x-1=111000 
 
Operaciones sobre lenguajes 
 Sean L1 y L2 dos lenguajes… 
 
Unión L1  L2 Contiene todas las palabras que 
pertenezcan a cualquiera de los dos 
lenguajes. 
L1  L2={x/x L1 ó x L2 } 
Ejemplo: 
Si L1(5)={mama,papa} 
 L2(5)={mapa,mapama} 
 L1  L2={mama,papa,mapa,mapama} 
 
 
Sintaxis y Semántica de los Lenguajes pág. 7 de Página 7 de 25 
Intersección L1  L2 Contiene todas las palabras que 
pertenezcan a los dos lenguajes. 
L1  L2={x/x L1 y x L2 } 
Ejemplo: 
Si L1(5)={mama,papa} 
 L2(5)={mapa,mama} 
 L1  L2={mama} 
Resta L1 - L2 Contiene todas las palabras que 
pertenecen a L1 y no pertenecen a L2 
L1 - L2={x/x L1 y x L2 } 
Ejemplo: 
Si L1(5)={mama,papa} 
 L2(5)={mapa,mama} 
 L1 - L2={papa} 
Concatenación L1 . L2 Contiene todas las palabras que se pueden 
formar por la concatenación de palabras de 
L1 con palabras de L2 
L1 . L2={x.y/x L1 e y L2 } 
 
Ejemplo:Si L1(5)={mama,papa} 
 L2(5)={mapa,mama} 
 L1.L2={mamamapa, mamamama, papamapa, 
papamama } 
 
Potencia Li La potencia i-ésima de un lenguaje 
corresponde a la concatenación i-veces del 
lenguaje consigo mismo. 
Li= L.L. ... .L (i-veces) 
Por definición: L0 = {} 
 
Clausura Positiva 
 
 
 
 
La clausura positiva de un lenguaje se 
forma por la Unión de todas las potencias 
del lenguaje, excluyendo la potencia 0. 
 
 
Potencia i-ésima de un 
Alfabeto 
 
i; i>0 
0;  
Clausura Positiva de un Alfabeto 
+ = W() -  
Sintaxis y Semántica de los Lenguajes pág. 8 de Página 8 de 25 
Cierre 
 L*=L+  {} 
 
 
 
El cierre de un lenguaje se forma por la 
unión de su clausura positiva a la cadena 
vacía. 
Reflexión L-1 
L-1={x-1 / xL} 
Esta formada por la aplicación de la 
reflexión a cada una de las palabras de L. 
 
Conceptos de regla de producción y derivaciones en una gramática 
Una regla de producción, es una descripción notacional de la forma N->R donde la parte 
izquierda N es un elemento que se define (o genera, o deriva, o produce) a partir de la 
parte derecha R. 
 
Producción x->y / x,y  * 
 
Una producción es una regla que indica que si se 
encuentra x como parte de cualquier palabra v, 
entonces se puede sustituir x por y en v. 
 
Ejemplo: 
En *3, donde 3={0,1} 
se podrían tener las producciones… 
P1 11::=10 
P2 00::=01 
P3 010::=110 
Cierre de un alfabeto 
* = +  { }= W() 
Sintaxis y Semántica de los Lenguajes pág. 9 de Página 9 de 25 
Derivación Directa vw Es la aplicación de una producción x->y a una 
palabra v, para convertirla en otra w, tal que: 
v=z.x.u => w=z.y.u 
donde (v,w,z,u  *) 
Es obvio: que haciendo z,u=, para cada 
producción x->y, existe una derivación directa 
xy 
Derivación v*w Indica que de una palabra v se puede llegar a otra 
w por la aplicación sucesiva de una secuencia de 
producciones. 
Ejemplo: sea v=0110101 y aplicando las producciones 
anteriores
 
Derivación por la izquierda Decimos que utilizamos derivación por la izquierda, 
si en cada derivación directa se utiliza la 
producción que aplica a los símbolos que se 
encuentren más a la izquierda de la palabra. 
Ejemplo: sea v=100110 y aplicando las producciones 
anteriores 
 
Derivación por la derecha Se utiliza derivación por la derecha, si en cada 
derivación directa se utiliza la producción que 
aplica a los símbolos que se encuentran más a la 
derecha de la palabra. 
Ejemplo: para la misma v=100110 y aplicando las 
producciones anteriores 
 
Regla compresora Se denomina regla compresora aquella cuya parte 
derecha tiene menos símbolos (menor longitud) 
que la parte izquierda. 
Ejemplo: 
Sean P: 011->11 y v=0011011 
 
De esta forma si aplico esta regla a la derivación 
de una palabra, la palabra resultante se comprime.