Programacion
Compilador
Intérprete
Intérprete de ByteCodes
1
Procesadores de Lenguajes
Compilador Just-In-Time
Hot Spot
2
Procesadores de Lenguajes
Modelo Conceptual de un Compilador
3
Procesadores de Lenguajes
Tema 2: Construcción de un analizador léxico. 2.1. Conceptos fundamentales 2.2 Diseño e implementación de un analizador léxico. 2.3Generación automática de analizadores léxicos.
4
Procesadores de Lenguajes
Conceptos básicos
Alfabeto: Conjunto finito de símbolos ( Σ={0,1} ) Cadena sobre un alfabeto: Secuencia finita de símbolos del alfabeto ( ω= 101) Sea s una cadena, |s| denota la longitud de la cadena s ( |101| = 3 )
ε denota la cadena vacía
( |ε| = 0 )
Lenguaje: Conjunto de cadenas de símbolos de algúnalfabeto
Σ∗ Conjunto de todas las cadenas sobre el alfabeto Σ (lenguaje universal sobre el alfabeto Σ)
Operaciones sobre lenguajes
Sean L, M dos lenguajes. Unión L∪M={x | x∈L ∨ Concatenación L • M = { xy | x ∈ L ∧ L2= L•L
∞
x∈M} y∈M} … L1=L L0= { ε }
L3= L•L2,
Cierre reflexivo-transitivo (clausura de Kleene)
L = Li
* i =0
Cierre transitivo (clausura positiva)
L = s Li
+ i=1
∞
5
Procesadores de Lenguajes
Expresión Regular
• Dado Σ, una Expresión Regular (ER) sobre Σ se define como: • • • • ∅ es una ER y define el lenguaje ∅.
ε es una ER y define el lenguaje { ε }.
a ∈ Σ es una ER y define el lenguaje { a }. Si r y s son ER siendo Lr y Ls sus lenguajes respectivos, entonces se cumple: r s es una ER y define el lenguaje Lr ∪ Ls r ⋅ s es una ER ydefine el lenguaje Lr ⋅ Ls r* es una ER y define el lenguaje Lr*
Conjunto Regular.
Lenguaje definido por una E.R.
6
Procesadores de Lenguajes
Autómata Finito
Es un reconocedor que toma una cadena como entrada y contesta: si, si la cadena es una sentencia del lenguaje no, en caso contrario.
Autómata Finito no Determinista.
AFND = (Q, Σ, δ, q0, F)
F ⊆ Q;
q0 ∈ Q;
δ : Q × ( Σ∪ {ε} ) → P(Q)
Autómata Finito Determinista.
AFD = (Q, Σ, δ, q0, F)
F ⊆ Q;
q0 ∈ Q;
δ : Q × Σ → Q
Equivalencias
E.R. ↔ AFND con ε-trans ↔ AFND ↔ AFD
7
Procesadores de Lenguajes
Autómata ejemplo de analizador léxico
8
Procesadores de Lenguajes
Ejemplo de especificación léxica en LEX
%{ /* definición de las constantes manifiestas MEN, MEI, IGU, DIF, MAY, MAI,IF, THEN, ELSE, ID, NUMERO, OPREL */ %} /* definiciones regulares */ delim [ \t\n] eb {delim}+ letra [A-Za-z] dígito [0-9] id {letra} ({letra} | {dígito})* número {dígito}+(\.{dígito}+)?(E[+\-]?{dígito}+)? %% {eb} if then else {id} {número} "=" %% instala_id() { /* procedimiento para instalar el lexema, cuyo primer carácter está apuntado por yytexto y cuya longitud es yylong, dentro de la tabla desímbolos y devuelve un apuntador a él */ } instala_núm() { /* procedimiento similar para instalar un lexema que es un número */ } {/* no hay acción ni se devuelve nada */} {return(IF);} {return(THEN);} {return(ELSE);} {yylval = instala_id(); return(ID);} {yylval = instala_núm; return(NUMERO);} {yylval = MEN; return(OPREL);} {yylval = MEI; return(OPREL);} {yylval = IGU; return(OPREL);} {yylval =DIF; return(OPREL);} {yylval = MAY; return(OPREL);} {yylval = MAI; return(OPREL);}
9
Procesadores de Lenguajes
Tema 3: Construcción de un analizador sintáctico descendente. 3.1. Especificación sintáctica de un lenguaje. 3.2. Tipos de análisis sintácticos. 3.3. Construcción de un analizador sintáctico descendente. 3.3.1. Condición LL(1) 3.3.2. Cálculo de PRIM y SIG 3.3.3. Transformación degramáticas 3.3.4. Construcción de un ASDR 3.4. Tratamiento y recuperación de errores. 3.5. Generación automática de analizadores sintácticos descendentes.
10
Procesadores de Lenguajes
Gramáticas Incontextuales G = (N, Σ, P, S) S ∈ N; V = N ∪ Σ; (A → α) ∈ P N∩Σ=∅
A ∈ N; α ∈ V*
Derivación Directa. δAγ⇒δβγ sii ∃ (A → β) ∈ P; δ, γ ∈ V*
Derivación. α ⇒* β sii ∃ α0, ..., αm ∈ V*...
Regístrate para leer el documento completo.