| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO Problema Unidad 8.4 Problemas 1-10 Problemas 11-20 Problemas 21-30

Problemas 31-40

Problemas 41-50

Bibliografía

PROBLEMARIO

Problemas 11-20

> 11. Escribir todas las derivaciones posibles de la sentencia a + a*a para la gramática siguiente:

> <expresión> → <expresión> + <término>
> <expresión> → <término>
> <término> → <término> * <factor>
> <término> → <factor>
> <factor> → a
> <factor> → (<expresión>)

> En la Figura siguiente se da la solución. Dado el número elevado de formas sentenciales,
> se dan las transiciones en forma de tabla, señalándose los tres
> tipos de derivación (izquierda, derecha y general).

> 12.- Describir el lenguaje definido por la gramática siguiente:

> S → ab S → aSb

> El lenguaje es el definido por la expresión regular anbn para n> O.

> 13.- Comprobar si son vacios los lenguajes definidos por las 4 gramáticas siguiente:

> a.- S → AB C → a
> b.- S → AB B → Ca C → a
> c.- S → Sa
> d.- S → Sa S → b

> Sólo d) define un lenguaje no vacío dado por ba *

> 14.- Comprobar si es vacio el lenguaje definido por la gramática del problema 11.

> Aplicando el algoritmo del texto se obtiene:

> y como el axioma <expr> aparece en NUEVO el lenguaje no es vacío.

> 15.- Dado el árbol sintáctico siguiente, escribir las reglas BNF de la gramática correspondiente.

> Del subárbol de cada meta noción se puede escribir, como sabemos, la regla
> BNF leyéndolo de izquierda a derecha:

> s → abSA s → AB A → a A → Aa B → c

> el único problema adicional es que si existieran más reglas BNF que no se
> hubieran empleado en la construcción de este árbol, por ejemplo B → d.

> 16.- Dados los tres diagramas de Conway siguientes extraídos del PASCAL, describir la gramática libre de contexto con reglas BNF.

> Los vocabularios y las reglas son:

> N = {<Sentencia>, <Sent _ sin_ etiq> , <Sent _ asig> , <Sent _ comp>, <L_sent> }
> T = {e : v:= a begin end ;}

> <Sentencia> → e : <Sent_sin_etiq> | <Sent_sin_etiq>
> <Sent _ sin_ etiq> → λ | <Sent_asig> | <Sent_comp>
> <Sent _ asig> → v := a
> <Sent_comp> → begin <L_sent> end
> <L_sent> → <Sent> | <L_sent> ; <Sent>

> Nota: En el aspa de la figura anterior se introduce la metanoción <Sent_sin_etiq>

> 17.- Convertir la gramática resultado del problema 16 a otra sin λ.

> Sólo existe la regla λ siguiente:

> <Sent_sin_etiq> → λ

> aplicando el algoritmo del texto, resultan además anulables las metanociones
> <Sent> y <L_sent> . Al ser anulable el axioma <Sent> y aparecer
> en partes derechas, introducimos otro axioma <Nueva_sent>, quedando la gramática.

> <Nueva sent> → λ
> <Nue,va _ sent> → <Sentencia>
> <Sentencia> → e: <Sent_sin_etiq> | <Sent_sin_etiq>
> <Sent _ sin_ etiq> → <Sent _ asig> | <Sent _ comp>
> <Sent _ asig> → v := a
> <Sent_comp> → begin <L_sent> end | begin end
> <L sent> → <Sent> | <L sent> ; <Sent> | <L_sent>;

> 18.- Escribir las reglas BNF y EBNF de la gramática que describe un lenguaje de programación análogo al PASCAL que tenga estas características:
> El programa es un bloque seguido de un punto.

