LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 1
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ALFABETOS
Definición
: conjunto finito y no vacío de símbolos.
Ejemplos: binario, vocales, letras, ajedrez, otros.
Pertenencia de símbolos; cardinalidad de alfabetos.
Relaciones: igualdad, inclusión e inclusión estricta.
Operaciones: unión, intersección, complementos.
Propiedades de las operaciones (son conjuntos !!!).
Concatenación o yuxtaposición de alfabetos y de símbolos
de un alfabeto.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 2
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
PALABRAS, cadenas, tiras o strings
Definición: concatenación de símbolos de un alfabeto.
Longitud de una palabra.
Palabra vacía. Largo cero !!!
Concatenación de palabras sobre un alfabeto. Potenciación.
Propiedades: no conmutativa, asociativa, elemento neutro.
Subpalabra (=), sufijo y prefijo (=) propios e impropios.
Palabra inversa o refleja. Palíndromos.
Nuevas operaciones con alfabetos:
Concatenación:
1
.
2
= {=xy / x
1
y
2
}
Potenciación:
n
=
n-1
. si n > 0,
n
= {} si n = 0
Clausura positiva:

Clausura o Cierre:

Estas operaciones generan conjuntos de “palabras”.
Universo de Discurso de un alfabeto: W() =
*
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 3
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
LENGUAJES
Lenguaje sobre un alfabeto : L *
Lenguaje vacío y lenguaje con cadena vacía. Cardinalidad.
Igualdad, inclusión e inclusión estricta.
Operaciones con lenguajes:
Unión / Intersección / Complementos / Concatenación
Potenciación, clausura positiva, clausura o cierre.
Inversión o reflexión.
Nueva operación con cadenas:
Regla de reescritura o producción: :=
Derivación directa por aplicación de producción:
Derivación (en cero o más pasos): *
Derivación por derecha, por izquierda y mixta.
Reducción (en cero o más pasos): *
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 4
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
LENGUAJES
Dado un alfabeto , un lenguaje es un conjunto de palabras
definidas sobre él: L
*
Descripción de lenguajes (son conjuntos !!!):
Por enumeración o extensión
Por comprensión
Conjunto con una propiedad (propiedad)
Conjunto con fórmula-patrón (algebraicamente)
GRAMÁTICA FORMAL (estableciendo cómo se derivan sus
elementos desde un símbolo inicial)
Recordar: LENGUAJES NATURALES vs LENGUAJES FORMALES
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 5
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
GRAMÁTICA FORMAL
Definición de la gramática G: (
T
,
N
, S, P) ;
T
N
= ; S
N
Lenguaje generado por G: L(G) = {

T
* / S * }
Noam Chomsky, Backus, Naur y BNF (ver formato).
Forma sentencial: S * ; (
T
N
)*
Sentencia: S * ; 
T
*
Equivalencia: G1
G2 L(G1) = L(G2)
Regla no compresora: := ; || ||
Regla compresora: := ; || > ||
Regla lambda: S := ; S = axioma
Regla innecesaria: A := A ; A = un símbolo no terminal
Regla no generativa: A :=
; A axioma
Regla de redenominación: A := B ; A y B símbolos no terminales
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 6
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
Tipos de Lenguajes: Jerarquía de Chomsky (1956)
Tipo 0: Estructurados por frases, sin restricciones o recursivamente
enumerables.
A := , , (
T
N
)
*
A
N
Tipo 1: Dependiente del contexto o sensibles al contexto.
(admiten reglas contextuales)
A :=  , (
T
N
)
*
(
T
N
)
+
A
N
S :=
(sin reglas compresoras salvo para el axioma)
Tipo 2: Independiente del contexto o de contexto libre.
A := A
N
(
T
N
)
+
S := S = axioma
Tipo 3: Regulares o Lineales.
A := a|aB ó Lineales por derecha
A := a|Ba ó Lineales por izquierda
S
A, B, S
N
a
T
S = axioma
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 7
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
TIPOS DE LENGUAJES: Jerarquía de Chomsky (1956)
? 0 Estructurados por Frases
1 Dependientes del Contexto
2 Independientes del Contexto
3 Regulares o Lineales
L3
L2 L1 L0
Sin reglas
compresoras
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 8
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
LENGUAJES REGULARES
Todo lenguaje finito es regular.
Si L1 y L2 son lenguajes regulares, también lo son su unión,
concatenación y clausura transitiva y reflexiva.
Solo son regulares los lenguajes construidos con lo anterior.
EXPRESIONES REGULARES (ER)
es una ER que denota al lenguaje L() = {}
es una ER que denota al lenguaje L() = {}
a, a es una ER que denota al lenguaje L(a) = {a}
Si E1 y E2 son expresiones regulares que denotan a L1 y L2, entonces:
E1+E2 es una ER que denota al lenguaje L(E1+E2) = L1 L2
E1.E2 es una ER que denota al lenguaje L(E1 . E2) = L1 . L2
E1* es una ER que denota al lenguaje L(E1*) = L*(E1) = L1*
(E1) es una ER que denota al lenguaje L((E1)) = L(E1) = L1
Sólo son ER las construidas con las reglas anteriores.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 9
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
LENGUAJES INDEPENDIENTES DEL CONTEXTO
Gramática Limpia: una gramática independiente del contexto SIN:
Reglas innecesarias: A := A , A
N
Símbolos inaccesibles:
 , X(
T
N
)
Símbolos superfluos:

