kk3

Fundamentos de Ordenadores I
Examen Septiembre 00

Dep. de Tecnol. Comunicaciones
Univ. Carlos III de Madrid

2ª Parte: Problemas

Duración: 1 hora 30 minutos

Puntuación: 6.5 puntos (sobre 10)

Fecha: 19 de septiembre de 2000

Nota: No se podrán usar libros ni apuntes.

EJERCICIO 1 (2 puntos)

Sea la siguiente gramática: G=<E_T, E_N, S, P>, E_T={a, b, c}, E_N={S, A, B}, S=S, P={S -> AB, A -> aA, A -> B, B -> bA, B -> c}. Se pide:

Escriba una expresión regular que defina el mismo lenguaje que la gramática dada. (1 punto)
Defina un reconocedor finito no determinista que reconozca las cadenas del lenguaje definido por la gramática dada. (1 punto)

Solución:

Apartado 1

Esta claro que las cadenas del lenguaje definido por S se forman como concatenación de las cadenas de los lenguajes definidos por A y por B. Si analizamos las reglas de producción, podemos deducir que las cadenas del lenguaje A estan formadas por una secuencia cualquiera de a's y b's (de A -> aA se sigue que si se añade por la izquierda una a a una cadena del lenguaje A se obtiene una cadena del lenguaje A; de A -> B y B -> bA se sigue que si se añade por la izquierda una b a una cadena del lenguaje A se obtiene una cadena del lenguaje A; por tanto si se añade por la izquierda cualquier combinación de a's y b's a una cadena del lengauaje A se obtiene una cadena del lenguaje A), terminada con una c (la única forma de llegar a una derivación sin símbolos no terminales a partir de A es utilizando A -> B -> c). Finalmente, las cadenas del lenguaje B son o la cadena c o b concatenada con cualquier cadena de A. Por lo tanto tenemos:

A = (a | b)* c
B = b (a | b)* c | c
S = (a | b)* c (b (a | b)* c | c)

Apartado 2

RFND= <E, Q, f, q_i, Q_f>
E= {a, b, c}
Q= {q1, q2, q3, q4}
q_i= q1
Q_f= {q4}

EJERCICIO 2 (4.5 puntos)

La siguiente gramática define una parte de un lenguaje de programación dedicada a la declaración de tipos: G=<E_T, E_N, S, P>, E_T={NUM, IDENT, TYPE, EQ, ARRAY, COR, CHETE, DOTS, OF, PC, RECORD, END, DP}, E_N={<DT>, <DT_List>, <DType>, <DAType>, <DRType>, <RCampos>, <RCampo>}, S=<DT>, P={<DT> -> TYPE <DT_List>, <DT_List> -> <DType> PC <DT_List>, <DT_List> -> <DType>, <DType> -> <DAType>, <DType> -> <DRType>, <DAType> -> IDENT EQ ARRAY COR NUM DOTS NUM CHETE OF IDENT, <DRType> -> IDENT EQ RECORD <RCampos> END, <RCampos> -> <RCampo> PC <RCampos>, <RCampos> -> <RCampo>, <RCampo> -> IDENT DP IDENT}.

El significado de los símbolos terminales es el siguiente:

Símbolo	Significado	Símbolo	Significado
NUM	constante entera positiva o cero	IDENT	identificador
TYPE	palabra clave TYPE	EQ	=
ARRAY	palabra clave ARRAY	COR	[
CHETE	]	DOTS	..
OF	palabra clave OF	PC	;
RECORD	palabra clave RECORD	END	palabra clave END
DP	:

Se pide:

Defina un reconocedor de pila no determinista que reconozca las cadenas del lenguaje definido por la gramática dada. (0.8 puntos)
A continuación se presenta una declaración de tipos. Escriba la cadena de tokens que generaría el analizador léxico para este ejemplo y dibuje el árbol de derivación que permite derivar dicha cadena de tokens. (0.8 puntos)

TYPE
  T1= ARRAY [0..10] OF Integer;
  T2= RECORD
        e1: T1;
        e2: Boolean
      END

Indique el tipo de la gramática dada y el del lenguaje que define. Razone la respuesta. (1 punto)
Defina un conjunto de clases Java que representen a los árboles de sintaxis abstracta del lenguaje. (1 punto)
A continuación se muestra un fichero en formato CUP que realiza el análisis sintáctico del lenguaje. Complete la zona marcada con los puntos suspensivos ...(a)... correspondientes a la definición de símbolos no terminales (0.1 puntos) y la zona marcada con los puntos suspensivos ...(b)... correspondientes a las reglas de producción (0.8 puntos). Las acciones asociadas a las reglas de producción se encargarán de la generación del árbol de sintaxis abstracta para la gramática definida.

package Parser;
import java_cup.runtime.*;

parser code {:

public void syntax_error(Symbol s) {

  report_error("Error de sintaxis en linea " + s.left, null);

public void unrecovered_syntax_error(Symbol s) throws

  java.lang.Exception {

  report_fatal_error("", null);

:};

terminal TYPE, EQ, ARRAY, COR, CHETE, DOTS, OF, PC, RECORD, END, DP;
terminal Integer NUM;
terminal String IDENT;

...(a)...

...(b)...

Solución:

Apartado 1

Nota: El símbolo \ representa la cadena vacía.

RPND= <E, Q, PI, f, q₀, Q_f, p₀>
E= {NUM, IDENT, TYPE, EQ, ARRAY, COR, CHETE, DOTS, OF, PC, RECORD, END, DP}
Q= {q₀, q₁, q₂}
PI= {NUM, IDENT, TYPE, EQ, ARRAY, COR, CHETE, DOTS, OF, PC, RECORD, END, DP, <DT>, <DT_List>, <DType>, <DAType>, <DRType>, <RCampos>, <RCampo>, p₀}
Q_f= {q₂}
f: E U {\} x PI x Q -> P(PI^*x Q)

f(\, p₀, q₀) = {(<DT>p₀, q₁)}
f(\, <DT>, q₁)= {(TYPE <DT_List>, q₁)}
f(\, <DT_List>, q₁)= {(<DType> PC <DT_List>, q₁), (<DType>, q₁)}
f(\, <DType>, q₁)= {(<DAType>, q₁), (<DRType>, q₁)}
f(\, <DAType>, q₁)= {(IDENT EQ ARRAY COR NUM DOTS NUM CHETE OF IDENT, q₁)}
f(\, <DRType>, q₁)= {(IDENT EQ RECORD <RCampos> END, q₁)}
f(\, <RCampos>, q₁)= {(<RCampo> PC <RCampos>, q₁), (<RCampo>, q₁)}
f(\, <RCampo>, q₁)= {(IDENT DP IDENT, q₁)}
f(NUM, NUM, q₁)= {(\, q₁)}
f(IDENT, IDENT, q₁)= {(\, q₁)}
f(TYPE, TYPE, q₁)= {(\, q₁)}
f(EQ, EQ, q₁)= {(\, q₁)}
f(ARRAY, ARRAY, q₁)= {(\, q₁)}
f(COR, COR, q₁)= {(\, q₁)}
f(CHETE, CHETE, q₁)= {(\, q₁)}
f(DOTS, DOTS, q₁)= {(\, q₁)}
f(OF, OF, q₁)= {(\, q₁)}
f(PC, PC, q₁)= {(\, q₁)}
f(RECORD, RECORD, q₁)= {(\, q₁)}
f(END, END, q₁)= {(\, q₁)}
f(DP, DP, q₁)= {(\, q₁)}
f(\, p₀, q₁) = {(\, q₂)}
Para cualquier otro trío (x, y, z) de parámetros de entrada, f(x, y, z) = {}

Apartado 2

Cadena de tokens: TYPE IDENT EQ ARRAY COR NUM DOTS NUM CHETE OF IDENT PC IDENT EQ RECORD IDENT DP IDENT PC IDENT DP IDENT END

Árbol de derivación:

Apartado 3

La gramática que se proporciona es de tipo 2, ya que todas sus reglas son de tipo 2 y existen reglas que no son de tipo 3 (por ejemplo, <DType> -> <DAType>). Sin embargo, el lenguaje que se define es de tipo 3. Esto se puede ver obervando que las cadenas de este lenguaje se pueden formar utilizando los operadores disponibles en expresiones regulares: unión, concatenación y cierres. Para empezar, las cadenas del lenguaje que define la gramática se forman concatenando el simbolo TYPE con cadenas del lenguaje <DT_List>, por lo que el lenguaje que define la gramática es regular si el lenguaje <DT_List> tambien lo es. El lenguaje <DT_List> es exactamente (<DType> PC)* <DType>, luego <DT_List> es regular si <DType> también lo es. El lenguaje que define <DType> es la unión de <DAType> (cuyo lenguaje esta formado por una única cadena) y <DRType>. Luego <DType> es regular si lo es <DRType>. El lenguaje <DRType> es una concatenación de símbolos no terminales y el lenguaje <RCampos>, luego <DRType> sera regular si lo es <RCampos>. El lenguaje <RCampos> es exactamente (<RCampo> PC)* <RCampo>, luego <RCampos> es regular si <RCampo> lo es, pero el lenguaje <RCampo> esta formado por una única cadena, luego es regular igual que <RCampos>, <DRType>, <DType>, <DT_List>, <DT>.

Apartado 4

Nota: Se ha utilizado un mismo interfaz para cada uno de estos conjuntos de símbolos no terminales:

<DT> y <DT_List> (contienen los mismos datos, una lista de declaraciones de tipos).
<DType>, <DAType> y <DRType> (aunque los datos contenidos por <DAType> y <DRType> son distintos, representan elementos del lenguaje que pertenecen a la misma categoría, y el utilizar el mismo interfaz no produce conflictos).
<RCampos>
<RCampo>

package AST;

import java.util.*;

public interface DTList {
public Vector ObtenerListaTipos();
}

package AST;

public interface DType { }

package AST;

import java.util.*;

public interface ListaCampos {
public Vector ObtenerListaCampos();
}

package AST;

public interface DCampo { }

package AST;

import java.util.*;

public class UnTipo implements DTList {

private Vector listaTipos;

public UnTipo(DType tipo) {
listaTipos= new Vector();
listaTipos.addElement(tipo);
}

public Vector ObtenerListaTipos() {
return listaTipos;
}
}

package AST;

import java.util.*;

public class VariosTipos implements DTList {

private Vector listaTipos;

public VariosTipos(DType tipo, DTList lista) {
listaTipos= lista.ObtenerListaTipos();
listaTipos.addElement(tipo);
}

public Vector ObtenerListaTipos() {
return listaTipos;
}
}

package AST;

public class Array implements DType {
public String nombre;
public Integer rango1;
public Integer rango2;
public String tipo;

public Array(String n, Integer r1, Integer r2, String t) {
    nombre=n;
    rango1=r1;
    rango2=r2;
    tipo=t;
}
}

package AST;

public class Record implements DType {
public String nombre;
public ListaCampos lista;

public Record(String n, ListaCampos l) {
nombre=n;
lista=l;
}
}

package AST;

import java.util.*;

public class UnCampo implements ListaCampos {

private Vector listaCampos;

public UnCampo(DCampo campo) {
listaCampos= new Vector();
listaCampos.addElement(campo);
}

public Vector ObtenerListaCampos() {
return listaCampos;
}
}

package AST;

import java.util.*;

public class VariosCampos implements ListaCampos {

private Vector listaCampos;

public VariosCampos(DCampo campo, ListaCampos lista) {
listaCampos= lista.ObtenerListaCampos();
listaCampos.addElement(campo);
}

public Vector ObtenerListaCampos() {
return listaCampos;
}
}

package AST;

public class RCampo implements DCampo {
public String nombre;
public String tipo;

public RCampo(String n, String t) {
nombre= n;
tipo= t;
}
}

Apartado 5

import AST.*;
 
parser code {:
public void syntax_error(Symbol s) {
  report_error("Error de sintaxis en linea " + s.left, null);
}
 
public void unrecovered_syntax_error(Symbol s) throws
  java.lang.Exception {
  report_fatal_error("", null);
}
:};
 
terminal TYPE, EQ, ARRAY, COR, CHETE, DOTS, OF, PC, RECORD, END, DP;
 
terminal String IDENT;
terminal Integer NUM;
 
non terminal DTList DT, DTList;
non terminal DType DType;
non terminal ListaCampos RCampos;
non terminal DCampo RCampo;
 
start with DT;
 
DT    ::= TYPE DTList:d                         {:RESULT=d; :} ;
 
DTList::= DType:d1 PC DTList:d2                 {:RESULT=new
          VariosTipos(d1, d2); :}
      |   DType:d                               {:RESULT=new UnTipo(d);
          :} ;
 
DType ::= IDENT:i1 EQ ARRAY COR NUM:n1 DOTS NUM:n2 CHETE OF IDENT:i2
                                                {:RESULT=new
          Array(i1,n1,n2,i2); :}
      |   IDENT:i EQ RECORD RCampos:r END       {:RESULT=new
          Record(i,r); :} ;
 
RCampos ::= RCampo:r1 PC RCampos:r2             {:RESULT=new
            VariosCampos(r1,r2); :}
        |   RCampo:r                            {:RESULT=new UnCampo(r);
            :} ;
 
RCampo ::= IDENT:i1 DP IDENT:i2                 {:RESULT=new
           RCampo(i1,i2); :} ;

Duración:	1 hora 30 minutos
Puntuación:	6.5 puntos (sobre 10)
Fecha:	19 de septiembre de 2000
Nota:	No se podrán usar libros ni apuntes.