Resumen Sintaxis y Semantica de los Lenguajes UTN

INDICE
INTRODUCCIÓN LENGUAJES
LENGUAJES FORMALES
LENGUAJES INFINITOS
GRAMÁTICA FORMAL
GRAMÁTICA REGULAR (GR)
TIPO 3
GRAMÁTICA REGULAR INFINITAS (GRI)
GRAMÁTICA QUASI-REGULAR (GQR)
GRAMÁTICA INDEPENDIENTE DEL CONTEXTO (GIC)
TIPO 2
GRAMÁTICA INDEPENDIENTE DEL CONTEXTO INFINITAS (GICI)
GRAMÁTICA SENSIBLES AL CONTEXTO (GSC)
TIPO 1
GRAMÁTICA IRRESTRICTAS (GI)
TIPO 0
DERIVACIÓN A IZQUIERDA Y DERECHA DEUNA GRAMÁTICA
BNF
EXPRESIONES REGULARES
Metalenguaje para Expresiones Regulares (metaERs)
AUTOMATAS
AUTÓMATA FINITO
Cláusula Positiva y Cláusula Potencia (kleene)
AUTÓMATA FINITO DETERMINÍSTICO
AUTÓMATA FINITO DETERMINÍSTICO COMPLETO
COMPLEMENTO DE UN AUTÓMATA FINITO DETERMINÍSTICO
INTERSECCIÓN DE DOS DE UN AUTÓMATAS FINITOS DETERMINÍSTICOS
AUTÓMATA FINITO NO DETERMINÍSTICO
AUTÓMATA FINITO NODETERMINÍSTICO CON TRANSICIONES (ε)
ALGORITMO DE THOMPSON
ALGORITMO DE CLAUSURA (ε) ó CONSTRUCCION DE SUBCONJUNTOS
CONJUNTO “HACIA”
CONVERTIR UN AUTÓMATA FINITO NO DETERMINÍSTICO A UN AUTÓMATA FINITO
DETERMINÍSTICO (AFN
AFD)
CONVERTIR UN AUTÓMATA FINITO A LA EXPRESIÓN REGULAR (AF
ER)
OBTENCIÓN AUTÓMATA FINITO MINIMO (AFD MINIMO)
MAQUINA DE TURING
AUTÓMATA FINITO CON PILA (AFP)
AUTÓMATA FINITO CONPILA DETERMINÍSTICO (AFPD)
PROCESOS DE COMPILACION
ANÁLISIS LÉXICO
ANÁLISIS SINTACTICO
ANÁLISIS SEMANTICO
TABLA DE SÍMBOLOS
CONSTRUCCIÓN DE PROCEDIMIENTOS DE ANÁLISIS SINTÁCTICO (PAS)
CONVERTIR UNA GIC EN GIC LL(1)
CONJUNTO PRIMERO
ANSI C

SSL - UTN

Adrian B.

2
3
3
4
4
4
5
5
5
6
6
7
8
9
11
12
13
14
15
16
17
18
20
21
22
23
24
25
28
30
35
37
38
40
41
42
43
44
45
47
48
49

Hoja 1 de 1

INTRODUCCIÓNLENGUAJES

Σ* = todas las cadenas que se puedan formar
a+ = a . a* = aparece al menos una vez

SSL - UTN

Adrian B.

Hoja 2 de 2

LENGUAJE FORMAL

L1 = { ccccp, cccpp, ppccc, ppppcc}

LENGUAJE POR EXTENSIÓN

L 1 = { c 4 p , c 3 p2 , p 2 c 3 , p 4 c }

LENGUAJE POR COMPRENSIÓN

L 2 = { bn / 0 ≤ n ≤ 8 }
Por extensión seria
L2 = {λ , b, b2, ..., b8 }

LENGUAJE REGULAR INFINITO

L3 = { anbn / n > 0 }• Un sublenguaje de un Lenguaje Regular Infinito (LRI) puede ser finito o
infinito

SSL - UTN

Adrian B.

Hoja 3 de 3

GRAMÁTICA FORMAL

GRAMÁTICA REGULAR

GRAMÁTICA REGULAR INFINITA

Las gramáticas regulares que generan lenguajes infinitos tienen producciones recursivas

SSL - UTN

Adrian B.

Hoja 4 de 4

GRAMÁTICA QUASI-REGULAR

GRAMÁTICA INDEPENDIENTE DEL CONTEXTO

GRAMÁTICA INDEPENDIENTE DELCONTEXTO INFINITAS

SSL - UTN

Adrian B.

Hoja 5 de 5

Gramática Sensibles al Contexto

Gramática Irrestricta

SSL - UTN

Adrian B.

Hoja 6 de 6

Derivación de una Gramática

•
•
•

Tanto la derivación a izquierda como a derecha generan una misma palabra
La derivación es un proceso que permite obtener cada una de las palabras de un Lenguaje Formal a partir
del axioma
La derivación sirve paradeterminar si una cadena pertenece o forma parte del Lenguaje

Ejemplo:
Construya la Tabla de Derivación Vertical a Izquierda y la Tabla de Evaluación correspondiente para la
expresión 2 + 4 * 6. Utilizando las producciones de la siguiente GIC.
N° Producción
1
2
3
4
5

Producción
E T
E E+T
E F
E T*F
E 2|4|6

Tabla de Derivación Vertical a Izquierda
Producción
Aplicada
Axioma
2
1
3
5
4
3
5
5

SSL -UTN

Cadena de Derivación
Obtenida
E
E+T
T+T
F+T
2+T
2+T*F
2+F*F
2+4*F
2+4*6

Tabla de Evaluación
Cadena de
Derivación a
Reducir
2+4*6
2+4*F6
2+F4+F6
2+T4+F6
2+T24
F2+T24
T2+T24
E2+T24
E26

Adrian B.

Producción a Operación
Aplicar
5
5
3
4
5
3
1
2
Axioma

4*6 = 24

2+24 = 26
Resultado Final

Hoja 7 de 7

BNF

¿Como se construye una BNF?
•

Los no terminales van encerrados entre los signos < >

•

Laflecha

•

Lo que esta encerrado entre llaves aparece cero o mas veces {}

se cambia por dos veces dos punto y un igual ::=

Ejemplo de BNF ALGOL
::= letra {}
::= |
::= a | b | c | A | B | C
::= 0 | 1 | 2 | 3

SSL - UTN

Adrian B.

Hoja 8 de 8

EXPRESIONES REGULARES
Importante: los lenguajes finitos siempre...

Leer documento completo

Regístrate para leer el documento completo.