Boletín de ejercicios I: análisis léxico

Boletín de ejercicios I: análisis léxico

EJERCICIO 1

Sea la siguiente expresión regular (se supone que cada letra minúscula es un símbolo del alfabeto y los paréntesis se utilizan para agrupar expresiones):

a (ab | c)⁺ b

Indique cuales de las siguienes cadenas pertenecen al lenguaje definido por dicha expresión regular.

abc
ab
acabcb
acabacb

EJERCICIO 2

Escriba una expresión regular que defina el lenguaje de los números naturales codificados en decimal distintos de 0. Por ejemplo, son cadenas del lenguaje pedido las siguientes:

Sin embargo no son cadenas del lenguaje pedido las siguientes:

EJERCICIO 3

A continuación se especifica un analizador léxico por medio de una lista ordenada de tokens con sus correspondientes expresiones regulares:

CLOG= true | false
IDENT= (a | b | ... | z) (a | b | ... | z | 0 | 1 | ... | 9)^*
AND= and
OR= or

Escriba la cadena de tokens que generaría al procesar la cadena var1 and true or var2 un analizador léxico conforme con la especificación indicada y de acuerdo con las reglas explicadas en clase.

EJERCICIO 4

Se desea ejecutar una clase Java, llamada Clase1, perteneciente al paquete P1. La clase Clase1 utiliza a las clases Clase2, del paquete P2, la Clase3, del paquete P3 y la clase Clase4 del paquete P3.P4.

Los ficheros en formato class están ubicados de la siguiente forma:

Sistema operativo Windows:
- Clase1: C:\Java\dir1\P1\Clase1.class
- Clase2: C:\Java\dir2\P2\Clase2.class
- Clase3: C:\Java\dir2\P3\Clase3.class
- Clase4: C:\Java\dir2\P3\P4\Clase4.class
Sistema operativo Linux:
- Clase1: /usr/Java/dir1/P1/Clase1.class
- Clase2: /usr/Java/dir2/P2/Clase2.class
- Clase3: /usr/Java/dir2/P3/Clase3.class
- Clase4: /usr/Java/dir2/P3/P4/Clase4.class

Seleccione el sistema operativo que desee e indique, para dicho sistema operativo cual o cuales serían los mínimos directorios que habría que incluir en el classpath para que se pudiera ejecutar la clase Clase1.

EJERCICIO 5

Indique que valor tendrían que tomar las expresiones regulares A y B para que se verifiquen las siguientes ecuaciones (los paréntesis se utilizan para agrupar expresiones regulares y, por lo tanto, no son símbolos del alfabeto):

(ab | ba)^* = A (abab | abba | baba | baab)^*
(ab | ba)^* = ((ab | λ) (baba | baab | λ))^* B

Nota: puede haber varias soluciones correctas. Es suficiente con que escriba una de ellas.

EJERCICIO 6

Sea la siguiente expresión regular (se supone que cada letra minúscula es un símbolo del alfabeto y los paréntesis se utilizan para agrupar expresiones):

a ((ab | ba)⁺ | ac)^* c

Indique cuales de las siguienes cadenas pertenecen al lenguaje definido por dicha expresión regular.

ac
abaabbaacabc
aabbaacc

EJERCICIO 7

Sea el alfabeto A={a, b, c, ", \}. Sobre este alfabeto se define un lenguaje cuyas cadenas se ajustan a las siguientes reglas:

Las cadenas del lenguaje comienzan con el símbolo ".
A continuación puede venir cualquier cadena de símbolos (incluyendo la cadena vacía) del alfabeto que no contenga el símbolo ", salvo si dicho símbolo viene precedido del símbolo \.
Las cadenas terminan con el símbolo ", que no puede venir precedido del símbolo \.

Las siguientes cadenas pertenecen a este lenguaje:

"abc"
"ab\c"
"a\"b\"c"
"\""

Las siguientes cadenas no pertenecen a este lenguaje:

"abc (falla regla 3)
ab\c" (falla regla 1)
"ab"c" (falla regla 2)
"ab\" (falla regla 3)
"\" (falla regla 3)

Escriba una expresión regular que defina el lenguaje propuesto.

EJERCICIO 8

Defina por medio de una expresión regular el lenguaje L, de todas las cadenas no vacías del alfabeto A={a, b, c, d} tales que no contengan a la subcadena abc. Por ejemplo, las siguientes cadenas pertenecen a L:

a
ab
abac

Las siguientes cadenas no pertenecen a L:

babcd
dabcd
abc