Trabajo

Páginas: 6 (1348 palabras) Publicado: 24 de septiembre de 2012
Cálculo de PRIMERO
El conjunto PRIMERO(α), siendo α una forma sentecial, es el conjunto de Terminales que pueden aparecer los primeros en cadenas derivadas de α. El conjunto PRIMERO puede referirse a una forma sentencial (PRIMERO(α), siendo α por ejemplo aBD ), pero también a un símbolo No Terminal de la gramática considerada (PRIMERO(A)). Si la gramática está formada por reglas Aàαi el conjuntoPRIMERO(A) será la unión de todos los PRIMERO(αi), que deben ser calculados por separado. Para calcular PRIMERO(α) basta con seguir las siguientes reglas para cada regla de producción de la gramática: 1. Si α ≡ ∈, donde ∈ es la cadena vacía : Añadir { ∈ } a PRIMERO(α) 2. Si α ≡ a, donde a es un Terminal: Añadir { a } a PRIMERO(α) 3. Si α ≡ A, donde A es un No Terminal: Añadir PRIMERO(A) aPRIMERO(α). 4. Si α ≡ AB, donde A y B son No Terminales y PRIMERO(A) incluye { ∈ }: Añadir PRIMERO(A) a PRIMERO(α), pero sin incluir de momento { ∈ }. Además, y puesto que A puede ser vacío, añadir PRIMERO(B) a PRIMERO(α). Esta regla puede extenderse a todos los No Terminales que aparezcan detrás de A. Por ejemplo, si α ≡ ABCD y PRIMERO (A), PRIMERO(B) y PRIMERO(C) incluyen { ∈ }, entonces habrá queañadir a PRIMERO(α) la unión de PRIMERO(A), PRIMERO(B), PRIMERO(C) y PRIMERO(D), sin incluir { ∈ }. Por último se decide si incluir { ∈ } en PRIMERO(α): sólo debe incluirse si aparece en los conjuntos PRIMERO de todos los No Terminales. Por ejemplo en el caso anterior, si PRIMERO(D) también incluyese { ∈ }, entonces PRIMERO(α) incluiría { ∈ }.

Primer ejemplo detallado de cálculo de PRIMERO
Veamosun ejemplo de cálculo detallado de PRIMERO para la siguiente gramática, que describe expresiones aritméticas con sumas y multiplicaciones: E à T E’ E’ à + T E’ | ∈ T à F T’ T’ à * F T’ | ∈ F à ( E ) | ident • PRIMERO(E) = PRIMERO(TE’) (en adelante escribiremos simplemente PRIMERO(E) ). PRIMERO(E) = PRIMERO(T) por la Regla 3, así que pasamos a calcular PRIMERO(T). • • • • • PRIMERO(T) = PRIMERO(F)por la Regla 3, así que pasamos a calcular PRIMERO(F). PRIMERO(F) = { ( , ident } por la Regla 2. En este punto ya sabemos que PRIMERO(E) = PRIMERO(T) = PRIMERO(F)= { ( , ident } PRIMERO(E’) = { + , ∈ } por las Reglas 2 y 1. PRIMERO(T’) = { * , ∈ } por las Reglas 2 y 1.

Resultado: PRIMERO(E) = { ( , ident } PRIMERO(E’) = { + , ∈ } PRIMERO(T) = { ( , ident } PRIMERO(T’) = { * , ∈ } PRIMERO(F) ={ ( , ident }

Segundo ejemplo detallado de cálculo de PRIMERO
Veamos otro ejemplo de cálculo detallado de PRIMERO para la siguiente gramática, con el objetivo de aclarar el uso de la Regla 4: A à Aa | BCD Bàb|∈ Càc|∈ D à d | Ce • • • • • PRIMERO(A) = PRIMERO(Aa) ∪ PRIMERO(BCD) = PRIMERO(BCD) Calculamos el resto de los conjuntos PRIMERO, ya que vamos a necesitarlos PRIMERO(B) = { b , ∈ } porlas Reglas 2 y 1. PRIMERO(C) = { c , ∈ } por las Reglas 2 y 1. PRIMERO(D) = { d } ∪ PRIMERO(Ce). Como PRIMERO(Ce) incluye el elemento vacío, aplicamos la Regla 4 y calculamos PRIMERO(e) = { e }, quedando PRIMERO(D) = { d, c, e }. Obsérvese que por la Regla 4, { ∈ } no se incluye: intuitivamente se comprueba que D no puede derivar la cadena vacía. • PRIMERO(A) = PRIMERO(Aa) ∪ PRIMERO(BCD)PRIMERO(BCD) = PRIMERO(B) ∪ PRIMERO(C) ∪ PRIMERO(D) = { b , c , d , e }. Por la Regla 4 sabemos que { ∈ } no debe incluirse: no está incluida en PRIMERO(D), y por tanto resulta imposible deducir la cadena vacía a partir de A. PRIMERO(Aa) es un caso al que conviene prestar atención, aunque no deja de ser un caso más de aplicación de la Regla 4: si PRIMERO(BCD) incluyese {∈}, habría que incluir {a} enPRIMERO(A). Como no es así, no lo incluimos, quedando: PRIMERO(A) = PRIMERO(BCD) = { b , c , d , e } Resultado: PRIMERO(A) = { b , c , d , e } PRIMERO(B) = { b , ∈ } PRIMERO(C) = { c , ∈ } PRIMERO(D) = { d , c , e }

Cálculo de SIGUIENTE
Si A es un símbolo No Terminal de una gramática, SIGUIENTE(A) es el conjunto de Terminales (incluyendo el símbolo de fin de cadena, $) que pueden aparecer justo...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Trabajadores Del Trabajo
  • trabajo del trabajo
  • Trabajo Del Trabajo
  • El trabajo y el Trabajador
  • Trabajo Trabajador
  • trabajo trabajo
  • trabajo trabajo
  • Trabajo de trabajo

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS