Introducción a la teoría de autómatas, lenguajes y computación
Introducción a la Teoría de Lenguajes
description
Transcript of Introducción a la Teoría de Lenguajes
Introducción a la Teoría de Lenguajes
Preparado por
Manuel E. Bermúdez, Ph.D.Profesor Asociado
University of Florida
Curso de Compiladores
Introducción a la Teoría de LenguajesDefinición: Un alfabeto (o vocabulario) Σ es un
conjunto finito de símbolos.
Ejemplo: Alfabeto de Pascal:+ - * / < … (operadores)begin end if var (Palabras reservadas)<identifier> (Identificadores)<string> (hileras)<integer> (enteros); : , ( ) [ ] (puntuación)
Nota: Todos los identificadores son representados por un símbolo, porque Σ debe ser finito.
Definición: Una secuencia t = t1t2…tn de símbolos de un alfabeto Σ es una hilera.
Definición: La longitud de la hilera t = t1t2…tn
(se denota |t|) es n. Si n = 0, la hilera es ε, la hilera vacía.
Definición: Dadas las hileras s = s1s2…sn
t = t1t2…tm,
la concatenación de s y t se denota st, yes la hilera s1s2…snt1t2…tm.
Introducción a la Teoría de Lenguajes
Nota: εu = u = uε, uεv = uv, para hileras cualesquier u,v (incluyendo ε)
Definición: Σ* es el conjunto de todas las hileras de símbolos de Σ.
Nota: Σ* es llamada la clausura transitiva y reflexiva de Σ.
Σ* está descrito por un grafo (Σ*, ·), donde “·” denota concatenación, y hay un nodo de inicio designado, ε.
Introducción a la Teoría de Lenguajes
Ejemplo: Σ = {a, b}.
(Σ*, ·)
Σ* es contablemente infinito: no se puede calcular todo Σ*. Solo se pueden calcular subconjuntos finitos de Σ*. Pero SÍ se puede calcular si una hilera dada pertenece a Σ*.
ε
a
b
aa
ab
ba
bb
aba
abba
b
ba
a
b
a
b
Introducción a la Teoría de Lenguajes
Introducción a la Teoría de Lenguajes
• Ejemplo: Σ = Vocabulario de Pascal. Σ* = Todos los posibles programas
potenciales de Pascal, i.e. todas las posibles entradas al compilador de Pascal.
• Deseamos especificar L Σ*, los programas de Pascal correctos.
• Definición: Un lenguaje L sobre un alfabeto Σ es un subconjunto de Σ*.
Introducción a la Teoría de Lenguajes
Ejemplo: Σ = {a, b}.L1 = ø es un lenguajeL2 = {ε} es un lenguajeL3 = {a} es un lenguajeL4 = {a, ba, bbab} es un lenguajeL5 = {anbn / n >= 0} es un lenguaje
donde an = aa…a, n vecesL6 = {a, aa, aaa, …} es un lenguaje
• Nota: L5 es un lenguaje infinito, pero descrito finitamente.
Introducción a la Teoría de Lenguajes
• ESTE ES EL OBJETIVO PRINCIPAL DE LA ESPECIFICACION DE LENGUAJES:
Describir (en forma finita) un lenguaje de programación (infinito), y proporcionar un algoritmo de prueba-de-inclusión correspondiente (finito).
Constructores de Lenguajes
Definición: La concatenación (o producto) de dos lenguajes L1 y L2, se denota L1L2, y es el conjunto {uv | uL1, vL2}.
Ejemplo: L1 = {ε, a, bb}, L2 = {ac, c}
L1L2 = {ac, c, aac, ac, bbac, bbc}
= {ac, c, aac, bbac, bbc}
Definición: Ln = LL…L (n veces), y L0 = {ε}.
Ejemplo: L = {a, bb} L3 = {aaa, aabb, abba, abbbb, bbaa, bbabb, bbbba, bbbbbb}
Constructores de Lenguajes
Definición: La unión de dos lenguajes L1 y L2 es el conjunto L1 L2 = {u | uL1} { v | vL2}
Definición: La clausura de Kleene (L*) de un lenguaje es el conjunto L* = U Ln, n >0.
Ejemplo: L = {a, bb} L* = {cualquier hilera compuesta de a’s y bb’s}
Definición: La clausura transitiva(L+) de un lenguaje L es el conjunto L+ = U Ln, n > 1.
∩ ∩
Constructores de Lenguajes
Nota: En general, L* = L+ U {ε}, pero L+ ≠ L* - {ε}.
Por ejemplo, considerar L = {ε}. Entonces {ε} = L+ ≠ L* – {ε} = {ε} – {ε} = ø.
Constructores de Lenguajes
Gramáticas
• Objetivo: Proporcionar un mecanismo finito para la descripción de lenguajes infinitos.
• Método: Se da un subgrafo (Σ*, →*) de (Σ*, ·), y un nodo inicial S, tal que los nodos accesibles (desde S) son las hileras en el lenguaje.
Gramáticas
Ejemplo: Σ = {a, b}
L = {anbn / n > 0}
ε
a
b
aa
ab
ba
bb
aab
aaa
bbb
bba
aaba
bbaa
bbab
aabb
b
a
b
a
b
a
a
b
bb
a
a
a
b
Gramáticas
Definición: “=>” (deriva) es una relación definida por un conjunto finito de reglas dere-escritura conocidas como producciones.
Definición: Dado un vocabulario V, una producción es un par (u, v) V* x V*, denotado u → v. u es llamada la parte-izquierda; v es llamada la parte-derecha.
Gramáticas
Ejemplo: Pseudo-Inglés.V = {Sentence, NP, VP, Adj, N, V, boy, girl, the,
tall, jealous, hit, bit}
Sentence → NP VP (una producción)NP → NNP → Adj NPN → boyN → girlAdj → theAdj → tallAdj → jealousVP → V NPV → hitV → bit
Nota: El inglés es demasiado complicado para ser descrito de esta manera.
GramáticasDefinición:
Dado un conjunto finito de producciones P V* x V*, se define la relación “=>” tal que
para todo , β, u, v V* , uβ => vβ sii (u,v) P es una producción.
Ejemplo: Sentence → NP VP Adj → the NP → N Adj → tall NP → Adj NP Adj → jealous N → boy VP → V NP N → girl V → hit
V → bit
Gramáticas
Sentence => NP VP=> Adj NP VP=> the NP VP=> the Adj NP VP=> the jealous NP VP=> the jealous N VP=> the jealous girl VP=> the jealous girl V NP=> the jealous girl hit NP => the jealous girl hit Adj NP=> the jealous girl hit the NP=> the jealous girl hit the N => the jealous girl hit the boy
GramáticasDefinición: Una gramática es una tupla de 4 elementos, G = (Φ, Σ, P, S), donde
Φ es un conjunto de no-terminales, Σ es un conjunto de terminales, V = Φ U Σ es el vocabulario de la gramática,
S Φ es el símbolo de inicio (o meta), y P V* x V* es un conjunto finito de
producciones.
Ejemplo: Gramática para {anbn / n > 0}:
G = (Φ, Σ, P, S), dondeΦ = {S}, Σ = {a, b}, y P = {S → aSb, S → ε}
Gramáticas
Derivaciones:S => aSb => aaSbb => aaaSbbb => aaaaSbbbb → …
ε ab aabb aaabbb aaaabbbb
Nota: Normalmente, las gramáticas son dadas por un simple listado de las producciones.
=> => =>=> =>
Convenciones gramaticales
convención del TWS
1. Letra mayúscula (identificador) – nonterminal2. Letra minúscula(hilera) – terminal3. Letra griega minúscula– hileras en V*4. La parte izquierda de la primera producción
se considera el símbolo de inicio, ej.S → aSbS → ε
1. La parte izquierda se omite si es la misma que para la producción anterior, ej.S → aSb → ε
Gramáticas Ejemplo: Gramática para identificadores.
Identificador → Letra → Identificador Letra → Identificador
Dígito Letra → ‘a’ → ‘A’ → ‘b’ → ‘B’
. . → ‘z’ → ‘Z’
Dígito → ‘0’ → ‘1’ . . → ‘9’
Gramáticas
Definición: El lenguaje generado por la gramática G, es el conjunto
L(G) = { Σ* | S =>* }
Definición: Una forma sentencial generada por una gramática G es cualquier hilera tal que S =>* .
Definición: Una sentencia generada por
una gramática G es cualquier forma sentencial tal que Σ*.
GramáticasEjemplo:
formas sentenciales
S => aSb => aaSbb => aaaSbbb => aaaaSbbbb > … ε ab aabb aaabbb aaaabbbb
Lemma: L(G) = { | es una sentencia}
Prueba: Trivial.
=> => => =>=>sentencias
Gramáticas
Ejemplo: A → aABC→ aBC
aB → ab B se reemplaza con b, pero
bB → bb solamente en el contexto bC → bc de tener a ó b a la
izquierda CB → BC
cC → cc
GramáticasDerivación: A => aABC => aaABCBC => …
aBC aaBCBC aaaBCBCBC abC aabCBC aaaBBCBCC abc aabBCC aaaBBBCCC
aabbCC aaabBBCCC (2) aabbcC aaabbbCCC aabbcc aaabbbcCC (2)
aaabbbccc
L (G) = {anbncn | n > 1} sensible al contexto
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
A → aABC
→ aBC
aB → ab
bB → bb
bC → bc
CB → BC
cC → cc
La Jerarquía de Chomsky
Una jerarquía de gramáticas, de los lenguajes que generan, y de las
máquinas que aceptan esos lenguajes.
La Jerarquía de ChomskyTipo Nombre del
LenguajeNombre de la Gramática
Restricciones sobre la Gramática
MáquinaAceptadora
0 RecursivamenteEnumerable
Sistema de re-escritura sin restricciones
Ninguna Máquinade Turing
1 Lenguaje sensible al contexto
Gramáticasensible al contexto
Para todo →, ||≤||
MáquinaAcotada Lineal
2 Lenguaje libre de contexto
Gramáticalibre de contexto
Para todo →,Φ.
Autómatade pila (parser)
3 Lenguaje Regular
GramáticaRegular
Para todo →,Φ, U ΦU{}
Autómatade Estado Finito (lexer)
Jerarquía del Chomsky
3: Lenguajes Regulares
{an | n > 0}
2: Lenguajes Libres de Contexto
1: Lenguajes Sensibles al Contexto
{anbn | n>0}
{anbncn | n>0}
0: Lenguajes Recursivamente Enumerables
¿ Lenguaje natural ?
Trataremos con los lenguajes de tipo 2 (sintaxis) y los de tipo 3 (léxico).