compiladores e interpretes

Compiladores e Intérpretes
Coordinador: Prof. Ing. Pablo Pandolfo

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

1

Contenido:
Lenguajes Formales.
Gramáticas Formales.
Lenguajes Regulares.
Lenguajes Incontextuales.
Maquina de Turing.
Proceso de compilación

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

2Lenguajes Formales
Lenguajes Formales:
Los LENGUAJES FORMALES están formados por
PALABRAS, las palabras son CADENAS y las cadenas
están constituidas por SÍMBOLOS de un ALFABETO.

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

3

Lenguajes Formales
Símbolo:
Es el elemento constructivo básico; es la entidad
fundamental, indivisible, a partir de la cual se formanlos
alfabetos.
Ejemplos:
La letra a es un símbolo o carácter que forma parte del alfabeto
español, del alfabeto inglés, etc.
Los símbolos >, = y + son elementos del alfabeto de los operadores
de los lenguajes Pascal y ANSI C .

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

4

Lenguajes Formales
Alfabeto:
Es un conjunto (colección de objetos) no vacíoy finito de
símbolos.
Se lo identifica, habitualmente, con la letra griega Σ
(sigma) y con sus caracteres se construyen las palabras de
un lenguaje.
Ejemplo:
El alfabeto Σ = {0, 1} proporciona los caracteres utilizados en la
construcción de los números binarios.
Los números enteros con signo en base 10 se construyen con
símbolos del siguiente alfabeto: Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-, +}

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

5

Lenguajes Formales
Cadena
Es una secuencia finita de caracteres tomados de cierto
alfabeto y colocados uno a continuación de otro.
Se construye CONCATENANDO (yuxtaponiendo)
caracteres de un alfabeto dado.
Ejemplo:
abac (se lee “a-b-a-c”) es una cadena formada con caracteres del
alfabeto {a, b,c}.
101110 (“uno-cero-uno-uno-uno-cero”) es una cadena construida
con caracteres del alfabeto {0, 1}.

Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

6

Lenguajes Formales
Longitud de una cadena
La LONGITUD de una cadena S (se representa |S|) es la
cantidad de caracteres que la componen.
Ejemplo:
La longitud de la cadena abac es: |abac| = 4.
La longitudde la cadena b es: |b| = 1.

Cadena vacía
Se representa λ (lambda)
Es la cadena que no tiene caracteres.
Es la cadena de longitud 0 (|λ| = 0).
Este símbolo λ no forma parte de ningún alfabeto.
Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

7

Lenguajes Formales
Potenciación de un símbolo
cn representa la repetición del carácter c, n veces.
Simplificala escritura de cadenas.
Ejemplo: aaaaabbbbbbb = a5b7.

Concatenación de dos cadenas
La operación de CONCATENACIÓN aplicada a cadenas (S1S2)
produce una nueva cadena formada por los caracteres de la primera
cadena seguidos inmediatamente por los caracteres de la segunda
cadena.
Ejemplo: Sean las cadenas S1 = aab y S2 = ba; entonces, S1S2 =
aabba.
NO ES CONMUTATIVA
La cadena vacía (λ) esla IDENTIDAD para la concatenación. Esto es:
para cualquier cadena S, S λ = λ S = S.
Universidad Kennedy – Compiladores e Intérpretes – Prof. Ing. Pablo Pandolfo

8

Lenguajes Formales
Potenciación de una cadena
Si S es una cadena, entonces Sn (con n ≥ 1 y entero) representa la cadena que
resulta de concatenar la cadena S, consigo misma, n-1 veces.
S0 es λ (la cadena vacía), paracualquier cadena S
Ejemplo: Sea S = ab; entonces: S3 = SSS = (ab)3 = ababab.

Prefijo de una cadena:
Es una secuencia de cero o más caracteres iniciales de esa cadena.
Ejemplo: Sea la cadena abcd. Entonces, sus prefijos son: λ, a, ab, abc y abcd
(la cadena completa).

Sufijo de una cadena:
Es una secuencia de cero o más caracteres finales de esa cadena.
Ejemplo: Sea la cadena abcd. Entonces,...