Gramática Bien Formada: una gramática limpia SIN:
Reglas no generativas: A :=
, A axioma
Reglas de redenominación: A := B , A,B
N
En cada caso, hay que ver cómo encontrar en la gramática y
cómo quitar de ella la característica no deseada,
obteniendo una gramática equivalente
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 10
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO
¿
L(G)?, siendo 
T
*
. Los procesos que usamos para responder
esta pregunta se denominan Análisis Sintáctico de la cadena
dada
una gramática G = (
T
,
N
, S, P).
Hasta ahora, respondemos:
SI, si podemos encontrar S* usando las reglas de P, y
NO, si demostramos que no existe S
*
Árbol de Derivación o de Análisis Sintáctico: representación
pictórica de la derivación S* de una cadena 
T
*
.
El axioma S de la gramática se sitúa en la raíz del árbol.
Si para A

N
existe en P la producción A := a
1
a
2
a
n
y ésta es
usada en la derivación, entonces se crean como hijos del nodo A
del árbol, nodos para cada uno de los a
i
en el orden anterior.
Así, los nodos internos son símbolos de
N
y las hojas de
T
.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 11
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO (continuación)
Ahora, también podemos responder a ¿
L(G)?:
SI, si podemos construir el árbol de análisis sintáctico de
, y
NO, si demostramos que tal árbol no existe.
Ambigüedad.
Decimos que una cadena 
T
*
es ambigua si y solo si existe
más de un árbol de análisis sintáctico ella en G.
Decimos que la gramática G es ambigua, si genera al menos una
cadena ambigua.
Un lenguaje L(G) se dice que es inherentemente ambiguo, si las
únicas gramáticas que lo generan son ambiguas.
La ambigüedad es una característica indecidible de las GIC.
La ambigüedad genera problemas de significado.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 12
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO (continuación)
Recursividad.
Decimos que una producción es recursiva, si el mismo no
terminal aparece en el lado derecho e izquierdo: A :=
A.
Si la gramática G posee una producción recursiva, se dice que
tiene recursividad en un paso.
Si no tiene producciones recursivas, pero puede efectuarse la
derivación A
*A, se dice que G posee recursión en más de
un paso.
Importancia de la recursión para generar lenguajes infinitos.
Recursión por izquierda: A := A - A*A
Recursión por derecha: A := A - A*A
Algunos algoritmos de análisis sintácticos para poder funcionar
requieren que no existe recursión por izquierda en la gramática.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 13
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO (continuación)
Recursividad (continuación)
Eliminación de recursión por izquierda en un paso: Dada una
gramática independiente del contexto G = (
T
,
N
, S, P) con
producciones recursivas por izquierda para el no terminal A
A := A
1
| A
2
| … | A
n
|
1
|
2
| … |
m
con
i
,
j
(
T
N
)
+
, entonces puede construirse una
gramática equivalente a la dada sin recursión por izquierda en A,
reemplazando esas producciones por:
A :=
1
X |
2
X | … |
m
X |
1
|
2
| … |
m
X :=
1
X |
2
X | … |
n
X |
1
|
2
| … |
n
donde X es un nuevo símbolo no terminal.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 14
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO (continuación)
Recursividad (continuación)
Eliminación de recursión por izquierda en más de un paso: Se
sigue un algoritmo iterativo donde se aplica la eliminación en un
paso reiteradamente (ver bibliografía).
Factorización por izquierda
Si en una GIC para un mismo no terminal A, hay producciones
que inician con los mismos símbolos en el lado derecho:
A :=

1
| 
2
entonces, se obtiene una gramática equivalente al reemplazar
esas producciones por:
A :=
X ; X :=
1
|
2
donde X es un nuevo símbolo no terminal.
LINGÜÍSTICA
MATEMÁTICA
Alfabetos
Palabras
Lenguajes
Gramática formal
Tipos de lenguajes
L. Regulares
Definición
Expresiones
regulares
L. Independientes
del Contexto
Limpia
Bien Formada
Análisis Sintáctico
¿L()?
Árbol
Ambigüedad
Recursión
Factorización
Forma Normal
UTN FRC ISI SSL Lingüística Matemática
JCV 15
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
ANÁLISIS SINTÁCTICO (continuación)
Formas Normales
Las GIC siempre pueden ser convertidas en gramáticas equivalentes,
en las cuales los lados derechos de sus producciones tengan un
formato uniforme. Estas gramáticas equivalentes reciben el nombre
de Formas Normales.
Estas normalizaciones son a veces convenientes para
desarrollar ciertos algoritmos de análisis sintáctico.
Recordemos que las GIC pueden tener como única producción
compresora, la regla lambda: S :=
. Todas las otras reglas
tendrán la forma A :=
donde (
T
N
)
+
, es una cadena de
terminales y no terminales.

Este documento contiene más páginas...

Descargar Completo
7_SSL_U5_Thompson.pdf
browser_emoji Estamos procesando este archivo...
browser_emoji Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
. . . . .