Programacion

Solo disponible en BuenasTareas
  • Páginas : 18 (4402 palabras )
  • Descarga(s) : 0
  • Publicado : 15 de noviembre de 2010
Leer documento completo
Vista previa del texto
Procesadores de Lenguajes

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*...
tracking img