Ingeniera

Creaci´n de un analizador sint´ctico
o
a
Modelos de Computaci´n
o

El objetivo de esta pr´ctica es crear un analizador sint´ctico rudimentario a partir de una gram´tica libre
a
a
a
decontexto. Dicha gram´tica debe modelizar un problema previamente propuesto por el alumno.
a

1.

Tareas a realizar

1. Formar un grupo de trabajo compuesto por dos personas.
2. Pensar un problemaoriginal. A partir de ´l, se definir´ un lenguaje libre de contexto (que no sea regular)
e
a
cuyas cadenas tengan una aplicaci´n particular en el problema propuesto y que correspondan a ciertas
opautas de comportamiento correctas del problema propuesto.
3. Encontrar una gram´tica libre de contexto limpia (sin producciones in´tiles, sin producciones nulas, sin
a
u
producciones unitarias,sin recursi´n a la izquierda y sin ciclos) que genere el lenguaje anterior.
o
4. Transformar la gram´tica anterior a Forma Normal de Chomsky y a Forma Normal de Greibach.
a
5. Presentar dos cadenasde s´
ımbolos terminales u y v tales que:
u pertenece al lenguaje que se est´ estudiando.
a
v no pertenece al lenguaje que se est´ estudiando.
a
6. Comprobar la pertenencia de u y de v con elalgoritmo YCK y el algoritmo de Earley. Visualizar el ´rbol
a
de derivaci´n que genera la cadena u.
o
7. Implementar en C++ un analizador sint´ctico basado en un algoritmo backtracking que permitasaber si
a
la palabra se puede generar a partir de sucesivas derivaciones.
8. Se deber´ realizar un documento por escrito que presente su soluci´n, adem´s de entregar electr´nicamente
a
o
a
olos ficheros de texto.
9. La documentaci´n de los puntos anteriores junto a los ficheros electr´nicos deben de ser defendidos. En la
o
o
defensa se debe explicar el problema tratado.

2.

Ejemplode problema propuesto

Formalizaci´n del lenguaje no verbal de un beb´ reci´n nacido. Cuando una persona con capao
e
e
cidad para comunicarse verbalmente acude a una consulta m´dica, en la...