Compiladores

COMPILADORES 
Las Estructuras Formales: Lenguajes Formales y Gramática 

ALVAREZ ALVAREZ, GUSTAVO ALEXANDER

1

1. INTRODUCCION Uno de los conceptos más importantes de este texto es el de Lenguaje. Para llegar a este concepto es necesario definir antes otras nociones más elementales. Para todas las definiciones utilizaremos extensivamente la teoría elemental de conjuntos. 2. SÍMBOLOS Un“símbolo” es una entidad abstracta que no definiremos, de la misma manera que los conceptos “punto” y “línea”, no se definen en geometría. Las letras y los dígitos son ejemplos de símbolos usados con frecuencia. 3. CADENA DE CARACTERES Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos. Por mencionar a, b y c son símbolos, y abcb es una cadena. La longitud de una cadena w, que sedenota como w , es el numero de símbolos que componen la cadena. Por ejemplo, abcb tiene longitud 4. Las cadenas de caracteres son llamadas también palabras. La longitud de una palabra es la cantidad de letras que contiene, contando las repeticiones; se denota por w para una palabra w . Por ejemplo, perro es 5 Un caso particular es la cadena vacía, denotada por ε , es la cadena que consiste en cerosímbolos. Por tanto ε = 0 . Los prefijos de una cadena están formados por los primeros símbolos de esta; y los sufijos, por los últimos. Por ejemplo, la cadena abc tiene como prefijos: a, ab y abc; sus sufijos son ε , c , bc y abc . Un prefijo o sufijo de una cadena que no sea la misma cadena es un prefijo o sufijo propios. 3.1.1. Operaciones Con el fin de manipular las cadenas es convenienteintroducir varias operaciones Para las cadenas

x = a1a2 … ah y = b1b2 … bk

La concatenación es definido como

x. y = a1a2 … ah b1b2 … bk
Se puede obviar el punto, solo escribiendo xy en lugar de x. y . Esta operación es esencial para los lenguajes formales y además desempeña la funciona de la teoría de números. Ejemplo: Sean las cadenas:

x = gel , y = a, z = tina

Luego obtendremos

2xy = gela yx = agel ≠ xy ( xy ) z = gela.tina = x( yz ) = gel.atina = gelatina
3.1.2. Cadenas Vacías Es útil introducir el concepto de cadenas vacía (o nula), denotadas por la letra griega Epsilon ε , como la única cadena de la satisfacción de la identidad xe = ex = x . Para cada cadena x, por propiedad de la igualdad una cadena vacía tiene longitud cero:

ε =0
Desde una perspectivaalgebraica, la cadena vacía es un elemento neutral con respecto a la concatenación, porque ninguna cadena se vería afectada por concatenar a ε hacia su derecha o izquierda. La cadena vacía no debe de confundirse con el conjunto vacío: el factor ∅ de hecho que no contiene alguna cadena, mientras que el conjunto {ε } contiene una, la cadena vacía. 3.1.3. Subcadenas Tenemos x = uyv de alguna concatenación,posiblemente vacía, cuyas cadenas son u , y , v . Además y es una subcadena de x , además u es prefijo de x, y v es sufijo de x. Una subcadena (prefijo, sufijo) es llamado propia si no coincide con la cadena x . Tenemos x como una cadena de al menos una longitud k , x ≥ k ≥ 1 . La notación

Inik ( x) denota el prefijo u de x teniendo como longitud k o longitud inicial k.
Ejemplo: La cadena x =aabacba contiene los siguientes componentes: prefijo: a, aa, aab, aaba, aabac, aabacb, aabacba sufijo: a, ba, cba, acba, bacba, abacba, aabacba subcadenas: todos los prefijos y sufijos y las cadenas internas como a, ab, ba, bacb,…

4. ALFABETO Un alfabeto es un conjunto no vació de símbolos, es también un conjunto finito de elementos llamados símbolos finales o caracteres. = {a, b, c,...., z} ,es solo uno de tantos alfabetos Así el alfabeto del idioma español posibles. En general utilizaremos la notación ∑ para representar un alfabeto. Con los símbolos de un alfabeto es posible formar secuencias o cadenas de caracteres, tales como mxzzptlk , balks , r ,etc. Cuando escribimos varias palabras o caracteres uno a continuación de otro, se supone que forman una sola palabra (se...