> Un bloque que pueda llevar:
> Una parte de constantes(opcional),
> Una parte de variables (opcional),
> Una parte de procedimientos (puede haber ninguno o varios);
> La parte de constantes consta de la palabra reservada const y de una o varias igualdades “identificador = entero”. Al final punto y coma,
> La parte de variables consta de la palabra reservada var y de uno o varios identificadores separados por comas. Al final punto y coma,
> La parte de procedimientos consta de la palabra reservada procedure seguida de un bloque,
> La sentencia puede ser de los tipos:
> De asignación, de una expresión a un identificador,
> De llamada de un procedimiento con call y el nombre,
> La compuesta: varias sentencias encerradas entre begin y end,
> La condicional, pero sin else,

> La de ciclo while con una condición.

> <Programa> → <Bloque>.
> <Bloque> → [<Constante>] [ <variable>] <Proced'> <Sentencia>
> <Constante> → const <Ident> = <Entero> , <Ident> = <Entero>;
> <Variable> → var <Ident> , <Ident>;
> <Proced> → procedure <Ident> ; <Bloque>;
> <Sentencia> → <S_Asig> | <S_Llam> | <S_Comp> | <S_Cond> | <S_Bucle> | λ
> <S_Asig> → <Ident> := | <Expr>
> <S_Llam> → call <Ident>
> <S_Comp> → begin <Sentencia> ; <Sentencia> end
> <S_Cond> → if <Condición> then <Sentencia>
> <S_Bucle> → while <Condición> do <Sentencia>
> <Condición> → <Expr> = <Expr>
> <Expr> → [ + | - ] <Término> [+ | - ] <Término>
> <Término> → <Factor> [* | /] <Factor>
> <Factor> → <Ident> | <Entero> | (<Expr>)

> T = {, const var . ; procedure := call begin end if then while do = + - * /}
> Con reglas BNF simples será:

> <Programa> → <Bloque>-
> <Bloque> → <Constante> <'variable> <Proced'> <Sentencia>
> <Constante> → const. <L _ Const.> | λ
> <L Const.> → <Ident> ,= <Entero> | <Ident> = <Entero>, <L _ Const> ;
> <Variable> → var <L_ Vars.> | λ

> <L Vars.> → <Ident> ; | <Ident> , <L _ vars.>;
> <Proced'> → <L_Proceds'> | λ

> <L Proceds'> → procedure <Ident>' <Bloque> ; |procedure <Ident> <Bloque> ; <L_roceds'>

> <Sentencia> → <S_Asig'> | <S_Llam'> | <S_Comp'> <S_Cond'> | <S_Bucle> | λ
> <S_Asig'> → <Ident> := <Expr>
> <S Llam'> → call <Ident>
> <S_Comp'> → begin <L_Sents'> end
> <L Sents.> → <Sentencia> -, <Sentencia> ; <L Sents.>
> <S Cond'> → if <Condición> then <Sentencia>
> <S Bucle> → while <Condición> do <Sentencia>
> <Condición> → <Expr> = <Expr>
> <Expr> → <Expr> + <Término> | <Expr> - <Término> | <Factor>
> <Término>→ <Término> * <Factor> | <Término> / <Factor> | <Factor>
> <Factor> → <Ident> | <Entero> | (<Expr>)

> así pues la EBNF tiene 22 alternativas, mientras la BNF tiene 37.

> 19.- Dada la gramática del problema 16, relativa a las expresiones aritméticas, pasarla a la forma normal de Greibach.

> Primero suprimir las reglas unitarias, como se indica en el texto. Luego
> al suprimir la recursividad por la izquierda, queda:

> E → T | TE’
> E' → +T | + TE'
> T → F | FT’
> etc.

> 20.- Escribir la gramática que defina la regla de asignación múltiple de PL/I:

> a, b, c = 0;

> ¿Por qué no se escribe esta sentencia con formato a = b = 0?

> <Sent mult> → <Lista_vars.> = <Expr>
> <Lista vars> → <Ident> | <Lista _ vars.> , <Ident>

> El PL/I, como otros lenguajes, tiene el problema del uso del " =" como el
> símbolo de asignación y como operador de relación. La sentencia a = b = 0,
> asigna a "a" verdadero o falso según que "b" sea nulo o no.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello