TP_GyL

Vista previa del material en texto

TRABAJO PRÁCTICOTRABAJO PRÁCTICO
B. GRAMÁTICAS Y LENGUAJES 
13. Defina los conjuntos P de la gramática de G = { {S, A, B, C}, {0, 1}, S, P } que reconozca: 
0 0 1 0 1 0
14. Defina los conjuntos P de la gramática de G = { {S, A, B, C}, {0, 1}, S, P } que reconozca: 
0 0 0 1 0 1
15. Definir las reglas de una gramática Tipo 2 en base a la especificación dada, que reconozca el lenguaje: 
L1 = {wncwn / w ε {a, b} n > 0}
G1 = ({A, S}, {a, b, c}, P, S)
16. Defina las reglas de producción para el lenguaje: L1 = { an c bm / n > 0 y m ≥ 0 }
17. Para la especificación dada dibuje el árbol de derivación para: a a c b b
P = { e0 � a e1, e1 � a e1 | c e2, e2 � b e2 | λ }
18. Sea la cuádrupla es G = ({S,A,B}, {0, 1}, P, S) con el siguiente conjunto de producciones, indique 3
cadenas válidas diferentes y dibuje los respectivos árboles de derivación:
P : { S -> A1B, A -> 0A | λ, B -> 0B | 1B | λ }
19. Dibuje el árbol de derivación para la cadena z = (x + y) * z correspondiente a la siguiente gramática:
ASSIGN -> ID ‘=’ EXPR
ID -> ‘x’ | ‘y’ | ‘z’
EXPR -> ID ‘+’ EXPR | EXPR ‘*’ ID | ‘(‘ EXPR’)’ | ID
20. Verificar si la siguiente gramática, genera cadenas ambiguas, en cuyo caso dar los ejemplos.
G = ({‘a’, ‘+’, ‘*’, ‘(‘, ‘)’}, {S}, S, P)
P = {S := ‘a’, S := S ‘+’ S, S := S * S, S := S}
21. Construya una gramática regular no ambigua que genere todas las cadenas de 0 y 1 en las cuales los 0, si
aparecen, lo hacen en grupos individuales de a tres.
Ej. cadenas que pertenecen al lenguaje Ej. cadenas que NO pertenecen al lenguaje
1,11111, 000, 1000, 1110001000 0, 00, 11000011, 000000, 000100 
22. Escriba las reglas de producción para la gramática G1, no ambigua, que reconoce el lenguaje L1.G1 =
({A}, {a, b, c}, P, S1) L1 = {wcwR / w Є {a | b} y R > 0}
Sintaxis y Semántica de Lenguajes: Guía de trabajos prácticos 3
TRABAJO PRÁCTICOTRABAJO PRÁCTICO
23. Completar las reglas de producción para la gramática.
Sea G = ({A, B}, {a}, P, S) una gramática regular lineal a derecha que genera L = {a2n / n ≥ 0}
S→ε S→ ?
A →aB A →?
B →?
24. Completar las reglas de producción para la gramática.
Sea G = ({A, B, C}, {0, 1, 2, 3}, P, S) que genera: L = {0i 1i+k 2k 3n+1 / i, k, n ≥ 0 }
S→ ABC S→?
S→ BC S→?
A → 0A1 A →?
B → 1B2 B →?
C → 3C C→?
25. Dibuje el diagrama sintáctico equivalente:
<ModDeclaration> ::= <MODULE> 'ident' ['priority'] ';' {<Import>} <Block> 'ident''.'
26. Exprese el equivalente del siguiente diagrama sintáctico, en notación EBNF: 
Declaration
27. Dibuje el diagrama sintáctico equivalente:
<list> ::= <alternative> { ‘|’ <alternative> }[ <else> ]
28. Exprese el equivalente del siguiente diagrama sintáctico, en notación EBNF y BNF: 
29. Re-escriba la expresión en notaciones pre y post fija. Dibuje el árbol de evaluación.
(x1 + x2) – x3 + (x4 / x5 + x6)
30. Re-escriba las expresiones en notaciones pre y post fija. Dibuje el árbol de evaluación.
a + b * c / d
Sintaxis y Semántica de Lenguajes: Guía de trabajos prácticos 4
TRABAJO PRÁCTICOTRABAJO PRÁCTICO
a * (b + c / 3) * d – k
(b / 2 + b * b – 4 * x – 2 * y) / (2 + a)
Sintaxis y Semántica de Lenguajes: Guía de trabajos prácticos 5