View
9
Download
0
Category
Preview:
Citation preview
Clase 12: Clasificación de gramáticas
Solicitado: Ejercicios 10: Clasificación de gramáticas
1M. en C. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom
edfrancom@ipn.mx
Contenido• Avram Noam Chomsky
• Jerarquía de Chomsky
• Gramáticas tipo 3
• Gramáticas tipo 2
• Gramáticas tipo 1
• Gramáticas tipo 0
• Clasificación de una gramática
• Descripción de las gramáticas
• Ejercicios 10: Clasificación de gramáticas
Compiladores (Lenguajes y gramáticas - Edgardo A. Franco)
2
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
�En 1950 el lingüista norteamericano Avram Noam Chomsky introdujo
la teoría de las gramáticas transformacionales o teoría de lenguajes
formales, que convirtió la lingüística en una ciencia y proporcionó una
herramienta que no sólo podía aplicarse a los lenguajes naturales, sino
que facilitaba el estudio y la formalización de los lenguajes para la
programación de computadoras (1960).
Estudio
tradicional
de los
lenguajes
gramática
semántica
análisis de la
estructura de las frases
estudio de su
significado
morfología
sintaxis
fonéticaaún no
aplicable a los
lenguajes de
computación
Diversas formas que toman
las palabras según su valor
en la frase
Diversas formas en que se
combinan las palabras para
formar frases correctas
Propiedades del
lenguaje hablado
3
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
4
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• En función de la forma de sus producciones, sepuede caracterizar qué tan compleja es unagramática formal.
• Noam Chomsky mostró que esta caracterizaciónclasifica jerárquicamente a las gramáticas formales:Gramáticas en un nivel están incluidas en lossiguientes niveles y la inclusión entre niveles espropia.
Gramáticas Tipo 3 (gramáticas regulares)
• Generan los lenguajes regulares. Las reglas(producciones) se restringen a un único no terminal enla parte izquierda y una parte derecha compuesta por unúnico terminal que puede estar seguido o no de unúnico no terminal. Es decir, normas del tipo:
A�aB
A � a
• Estos lenguajes son los que pueden ser decididos por unautómata finito (regular). Los lenguajes regulares se utilizanpara definir estructura léxica de los lenguajes de programación.Definen la sintaxis de los identificadores, números, cadenas yotros elementos básicos del lenguaje.
5
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
6
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramáticas Tipo 2(independientes o libres de contexto)
• Generan los lenguajes libres de contexto. Están definidas por
reglas de la forma:
A ���� γγγγ• A es un no terminal
• γγγγ es una cadena de terminales y no terminales.
• Se denominan independientes de contexto porque A puede
sustituirse por γ independientemente de las cadenas por las
que esté acompañada.
• Estos lenguajes son todos los lenguajes que pueden ser
reconocidos por los autómatas de pila.
• Los lenguajes independientes de contexto constituyen la base teórica para la
sintaxis de la mayoría de los lenguajes de programación. Definen la sintaxis de
las declaraciones, las proposiciones, las expresiones, etc.(i.e. la estructura de
un programa).
Gramáticas Tipo 1 (dependientes de contexto)
• Generan los lenguajes dependientes de contexto. Contienen reglas de producción de la forma:
αααα A ββββ���� αααα γγγγ ββββ• A es un no terminal
• αααα, ββββ y γγγγ son cadenas de terminales y no terminales.
• αααα y ββββ pueden ser vacíos, pero γγγγ ha de ser distinto del vacío.
• Se denominan gramáticas dependientes del contexto, porque,como se observa, A puede ser sustituido por γ si estáacompañada de α por la izquierda y de β por la derecha.
• Estos lenguajes son todos los lenguajes que pueden serreconocidos por autómatas lineales acotados (Maquina deTuring Determinista). 7
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramáticas Tipo 0 (sin restricciones)
• Incluyen todas las gramáticas formales.
• El más general, al que pertenece la semántica de los
lenguajes naturales y artificiales.
• A estos lenguajes no se les impone restricción
alguna.
• Estos lenguajes son todos los lenguajes que pueden
ser reconocidos por una máquina de Turing.8
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Se dice que un lenguaje es de tipo k [k = 0, k = 1, k =
2, k = 3] cuando existe una gramática de tipo k que
genera ese lenguaje.
• La clasificación de la gramática será la
correspondiente al tipo de la producción de menor
clasificación.
9
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramática LenguajeReglas de
Producción
Si µµµµ ���� ϕϕϕϕ,
relación entre
|µµµµ| y |ϕϕϕϕ|
Solución
Tipo-0 RecursivasSin
restricciones
Máquinas de
Turing
Tipo-1Dependiente de
contexto αAβ ���� αγβ
|µµµµ| ≤≤≤≤ |ϕϕϕϕ| Autómatas
lineales
acotados
Tipo-2Independiente de
contexto A ���� γ
|µµµµ| = 1 Autómatas de
pila
Tipo-3 RegularA���� aBA ���� a
|µµµµ| = 1
Autómatas
finitos,
regulares
G3 ⊂⊂⊂⊂ G2 ⊂⊂⊂⊂ G1 ⊂⊂⊂⊂ G0 10
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas Regulares (tipo 3 o G3)
• Gramáticas Regulares (tipo 3 o G3)
• El lado izquierdo consiste sólo de una variable.
• El lado derecho consiste de
• Un símbolo terminal seguido de una variable ó
• Sólo un símbolo terminal ó
• La cadena vacía.
P.g.: A → aB | a | λ
11
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas Regulares (tipo 3 o G3)
12
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas Libres de Contexto, GLC, (tipo 2 o G2)
• Gramáticas Libres de Contexto, GLC, (tipo 2 o G2)
• El lado izquierdo consiste sólo de una variable.
• No hay restricciones para el lado derecho.
P.g.: S → aSb | ab | λ
13
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas Libres de Contexto, GLC, (tipo 2 o G2)
14
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Gramáticas Sensitivas al Contexto (tipo 1 o G1) A es unsímbolo no terminal. Además, las reglas son no-contractivas,i.e. la longitud del lado izquierdo es menor o igual a lalongitud del lado derecho. Esta propiedad de no-contraccióngarantiza que un lenguaje sensitivo al contexto no contiene λ.
P.g.:
S → abc | aAbc Ab → Acb Ac → Bbcc
aB → aa | aaA
Descripción de las gramáticasGramáticas Sensitivas al Contexto (tipo 1 o G1)
15
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas Sensitivas al Contexto (tipo 1 o G1)
16
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Gramáticas sin restricción (tipo 0 o G0), no hay restricciones para las reglas, excepto que el lado izquierdo no es λ.
P.g.:
S → aSBC | aBC CB → BC aB → abbB → bb bC → bc cC → cc
A → bc
Descripción de las gramáticasGramáticas sin restricción (tipo 0 o G0)
17
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Descripción de las gramáticasGramáticas sin restricción (tipo 0 o G0)
18
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Ejercicios 10 “Clasificación de gramáticas"
• Clasificar las siguientes gramáticas dadas sus reglasde producción.
*Se entregarán antes del día Lunes 14 de Octubre de 2013(23:59:59 hora limite)
*Incluir la redacción de cada ejercicio
*Portada y encabezados de pagina
19
Ga Gb Gc Gd Ge Gf Gg
Z → yX
X →y
X→λyX → yx
X →xZyW
yW → yx
Z→vy
E → E+T
E → E-T
E → T
T → T*F
T → T/F
T → F
F → (E)
F → id
S → aAbcAb → bAAc→BbccbB→bbaAA→ aaB → bb
A → bC
A → bBC
bB→bCa
C →b
C→λyCc → yCc
S→aAB|A
A→cBd
B→e|fS
C→gD|hDt
D→x|y|z
S → aS
S → aN
N → bN
N → bM
N → b
M → c
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
2:
Cla
sifi
caci
ón
de
gra
má
tica
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Recommended