Práctica 10: Gramaticas y parsers de precedencia (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 01[editar]

¿Cuales de las siguientes gramaticas son de precedencia simple? Generar la tabla y de ser posible, reconocer la cadena dada.

a)

S −> if E then S else S | a
E −> E or b | b

w = if b then a else a

Respuesta

S E if then else a or b $
S = >
E = = >
if = y < < >
then = >
else = >
a >
or = >
b >
$ < < < < < < < <









Como se puede ver, if = E y if < E, por lo tanto hay mas de una relacion de precedencia entre los simbolos (conflicto) y por lo tanto la gramatica no es de precedencia simple. La tabla no esta terminada porque al no ser de precedencia simple no tiene sentido seguir...

b)

S −> AS | A
A −> (S) | ()

w = ()()

Respuesta

S A ( ) $
S = y > >
A = < < > >
( = < < = >
) > > >
$ < < < <







Esta gramatica tampoco es de precedencia simple, pero tratamos de reconocer la cadena para mostrar como se hace.

Reconocimiento de la cadena w = ()()

Pila Cadena Accion
$< ()()$ shift
$<(= )()$ shift
$<(=)> ()$ reduce: A -> ()
$<A< ()$ shift
$<A<(= )$ shift
$<A<(=)> $ reduce: A -> ()
$<A<A> $ reduce: S -> A
$<A=S> $ reduce: S -> AS
$ $ accept









c)

S −> SA | A
A −> (S) | ()

w = ()()

Respuesta

Aca se puede ver que ( = S y ( < S. Por lo tanto hay un conflicto y la gramatica no es de precedencia simple.

Ejercicio 02[editar]

Ejercicio 03[editar]

Ejercicio 04[editar]